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

An­hang

Über­sicht - Be­grif­fe der ele­men­ta­ren Gra­phen­theo­rie

Ad­ja­zenz­ma­trix: Dar­stel­lung eines Gra­phen als Nach­bar­schaft­s­ta­bel­le, in der für jedes Paar von Kno­ten die An­zahl ihrer Ver­bin­dungs­kan­ten ein­ge­tra­gen wird. Ad­ja­zenz­ma­tri­zen und Ad­ja­zenz­lis­ten wer­den u.a. ge­nutzt, um Da­ten­struk­tu­ren als Gra­phen in den Com­pu­ter ein­ge­ben- und wei­ter­ver­ar­bei­ten zu kön­nen.

Baum: zu­sam­men­hän­gen­der Graph, der kei­nen Kreis ent­hält (u.a. sind dann zwei be­lie­bi­ge Kno­ten immer nur durch genau einen Kan­ten­zug ver­bun­den)

Be­wer­te­ter (ge­wich­te­ter) Graph: Graph, bei dem jeder Kante ein be­stimm­ter Zahl­wert zu­ge­ord­net ist.

Ein­fa­cher („schlich­ter“) Graph: Graph ohne Schlin­gen und Mehr­fach­kan­ten.

Eu­ler­graph: Graph, der min­des­tens einen ge­schlos­se­nen Eu­ler­schen Kan­ten­zug ent­hält.

Eu­ler­scher Kan­ten­zug (Eu­l­er­zug): Kan­ten­zug, der alle Kan­ten eines Gra­phen genau ein­mal ent­hält. Kno­ten kön­nen dabei mehr­mals durch­lau­fen wer­den. Man un­ter­schei­det of­fe­ne von ge­schlos­se­nen Eu­ler­schen Kan­ten­zü­gen:

Ge­schlos­se­ner Eu­ler­scher Kan­ten­zug(auch Eu­ler­tour):1 Eu­ler­scher Kan­ten­zug, der im An­fangs­kno­ten endet.

Ge­schlos­se­ner Kan­ten­zug: Kan­ten­zug, bei dem An­fangs- und End­kno­ten über­ein­stim­men.

Graph: Be­steht aus einer nicht­lee­ren Menge von Kno­ten und einer Menge von Kan­ten. Jede Kante ver­bin­det dabei zwei Kno­ten oder einen Kno­ten mit sich selbst.

Ha­mil­ton-Kreis: Kreis, der alle Kno­ten eines Gra­phen genau ein­mal ent­hält. Er muss dabei aber nicht alle Kan­ten des Gra­phen ent­hal­ten.

Ha­mil­ton­graph: Graph, der min­des­tens einen Ha­mil­ton-Kreis ent­hält.

In­zi­denz­ma­trix: Dar­stel­lung eines Gra­phen als Ma­trix, bei der die In­zi­denz von Kno­ten und Kan­ten do­ku­men­tiert wird. In­zi­denz­ma­tri­zen die­nen wie Ad­ja­zenz­ma­tri­zen der Ein­ga­be und Wei­ter­ver­ar­bei­tung von Da­ten­struk­tu­ren.

Kan­ten­zug: Eine Folge von an­ein­an­der­gren­zen­den Kan­ten (AB-BC-CD-…). Ein Kan­ten­zug kann offen oder ge­schlos­sen sein, er kann Kno­ten und Kan­ten mehr­mals ent­hal­ten.

Kreis: ge­schlos­se­ner Weg bzw. ge­schlos­se­ner Kan­ten­zug, der jeden sei­ner Kno­ten genau ein­mal ent­hält (unter der Be­din­gung, dass man kei­nen An­fangs­kno­ten aus­zeich­net, die­ser wäre sonst zwei­mal ent­hal­ten, da der Kan­ten­zug im An­fangs­kno­ten endet). Durch das „Schlie­ßen des Krei­ses“ kann jeder der Kno­ten als An­fangs­kno­ten be­trach­tet wer­den. Ein Kreis muss nicht alle Kno­ten eines Gra­phen ent­hal­ten, tut er es, so han­delt es sich um einen Ha­mil­ton-Kreis.

Mehr­fach­kan­ten (Mul­ti­kan­ten): par­al­le­le Kan­ten zwi­schen zwei Kno­ten

Mul­ti­graph: Graph, bei dem Mehr­fach­kan­ten zu­ge­las­sen sind.

Of­fe­ner Eu­ler­scher Kan­ten­zug: Eu­ler­scher Kan­ten­zug, bei dem Start- und End­kno­ten nicht iden­tisch sind (z.B. Haus des Ni­ko­laus“).

Of­fe­ner Kan­ten­zug: Kan­ten­zug, bei dem An­fangs- und End­kno­ten ver­schie­den sind.

Ord­nung eines Kno­tens (Wer­tig­keit, Grad): An­zahl der Kan­te­nen­den, die in einem Kno­ten zu­sam­men­tref­fen (bei einer Schlin­ge zäh­len beide Kan­te­nen­den).

Pla­na­re („plätt­ba­re“) Gra­phen: Graph, der durch Um­zeich­nen so als ebe­ner Graph dar­ge­stellt wer­den kann, dass sich seine Kan­ten nicht über­schnei­den. Die 5 pla­to­ni­schen Kör­per sind plätt­ba­re oder pla­na­re Gra­phen.

Tour: Ein Kan­ten­zug, der aus lau­ter ver­schie­de­nen Kan­ten be­steht. Im Ge­gen­satz zu einem Weg darf eine Tour Kno­ten auch mehr­mals ent­hal­ten.

Voll­stän­di­ger Graph: Graph, bei dem jeder Kno­ten mit jedem an­de­ren Kno­ten durch genau eine Kante ver­bun­den ist.

Weg (Pfad): Kan­ten­zug, der jeden sei­ner Kno­ten genau ein­mal ent­hält (Ein­zi­ge Aus­nah­me: „ge­schlos­se­ner Weg“ → Kreis), es kön­nen somit keine Kan­ten dop­pelt vor­kom­men.2

Zu­sam­men­hän­gen­der Graph: Graph, bei dem es von jedem Kno­ten zu jedem an­de­ren Kno­ten einen Kan­ten­zug gibt, der die bei­den ver­bin­det. Ist das nicht der Fall, so kann man den Gra­phen in Kom­po­nen­ten (Teil­gra­phen) auf­spal­ten, die keine Ver­bin­dung be­sit­zen.

1 Eine Eu­ler­tour wird fälsch­li­cher­wei­se auch als Eu­ler­kreis, Eu­ler­pfad oder Eu­l­er­weg be­zeich­net. Ein Eu­l­er­zug darf Kno­ten mehr­mals ent­hal­ten, was bei einem Kreis, Weg oder Pfad (mit Aus­nah­me des Start­kno­tens) nicht der Fall ist. Falls das Pro­blem im Un­ter­richt auf­tritt, soll­te man sich Zeit neh­men und es im Sinne der Aus­sa­gen­lo­gik zur Ab­gren­zung nut­zen: Jeder Eu­ler­kreis ist eine Eu­ler­tour, aber nicht jede Eu­ler­tour ist ein Eu­ler­kreis … .

2 Der Be­griff Weg wurde bei der Kon­zep­ti­on der Auf­ga­ben­blät­ter ge­mie­den, da er in Quel­len zu häu­fig in ver­schie­de­nen Be­deu­tun­gen ver­wen­det wird, was im Un­ter­richt nur zu un­nö­ti­gen Über­la­ge­run­gen füh­ren würde.

 

 

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

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

 

Wei­ter zu Un­ter­richts­ver­lauf