Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Re­prä­sen­ta­ti­on von Gra­phen

Be­grif­fe: Ad­ja­zenz­ma­trix, Ad­ja­zenz­lis­te

In IMP Klas­se 8 wer­den im The­men­be­reich "Aus­sa­gen­lo­gik und Gra­phen" (Ma­the­ma­tik) die Gra­phen ein­ge­führt. Schon da wird die Ad­ja­zenz­ma­trix als Re­prä­sen­ta­ti­ons­form für Gra­phen ver­wen­det. Auch im All­tag kom­men so­wohl die Ad­ja­zenz­lis­te (z.B. Liste der Freun­de von Per­so­nen als Grund­la­ge eines So­zio­gramms) als auch die Ad­ja­zenz­ma­trix (z.B. Ent­fer­nungs­ta­bel­len der gro­ßen Städ­te) vor, ohne dass dort der zu­grun­de­lie­gen­de Graph den meis­ten Men­schen be­wusst ist.

Die Schü­le­rin­nen und Schü­ler haben bis­her ge­lernt, Pro­blem­stel­lun­gen in Gra­phen zu über­set­zen. Im Ar­beits­blatt "06_­re­pra­e­sen­ta­ti­on.odt" wer­den aus­ge­hend von All­tags­bei­spie­len die da­zu­ge­hö­ri­gen Gra­phen er­stellt und die Be­grif­fe "ge­rich­tet/un­ge­rich­tet" und "ge­wich­tet/un­ge­wich­tet" wie­der­holt. (Auf­ga­ben 1 und 2).

Da­nach soll­te der Leh­rer die Be­grif­fe "Ad­ja­zenz­ma­trix" und "Ad­ja­zenz­lis­te" for­mal ein­füh­ren (Folie 1 der Prä­sen­ta­ti­on 06_­re­pra­e­sen­ta­ti­on_lauf­zeit.odp). Durch Über­füh­rung der einen Re­prä­sen­ta­ti­on in die an­de­re wird deut­lich, dass beide gleich­wer­tig sind (Auf­ga­ben 3 bis 6). Damit hat man die An­for­de­run­gen des Bil­dungs­plans er­füllt.

Er­gän­zung 1: Lauf­zeit­ana­ly­se

Man kann sich aber auch noch die Frage stel­len, wel­che Re­prä­sen­ta­ti­on nun die "bes­se­re" ist. Damit stellt sich na­tür­lich die Frage, was man damit ma­chen will. Da bei den do­mi­nie­ren­den Men­gen die Lauf­zeit eine große Rolle ge­spielt hat, kann man sich Ge­dan­ken ma­chen, wel­che Lauf­zei­ten die Grund­ope­ra­tio­nen auf Gra­phen in den ver­schie­de­nen Re­prä­sen­ta­tio­nen haben (wei­te­re Fo­li­en der Prä­sen­ta­ti­on 06_­re­pra­e­sen­ta­ti­on_lauf­zeit.odp). Vor­aus­set­zung dafür ist, dass die Schü­le­rin­nen und Schü­ler mit Lauf­zeit­ana­ly­sen von Lis­ten­ope­ra­tio­nen auf Array und ver­ket­te­ter Liste ver­traut sind. In der Prä­sen­ta­ti­on wird ein Array mit ver­ket­te­ten Lis­ten kom­bi­niert. Es wäre auch mög­lich, statt des Ar­rays eine wei­te­re ver­ket­te­te Liste zu be­nut­zen. Dies würde die Lauf­zei­ten än­dern. Diese De­tails soll­ten hier aber keine Rolle spie­len.

Ent­schei­dend ist aber, ob mit der An­zahl der Kno­ten au­to­ma­tisch auch die An­zahl der Kan­ten eines Kno­ten wächst. In vie­len Fäl­len hängt die An­zahl der Kan­ten eines Kno­tens nicht von der Ge­samt­an­zahl der Kno­ten ab (z.B. gehen von einer Kreu­zung in der Regel nur 4 Stra­ßen aus, ein Mensch hat 30-40 nä­he­re Be­kann­te, auch wenn die Welt­be­völ­ke­rung steigt usw.). Das an­de­re Ex­trem ist der voll­stän­di­ge Graph, bei dem jeder Kno­ten mit jedem an­de­ren ver­bun­den ist (z.B. bei Tra­ve­ling Sa­les­man Pro­blem).

