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

Ein­lei­tung

Mit Ein­füh­rung des neuen Bil­dungs­plans ist das Thema "Gra­phen" neu hin­zu­ge­kom­men. Gra­phen ver­voll­stän­di­gen die Samm­lung von Da­ten­struk­tu­ren, die bis­her aus Lis­ten und Bäu­men be­stand1 . Gra­phen sind für eine Viel­zahl von An­wen­dun­gen eine ge­eig­ne­te Mo­del­lie­rung, für die viele Stan­dard­al­go­rith­men zur Ver­fü­gung ste­hen. Der Bil­dungs­plan sieht vor, diese Al­go­rith­men "von Hand" durch­zu­füh­ren oder im Leis­tungs­fach auch mit Hilfe einer ge­eig­ne­ten Bi­blio­thek zu im­ple­men­tie­ren.

Im Fol­gen­den wer­den zu­nächst grund­le­gen­de Ei­gen­schaf­ten von Gra­phen er­läu­tert. Dann wird un­ter­sucht, für wel­che An­wen­dun­gen Gra­phen ein­ge­setzt wer­den kön­nen und wel­che Lö­sungs­an­sät­ze exis­tie­ren. Das Lauf­zeit­ver­hal­ten die­ser Lö­sungs­an­sät­ze wird ana­ly­siert. Den Ab­schluss bil­den spe­zi­el­le Pro­ble­me, für die diese ver­schie­de­nen Lö­sungs­an­sät­ze vor­ge­stellt wer­den.

Gra­phen

„Ein Graph […] ist in der Gra­phen­theo­rie eine abs­trak­te Struk­tur, die eine Menge von Ob­jek­ten zu­sam­men mit den zwi­schen die­sen Ob­jek­ten be­ste­hen­den Ver­bin­dun­gen re­prä­sen­tiert. Die ma­the­ma­ti­schen Abs­trak­tio­nen der Ob­jek­te wer­den dabei Kno­ten (Ver­tex/Ver­ti­ces, auch Ecken oder Kno­ten­punk­te) des Gra­phen ge­nannt. Die paar­wei­sen Ver­bin­dun­gen zwi­schen Kno­ten hei­ßen Kan­ten (Edge, manch­mal auch Bögen2 ). […] Häu­fig wer­den Gra­phen an­schau­lich ge­zeich­net, indem die Kno­ten durch Punk­te und die Kan­ten durch Li­ni­en dar­ge­stellt wer­den.“3

Im Bil­dungs­plan der Kurs­stu­fe wer­den die Be­grif­fe Kno­ten und Kante ex­pli­zit ge­nannt. In IMP (Ma­the­ma­tik Klas­se 8) wird al­ler­dings Kno­ten­punkt und Kante ein­ge­führt. Im Fol­gen­den wer­den die Be­grif­fe aus der Kurs­stu­fe ein­ge­setzt.

In Klas­se 8 wurde eine di­dak­tisch re­du­zier­te De­fi­ni­ti­on emp­foh­len, die einen an­schau­li­chen Zu­gang er­mög­licht, z.B.:

Gra­phen

Ein Graph ist eine geo­me­tri­sche Figur aus end­lich vie­len Kno­ten­punk­ten und Kan­ten, die ei­ni­ge die­ser Punk­te ver­bin­den. Die Kan­ten müs­sen nicht ge­rad­li­nig ver­lau­fen und kön­nen sich über­kreu­zen. Mehr­fach­kan­ten, Schlin­gen und iso­lier­te Kno­ten sind eben­falls zu­ge­las­sen.

oder auch knap­per:

Gra­phen

Ein Graph ist ein Ge­bil­de, das aus Kno­ten­punk­ten4 und Kan­ten be­steht. Jede Kante ver­bin­det 2 Kno­ten­punk­te.

Diese De­fi­ni­ti­on ist auch für die Kurs­stu­fe prä­zi­se genug.

Wich­tig ist, dass "ein Graph eine Struk­tur be­zeich­net und ein to­po­lo­gi­scher Be­griff ist, da es auf die Länge der Kan­ten oder die Win­kel zwi­schen den Kan­ten nicht an­kommt."5 Daher ist die Po­si­ti­on der Kno­ten und der ge­zeich­ne­te Ver­lauf der Kan­ten ir­re­le­vant und keine Ei­gen­schaft des Gra­phen. Das be­kann­te „Haus des Ni­ko­laus“ kann gut als Aus­gangs­punkt die­nen, um zu ver­an­schau­li­chen, dass man beim Zeich­nen eines Gra­phen viele Frei­hei­ten hat6 :

Das Haus des Nikolaus wird schrittweise zu topologisch äquivalenten Graphen „verformt.“

Ab­bil­dung 1: Das Haus des Ni­ko­laus wird schritt­wei­se zu to­po­lo­gisch äqui­va­len­ten Gra­phen „ver­formt.“ ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 1_gra­phen_hin­ter­grund.odt

 

Matrix topologisch äquivalenter Graphen

Ta­bel­le: Ma­trix to­po­lo­gisch äqui­va­len­ter Gra­phen ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 1_gra­phen_hin­ter­grund.odt

Diese Re­prä­sen­ta­tio­nen von Gra­phen las­sen sich durch elas­ti­sche Ver­for­mun­gen in­ein­an­der über­füh­ren, sie sind to­po­lo­gisch äqui­va­lent. Die ge­mein­sa­men Ei­gen­schaf­ten (Be­zie­hun­gen zwi­schen Kno­ten und Kan­ten) las­sen sich dabei über­sicht­lich in einer Ta­bel­le bzw. Ma­trix dar­stel­len, die dann je­weils eine Klas­se to­po­lo­gisch äqui­va­len­ter Gra­phen re­prä­sen­tiert.

 

 

 

 

 

 

1 Ei­gent­lich sind na­tür­lich Lis­ten und Bäume spe­zi­el­le Gra­phen.

2 Bögen wer­den bis­wei­len auch als ge­rich­te­te Kan­ten auf­ge­fasst.

3 Wi­ki­pe­dia: siehe Seite „Graph (Gra­phen­theo­rie)“, URL: https://​de.​wi­ki­pe­dia.​org/​wiki/​Graph_(Gra­phen­theo­rie) (ab­ge­ru­fen: 28.03.2018)

4 Der im Bil­dungs­plan ver­wen­de­te Be­griff Kno­ten­punkt kann hilf­reich sein, wenn man die Vi­sua­li­sie­rung als Punkt be­to­nen möch­te, an­sons­ten ist die Be­zeich­nung Kno­ten üb­lich. Im Un­ter­richt bie­tet sich auch ein Rück­griff auf die Be­zeich­nung „Ver­kehrs­kno­ten­punkt“ in Stra­ßen- oder Bahn­net­zen an.

5 Ein­trag Graph, in: „Schü­ler­du­den Die Ma­the­ma­tik I“, Du­den­ver­lag, 1990, 5. Auf­la­ge, S.162

6 vgl. Nitz­sche: „Gra­phen für Ein­stei­ger“, View­eg+Teub­ner, Wies­ba­den, 2009, 3. Auf­la­ge, S.5

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][990 KB]

 

Wei­ter zu Ei­gen­schaf­ten eines Gra­phen