Wich­tig ist es zu er­ken­nen, dass je nach be­nö­tig­ten Ope­ra­tio­nen, die Re­prä­sen­ta­ti­ons­form pas­send ge­wählt wer­den soll­te. In der Pra­xis wer­den Gra­phen meis­tens als Ad­ja­zenz­lis­ten im­ple­men­tiert, da diese we­ni­ger Spei­cher­platz be­nö­ti­gen. Ma­the­ma­ti­ker nut­zen aber gerne auch Ad­ja­zenz­ma­tri­zen, da sich man­che Al­go­rith­men dann auch als Ma­tri­zen­mul­ti­pli­ka­tio­nen be­schrei­ben las­sen8 .

Enaktive Übung (Holzbrett mit Nägeln und Schnur)

Bild­quel­le: En­ak­ti­ve Übung (Holz­brett mit Nä­geln und Schnur) ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt

Er­gän­zung 2: Tra­ve­ling Sa­les­man Pro­blem

Die Schü­le­rin­nen und Schü­ler kön­nen an­hand des für die Ad­ja­zenz­ma­trix ein­ge­führ­ten Tra­ve­ling Sa­les­man Pro­blems das Kon­zept des Nä­he­rungs­al­go­rith­mus wie­der­ho­len. Hier führt die Über­le­gung, wie viele mög­li­che Wege es geben kann, zu n! = n * (n-1) ...* 3* 2 * 1, da das die An­zahl der Mög­lich­kei­ten ist n Städ­te an­zu­ord­nen. Auch O(n!) ist für große n eine un­prak­ti­ka­ble Lauf­zeit. Eine schö­ne Mög­lich­keit, dies en­ak­tiv zu er­fah­ren, hat man bei einem Holz­brett mit her­aus­ste­hen­den Nä­geln (für die ein­zel­nen Städ­te) und einer Schnur, die um alle Nägel her­um­ge­führt wer­den muss. Je län­ger das Rest­stück der Schnur nach der Rund­rei­se ist, desto kür­zer ist die ge­fun­de­ne Rund­stre­cke. Das Op­ti­mum kann man an der Schnur farb­lich mar­kie­ren.

Eine Gree­dy-Nä­he­rungs­lö­sung er­hält man, wenn man in jedem Schritt die nächst­ge­le­gen noch nicht be­such­te Stadt an­fährt. Auch hier­für steht im Gra­phen­tes­ter ein Al­go­rith­mus be­reit, der an einer Deutsch­land­kar­te mit 40 Städ­ten aus­pro­biert wer­den kann. Da dies ein re­la­tiv ein­fa­cher Al­go­rith­mus ist, eig­net er sich für eine Ver­tie­fung der Im­ple­men­ta­ti­on von Gra­phen-Al­go­rith­men. Die Schü­le­rin­nen und Schü­ler hät­ten dann einen op­ti­ma­len und einen Nä­he­rungs­al­go­rith­mus im­ple­men­tiert.

Als Aus­blick könn­te man im Gra­phen­tes­ter an­de­re An­sät­ze zei­gen, um eine Nä­he­rungs­lö­sung zu fin­den. Ge­ge­be­nen­falls könn­te dies auch im Rah­men einer GFS von einem Schü­ler vor­ge­stellt wer­den.

 

8 Z.B. Er­reich­bar­keit von Kno­ten (=tran­si­ti­ve Hülle), https://​me-​lrt.​de/​12-​err​eich​bark​eits​prob​lem-​graph-​tran­si­ti­ve-​hulle (ab­ge­ru­fen 27.10.2020)

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][298 KB]

 

Wei­ter zu Kar­ten­fär­be­pro­blem (op­tio­nal)