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

Gra­phen

1. Stun­de: Eu­ler­sche Kan­ten­zü­ge

Ab­lauf und In­hal­te Hin­wei­se
  • Ein­füh­rung ers­ter Be­grif­fe (Graph, Kan­ten, Kno­ten­punk­te, zu­sam­men­hän­gen­der Graph), Pro­ble­ma­ti­sie­rung und Prä­zi­sie­rung an fik­ti­vem Graph (z.B. Dra­chen auf Rand)
  • Auf­trag 1: nie­der­schwel­li­ger Ein­stieg (AB, Nr. 1) PA: Zu­sam­men­hän­gen­de Gra­phen iden­ti­fi­zie­ren, nicht zu­sam­men­hän­gen­de Gra­phen ge­eig­net er­gän­zen Prä­sen­ta­ti­on, in der Wei­ter­füh­rungs­pha­se folgt die De­fi­ni­ti­on von Eu­ler­schen Kan­ten­zü­gen (of­fe­nen und ge­schlos­se­nen)
  • Auf­trag 2: Eu­ler­sche Kan­ten­zü­ge in Gra­phen (AB, Nr. 2) en­ak­ti­ver Zu­gang durch (men­ta­le) „Kan­ten­wan­de­run­gen“ Vi­sua­li­sie­rung durch Nach­zeich­nen und ggf. Num­me­rie­ren,
  • op­tio­nal: kur­zes Rol­len­spiel, s. rechts
  • Auf­trag 3: hin­rei­chen­de Be­din­gung für EKZ (AB, Nr. 3) ggf. Un­ter­stüt­zung durch Tipps, al­ter­na­tiv auch an „Rol­len­spiel“ an­knüp­fen­de Er­ar­bei­tung, Prä­sen­ta­ti­on, Er­geb­nis­si­che­rung
  • Re­fle­xi­on und Haus­auf­ga­ben (ggf. dif­fe­ren­ziert)
  • evtl. ver­tie­fen­de Übun­gen (AB, Nr. 4), ei­ge­ne Eu­ler­gra­phen
  • Ma­te­ri­al:

    AB Gra­phen

    Übung Gra­phen

  • Bin­nen­dif­fe­ren­zie­rung durch auf­trags­ge­steu­er­te Er­ar­bei­tung: Un­ter­richts­gang ist als Folge von ge­stuf­ten Auf­trä­gen an­ge­legt, die je­weils von den SuS prä­sen­tiert, von der Lehr­per­son er­gänzt und ge­mein­sam ge­si­chert wer­den. Er­läu­te­run­gen des SSDL Karls­ru­he:

    03_au­g_auf­trags­steue­rung.pdf

  • Rol­len­spiel als al­ter­na­ti­ver bzw. er­gän­zen­der en­ak­ti­ver Zu­gang: Woll­fa­den wird als EKZ zwi­schen 5 Kno­ten (Schü­lern) ge­spannt, Ord­nun­gen wer­den „hoch­ge­zählt“, hin­rei­chen­de Be­din­gung für EKZ wird so in­tui­tiv ein­sich­tig, die For­mu­lie­run­gen aktiv vor­be­rei­tet.

Er­läu­te­run­gen

Abbildung Graph 1

Der nicht zu­sam­men­hän­gen­de Mul­ti­graph mit Schlin­ge am rech­ten Rand hat 9 Kno­ten und 10 Kan­ten. Er bie­tet Ge­le­gen­heit zur Prä­zi­sie­rung der De­fi­ni­ti­on. Las­sen Sie z.B. Kan­ten und Kno­ten zäh­len bzw. be­schrei­ben. Dabei las­sen sich u.a. fol­gen­de As­pek­te the­ma­ti­sie­ren:

- iso­lier­te Kno­ten („Augen“) als Kno­ten ohne Kan­ten („mit der Ord­nung 0“), dar­aus re­sul­tie­ren­de Auf­tei­lung in drei Teil­gra­phen, die nicht zu­sam­men­hän­gen,

- Schlin­ge (am Kopf) als Kante, die einen Kno­ten mit sich selbst ver­bin­det,

- dop­pel­te Kan­ten unten als Mehr­fach­kan­ten (bzw. Mul­ti­kan­ten),

- die to­po­lo­gisch nicht re­le­van­te „Über­la­ge­rung“ von Kan­ten

und mög­li­cher­wei­se auch das zen­tra­le Merk­mal eines Gra­phen als to­po­lo­gi­sche Struk­tur: Die „Ver­form­bar­keit“, ohne dabei seine we­sent­li­chen Ei­gen­schaf­ten zu ver­lie­ren. Die In­va­ri­anz ge­gen­über Ver­for­mun­gen lässt sich dabei dy­na­misch gut mit der Datei 01_au­g_a­b_graph_dra­chen.ggb vi­sua­li­sie­ren, indem man an ge­eig­ne­ten Punk­ten „zieht“.

Eine sys­te­ma­ti­sche Er­geb­nis­si­che­rung ist an die­ser Stel­le nicht sinn­voll, gleich­wohl kön­nen Schwer­punk­te ge­setzt und aus­ge­wähl­te As­pek­te an der Tafel fest­ge­hal­ten wer­den.

Kom­men­ta­re zu den ein­zel­nen Auf­ga­ben bzw. Auf­trä­gen:

  1. Zu­sam­men­hän­gen­de Gra­phen

    Die Auf­ga­be bie­tet einen ers­ten „wei­chen“ Ein­stieg und soll das Ver­ständ­nis für die be­son­de­ren Ei­gen­schaf­ten zu­sam­men­hän­gen­der Gra­phen ent­wi­ckeln, da die not­wen­di­gen und hin­rei­chen­den Be­din­gun­gen für die Exis­tenz Eu­ler­scher Kan­ten­zü­ge nur für diese Gra­phen gel­ten.

  2. Eu­ler­sche Kan­ten­zü­ge (EKZ)

    Die Auf­ga­be er­öff­net zu­nächst einen en­ak­ti­ven Zu­gang über das men­ta­le Su­chen bzw. das ak­ti­ve Nach­zeich­nen ver­schie­de­ner Eu­ler­scher Kan­ten­zü­ge, erste Ge­setz­mä­ßig­kei­ten wer­den mög­li­cher­wei­se ent­deckt und bei den Prä­sen­ta­tio­nen aus­ge­tauscht.

  3. Er­ar­bei­tung der all­ge­mei­nen Regel (hin­rei­chen­de Be­din­gung für EKZ)

    Falls Sie die De­fi­ni­ti­on der Ord­nung eines Kno­tens hier nicht an­ge­ben und statt des­sen fle­xi­bel im Er­ar­bei­tungs­pro­zess ein­brin­gen bzw. da­nach er­gän­zen möch­ten, lö­schen Sie sie bitte auf dem Ar­beits­blatt.

    Zur Un­ter­stüt­zung bie­tet sich bei Be­darf der Zu­satz­auf­trag an, ge­eig­ne­te Start- und End­kno­ten zu mar­kie­ren (siehe Lö­sung). Ei­ni­ge Schü­le­rin­nen und Schü­ler wer­den aber auch ohne diese Hilfe auf die rich­ti­ge Idee kom­men, al­ler­dings wird die For­mu­lie­rung der Ver­mu­tung si­cher­lich eine Her­aus­for­de­rung blei­ben.

    Op­tio­na­les „Rol­len­spiel“ zur in­halt­li­chen Vor­be­rei­tung

    5 S. stel­len sich als „Haus des Ni­ko­laus“ auf, sie „spie­len“ die Kno­ten, die Kan­ten blei­ben zu­nächst un­sicht­bar. Ein S. spannt zwi­schen den „Kno­ten“ mit einem Woll­fa­den „sei­nen“ Eu­ler­schen Kan­ten­zug auf. Jedes Mal, wenn er dabei einen Kno­ten pas­siert, nennt der Mit­schü­ler die Ord­nung „sei­nes“ Kno­tens, die An­zahl der an­kom­men­den und weg­ge­hen­den Kan­ten. Hier muss ein­ma­lig ge­klärt wer­den, dass der durch­ge­hen­de Woll­fa­den als 2 Kan­ten ge­zählt wer­den muss. Durch die di­dak­ti­sche Um­keh­rung des Pro­blems wird so ein Graph ge­ne­riert, der einen Eu­ler­schen Kan­ten­zug ent­hält und die hin­rei­chen­de Be­din­gung („höchs­tens zwei un­ge­ra­de Kno­ten“) wird in­tui­tiv er­fahr­bar. Durch das Hoch­zäh­len der Kno­ten­ord­nun­gen wird die For­mu­lie­rung einer all­ge­mei­nen Regel vor­be­rei­tet. Es wird die Ein­sicht an­ge­bahnt, dass sich die Ord­nung beim Durch­lau­fen eines Kno­tens immer um 2 er­höht. Al­ter­na­tiv könn­te statt einem Rol­len­spiel auch ein en­ak­ti­ver Zu­gang in Part­ner­ar­beit an­ge­bo­ten wer­den, bei dem jedes Team mit einem Woll­fa­den (genau pas­sen­der Länge) einen EKZ in einem Mo­dell eines Gra­phen span­nen muss (z.B. Holz­brett mit Nä­geln oder Kork­plat­te mit Steck­na­deln o.ä.). Hier­bei wären alle SuS aktiv ein­ge­bun­den.

    For­mu­lie­rung einer all­ge­mei­nen Regel

    Einen Vor­schlag fin­den Sie in der Mus­ter­lö­sung, es sind aber viele Va­ri­an­ten sind denk­bar. For­mu­lie­run­gen der SuS wer­den meist auf Be­we­gungs­vor­stel­lun­gen ba­sie­ren und müs­sen ggf. noch er­gänzt wer­den, z.B. könn­te for­mu­liert wer­den:

    - „Kno­ten, in die gleich viele Kan­ten hin­ein- wie hin­aus­füh­ren“ …

    - „man ver­lässt einen Kno­ten genau so oft wie man bei ihm an­kommt ...“

    Mög­li­che For­mu­lie­rungs­va­ri­an­te nach dem Rol­len­spiel:

    „Beim Durch­lau­fen eines Kno­tens er­höht sich seine Ord­nung immer um 2, da je­weils eine hin- und eine weg­füh­ren­de Kante zu zäh­len sind. Beim Start- und End­kno­ten er­höht sich die Ord­nung nur um „1“, so dass sie un­ge­ra­de bleibt. Nur wenn man zum Aus­gangs­punkt zu­rück­kehrt, hat auch der Start-End­kno­ten eine ge­ra­de Ord­nung.“

    Zur Ori­en­tie­rung hier noch zwei Schü­ler­for­mu­lie­run­gen aus der Er­pro­bung:

    „Bei mehr als zwei un­ge­ra­den Kno­ten gibt es kei­nen EKZ. Wenn von zwei Kno­ten eine un­ge­ra­de An­zahl von Kan­ten aus­geht und von allen an­de­ren Kno­ten eine ge­ra­de An­zahl, so gibt es einen EKZ, der offen ist. Wenn es nur Kno­ten mit ge­ra­der Kan­ten­an­zahl gibt, so gibt es einen EKZ, der ge­schlos­sen ist. “

    „Wenn die Ord­nun­gen aller Kno­ten ge­ra­de ist, so gibt es einen ge­schlos­se­nen EKZ. Wenn ein Graph un­ge­ra­de Kno­ten ent­hält, so gibt es nur dann einen EKZ, wenn es genau zwei un­ge­ra­de Kno­ten sind, ein Start- und ein Ziel­kno­ten.“

  4. Re­fle­xi­on am Stun­den­en­de

    Eu­ler­sche Kan­ten­zü­ge sind wie be­reits er­wähnt nur in zu­sam­men­hän­gen­den Gra­phen mög­lich, was aber an die­ser Stel­le nicht im Fokus steht und des­halb leicht ver­ges­sen wird. Man könn­te dies ab­schlie­ßend hin­ter­fra­gen, even­tu­ell auch mit einem der fol­gen­den Ge­gen­bei­spie­le an der Tafel pro­ble­ma­ti­sie­ren:

    Abbildung Gegenbeispiele

    Las­sen sich Kno­ten er­gän­zen, so dass im neuen zu­sam­men­hän­gen­den Gra­phen ein EKZ exis­tiert? Las­sen sich Brü­cken hin­zu­fü­gen, so dass ein EKZ mög­lich ist? Wel­che Mög­lich­kei­ten gibt es?

    Ver­tie­fungs­mög­lich­kei­ten:

    Prä­zi­se For­mu­lie­run­gen wie „Es darf höchs­tens 2 un­ge­ra­de Kno­ten geben“ sind nicht zu er­war­ten, könn­ten aber ge­mein­sam wie oben skiz­ziert ent­wi­ckelt wer­den, wenn man zuvor er­ar­bei­tet, dass es kei­nen Gra­phen mit nur einem un­ge­ra­den Kno­ten geben kann.

    Re­fle­xi­ons­an­re­gen­de Fra­gen:

    Warum ist die Summe der Ord­nun­gen aller Kno­ten das Dop­pel­te der Kan­ten­zahl? Warum ist die An­zahl der Kno­ten mit un­ge­ra­der Ord­nung immer ge­ra­de?1 Gilt dies nur in zu­sam­men­hän­gen­den Gra­phen? …

    Hin­weis: Das Rol­len­spiel bie­tet sich auch an, wenn man sol­che Fra­gen zur Ver­tie­fung stel­len möch­te. Dann könn­te man mit dem Woll­fa­den auch einen „be­lie­bi­gen“ Mul­ti­gra­phen mit EKZ er­zeu­gen, der dann als Graph mit Mehr­fach­kan­ten an die Tafel über­tra­gen wird, um aus­ge­hend vom kon­kre­ten Bei­spiel Ant­wor­ten zu fin­den.

    Ab­schlie­ßen­der Warn­hin­weis zu kom­bi­na­to­ri­schen Ne­ben­schau­plät­zen

    Auf die Frage nach der An­zahl der mög­li­chen EKZ soll­te man vor­be­rei­tet sein und wis­sen wie ge­fähr­lich sie im Un­ter­richt wer­den kann. Sie er­öff­net je nach Graph un­ge­ahn­te kom­bi­na­to­ri­sche Wel­ten, die an die­ser Stel­le auf jeden Fall ge­mie­den wer­den soll­ten. Bei 2a) („Haus des Ni­ko­laus“) wären es z.B. schon 44·2=88 ver­schie­de­ne Eu­ler­sche Kan­ten­zü­ge. Die An­zahl ist nicht ohne Wei­te­res er­kenn­bar, man braucht Ge­duld und Zeit.

    Bei 2d) wären es immer noch 16·2=32 Va­ri­an­ten. Sol­che kom­bi­na­to­ri­schen As­pek­te bie­ten Po­ten­zi­al für bin­nen­dif­fe­ren­zie­ren­de Zu­satz­auf­trä­ge, die dann aber auch an­ge­mes­sen nach­be­rei­tet wer­den müs­sen und Zeit er­for­dern. Bei 2b) hängt die An­zahl z.B. von der Wahl des Start­kno­tens ab, ins­ge­samt er­ge­ben sich hier 8·2·3·2+2·4·3·2=144 ver­schie­de­ne EKZ.

1 Ge­dan­ken­gang zum Nach­weis z.B. in: „Schü­ler­du­den Die Ma­the­ma­tik I“, Du­den­ver­lag, 1990, 5. Auf­la­ge, S.164 oder in: Peter Titt­man: „Gra­phen­theo­rie- eine an­wen­dungs­ori­en­tier­te Ein­füh­rung“, Han­ser, 2011, 2. Auf­la­ge, S.14

 

 

2. Stun­de: Mul­ti­gra­phen – Kö­nigs­ber­ger Brü­cken­pro­blem

Ab­lauf und In­hal­te Hin­wei­se
  • Prä­sen­ta­ti­on der Haus­auf­ga­ben durch SuS, Er­gän­zun­gen
  • Ko­gni­ti­ve Ak­ti­vie­rung mit kur­zer Bei­spiel­auf­ga­be aus dem Ma­te­ri­al oder ge­eig­ne­ter Ta­fel­skiz­ze eines Gra­phen
  • Kö­nigs­ber­ger Brü­cken­pro­blem (AB, Nr. 1)

    Ein­stim­mung, evtl. kurze An­ek­do­te zu Le­on­hard Euler

    Auf­trag 1: GA: Aus­pro­bie­ren, Stra­te­gie su­chen (2-3 min), Aus­tausch im Ple­num, Prä­sen­ta­ti­on von Ideen, ggf. Tipps

    Auf­trag 2: Zeich­net Gra­phen mit den Brü­cken als Kan­ten, um das Pro­blem zu lösen.

    Auf­trag 3: Sucht Eu­ler­sche Kan­ten­zü­ge …, ggf. wei­te­re deut­li­che­re Tipps, Prä­sen­ta­ti­on durch S.

    Auf­trag 4: Re­fle­xi­on: Was half euch bei der Lö­sung? No­tiert für eure Grup­pe die ent­schei­den­den As­pek­te! Prä­sen­ta­ti­on, Si­che­rung im Ple­num an Tafel, z.B.

    Er­folg­rei­che Stra­te­gie: Ge­bie­te als Kno­ten, Brü­cken als Kan­ten auf­fas­sen und Pro­blem als Graph dar­stel­len; Zu­rück­füh­ren auf Be­kann­tes (Eu­ler­sche Kan­ten­zü­ge)

  • De­fi­ni­ti­on: Mul­ti­gra­phen

    an­schlie­ßend Übungs­auf­ga­be (AB, Nr. 2)

  • Wahl­mög­lich­keit in Ab­hän­gig­keit des zeit­li­chen Ver­lau­fes:

    - Be­ar­bei­tung des Nacht­wäch­ter-Pro­blems (Nr.3)

    - Ver­tie­fung des Kö­nigs­ber­ger Brü­cken­pro­blems (Nr. 4)

    - ein­fa­che Übun­gen aus Fun­dus

  • Haus­auf­ga­be (ggf. dif­fe­ren­ziert)
  • Ma­te­ri­al:

    AB Mul­ti­gra­phen

    Übung Mul­ti­gra­phen

  • Bin­nen­dif­fe­ren­zie­rung durch auf­trags­ge­steu­er­te Er­ar­bei­tung, So­zi­al­form: Klein­grup­pen, 3-4 SuS. Auf­trä­ge sind ex­em­pla­risch und wer­den im Un­ter­richt bei Be­darf mo­di­fi­ziert.
  • fle­xi­bles Auf­ga­ben­ma­te­ri­al: Nacht­wäch­ter-Pro­blem ent­we­der zur Bin­nen­dif­fe­ren­zie­rung als Zu­satz­auf­trag für schnel­le Grup­pen oder als ver­tie­fen­de An­wen­dung der Stra­te­gie oder als er­gän­zen­de Haus­auf­ga­be. me­tho­di­sche, ko­ope­ra­ti­ve Va­ri­an­te: Grup­pen­puz­zle mit gleich­zei­ti­ger Er­ar­bei­tung des Kö­nigs­ber­ger Brü­cken- und des Nacht­wäch­ter-Pro­blems (siehe dazu hier) in die­sem Fall Zu­satz­auf­ga­be als „Puf­fer“ be­reit­hal­ten, z.B. AB, Nr. 3.

Er­läu­te­run­gen

Abbildung Graph 3

In der Ti­tel­zei­le wurde als Logo ein Mul­ti­graph ein­ge­bun­den: Das „Haus des Ni­ko­laus mit Kel­ler“. Falls Ihnen der Ein­stieg im Kon­text des Kö­nigs­ber­ger Brü­cken­pro­blems für Ihre Klas­se schwie­rig er­scheint, könn­ten Sie auch die­sen Gra­phen zur Ein­füh­rung von Mul­ti­gra­phen ver­wen­den: Was müss­te man am „Haus des Ni­ko­laus“ än­dern, damit man beim Zeich­nen in einem Zug am Aus­gangs­punkt endet? Ein ge­schlos­se­ner Eu­ler­scher Kan­ten­zug wird mög­lich, wenn zwi­schen bei­den un­ge­ra­den Kno­ten eine Kante hin­zu­ge­fügt wird, man er­hält den Kel­ler ...

  1. Kö­nigs­ber­ger Brü­cken­pro­blem

    Das Pro­blem des Stadt­rund­gangs wird auf auf das Zeich­nen eines Gra­phen in einem Zug zu­rück­ge­führt (Stra­te­gie des Zu­rück­füh­rens auf be­kann­te Zu­sam­men­hän­ge). Die Er­ar­bei­tung soll­te dabei auf die Klas­se ab­ge­stimmt wer­den:

    - Lö­schen Sie den Tipp, wenn Sie die Auf­ga­be of­fe­ner stel­len möch­ten.

    - Geben Sie wei­te­re Tipps im Laufe der Er­ar­bei­tung, falls Sie Pro­ble­me er­war­ten, z.B.

    „Zeich­net einen mög­li­chen Gra­phen ein / fasst Brü­cken als Kan­ten auf“, oder „Sucht nach Eu­ler­schen Kan­ten­zü­gen / no­tiert neben den Kno­ten ihre Ord­nung“.

    In Auf­ga­be 3b) ist be­reits ein Graph ein­ge­bun­den, der ge­nutzt wer­den könn­te.

  2. Auf­ga­be 2 ist zur Wie­der­ho­lung der Be­griff­lich­kei­ten und zur Übung ge­dacht.

    Der bin­nen­dif­fe­ren­zie­ren­de Zu­satz­auf­trag kann durch Ver­wen­dung der ein­ge­führ­ten Be­grif­fe an­ders for­mu­liert wer­den, z.B. „Fügt dem Graph mög­lichst we­ni­ge Kan­ten hinzu, so dass ein ge­schlos­se­ner Eu­ler­scher Kan­ten­zug exis­tiert“.

  3. Nacht­wäch­ter-Pro­blem

    Hier kann man bei Be­darf den Tipp geben, dass der Hof als Ge­biet be­rück­sich­tigt wer­den muss. Die Auf­ga­be kann über­sprun­gen oder als Haus­auf­ga­be ge­ge­ben wer­den, falls zu wenig Zeit vor­han­den sein soll­te.

  4. Op­tio­na­le Ver­tie­fung des Kö­nigs­ber­ger Brü­cken­pro­blems

    Alle Kno­ten haben un­ge­ra­de Ord­nung, ent­fernt man eine Kante (bzw. Brü­cke), so haben da­nach zwei der vier Kno­ten eine ge­ra­de Ord­nung. Dann ist ein of­fe­ner Eu­ler­scher Kan­ten­zug mög­lich, aber die ge­for­der­te Rück­kehr zum Aus­gangs­punkt bleibt un­mög­lich. Mann muss daher min­des­tens 2 Brü­cken ent­fer­nen. Damit alle Kno­ten ge­ra­de Ord­nung haben, muss eine der Brü­cken 1,2,3,4 und die rich­ti­ge der Brü­cken 5 oder 7 ent­fernt wer­den.

    Abbildung Graph 4

    Tat­säch­lich wurde in Kö­nigs­berg eine 8. Brü­cke über den Pre­gel und eine 9. Brü­cke über den Alten Pre­gel ge­baut2 , so dass heute „Euler-Spa­zier­gän­ge“ (Eu­l­er­we­ge) über alle Brü­cken mög­lich sind, al­ler­dings kann man nach wie vor nicht zum Aus­gangs­punkt zu­rück­keh­ren.

  5. Auf­ga­be 5 ist zur Dif­fe­ren­zie­rung ge­dacht und bin­det die drit­te Di­men­si­on ein.

    In stär­ke­ren Lern­grup­pen bie­tet sich hier ein kur­zer Ex­kurs zu „pla­na­ren bzw. plätt­ba­ren Gra­phen“ an, bei denen Über­schnei­dun­gen von Kan­ten in der ebe­nen Dar­stel­lung nicht er­laubt sind.3

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

3 Vgl. dazu Kap 8: „Vom Kör­per zum Gra­phen“, in Nitz­sche: „Gra­phen für Ein­stei­ger“, View­eg+Teub­ner, Wies­ba­den, 2009, 3. Auf­la­ge, S.5, S.165 ff. Ins­be­son­de­re die 5 „Pla­to­ni­schen Gra­phen“ (S.179) wären reiz­vol­le Ob­jek­te.

 

 

3. Stun­de: Ha­mil­ton-Krei­se – „Tra­vel­ling-Sa­les­man-Pro­blem (TSP)“

Ab­lauf und In­hal­te Hin­wei­se
  • Prä­sen­ta­ti­on der Haus­auf­ga­ben durch SuS, Er­gän­zun­gen
  • Ko­gni­ti­ve Ak­ti­vie­rung: Graph mit Eu­ler­schem Kan­ten­zug, Pro­blem­stel­lung bei Ha­mil­ton-Krei­sen von der bei Eu­ler­schen Kan­ten­zü­gen ab­gren­zen: Nun ist ein Kan­ten­zug ge­sucht, der jeden Kno­ten ein­mal ent­hält
  • De­fi­ni­ti­on Ha­mil­ton-Kreis
  • Auf­trag 1: PA: geo­me­tri­sche An­nä­he­rung (AB, Nr. 1)

    dif­fe­ren­zie­ren­der Zu­satz: Kan­ten ge­eig­net er­gän­zen

    Prä­sen­ta­ti­on durch SuS, ggf. Kon­troll­fra­gen

  • Auf­trag 2: Be­wer­te­te Gra­phen (AB, Nr. 2)

    Kon­zept ex­em­pla­risch ken­nen­ler­nen und nut­zen

    Prä­sen­ta­ti­on durch SuS

  • Auf­trag 3: TSP in Klein­grup­pen (2-3 S.)

    Dif­fe­ren­zie­ren­der Zu­satz­auf­trag Nr. 4

    Prä­sen­ta­ti­on durch Team / Grup­pe

  • Re­fle­xi­on (siehe Hin­weis rechts)

  • evtl. wei­te­re Übungs­auf­ga­ben aus Fun­dus
  • Haus­auf­ga­be (ggf. dif­fe­ren­ziert)
  • Ma­te­ri­al:

    AB Ha­mil­ton­krei­se

    Übung Ha­mil­ton­krei­se

  • Bin­nen­dif­fe­ren­zie­rung durch auf­trags­ge­steu­er­te Er­ar­bei­tung So­zi­al­form: PA und Klein­grup­pen
  • Re­fle­xi­on

    Bezug zu Ha­mil­ton-Krei­sen, TSP als Suche nach Ha­mil­ton-Kreis mit ge­rings­tem Ge­samt­wert er­fas­sen, Wie viele Ha­mil­ton-Krei­se hat ein voll­stän­di­ger Graph mit 4 Kno­ten?

  • Mög­li­che Ver­tie­fung (1):

    bei 5 bzw. 6 Kno­ten? Vi­sua­li­sie­rung, Si­che­rung, auch Ver­all­ge­mei­ne­rung? (vgl. Er­läu­te­run­gen)

  • Mög­li­che Ver­tie­fung (2):

    in leis­tungs­star­ken Grup­pen: Be­grif­fe eu­lersch und ha­mil­tonsch ein­füh­ren und ab­gren­zen (vgl. Er­läu­te­run­gen)

Er­läu­te­run­gen

Im Bil­dungs­plan ist der Fach­be­griff Ha­mil­ton­scher Kan­ten­zug aus­ge­wie­sen. In der Li­te­ra­tur ist da­ge­gen die Be­zeich­nung Ha­mil­ton-Kreis üb­lich, der daher hier ein­ge­bun­den und be­vor­zugt ver­wen­det wurde. Es wurde dar­auf ver­zich­tet, im Kon­text Ha­mil­ton­scher Gra­phen auch of­fe­ne Kan­ten­zü­ge zu be­trach­ten.

Da wenig Zeit zur Ver­fü­gung steht und mit den Be­grif­fen nicht an­ge­mes­sen wei­ter ge­ar­bei­tet wer­den kann, wur­den fol­gen­de mög­li­chen De­fi­ni­tio­nen noch nicht ein­ge­bun­den:

Abbildung Definitionen

Da es sich um zen­tra­le Be­grif­fe der Gra­phent­hoerie han­delt, ist es eine Über­le­gung wert, diese in stär­ke­ren Lern­grup­pen ein­zu­füh­ren und eu­ler­sche von ha­mil­ton­schen Gra­phen ab­zu­gren­zen. Dazu bie­tet sich bei­spiels­wei­se fol­gen­de Auf­ga­be an4 :

Wel­che der Gra­phen sind eu­lersch, wel­che ha­mil­tonsch?

Abbildung Graph 6

„Ha­mil­tonsch und eu­lersch … sind zwei auf den ers­ten Blick ähn­li­che, aber ganz ver­schie­de­ne Ei­gen­schaf­ten. Na­tür­lich kann man auch bei einem ha­mil­ton­schen Gra­phen eine Kante nicht dop­pelt durch­lau­fen, weil man ja sonst durch die End-Ecken die­ser Kante zwei­mal käme.“5

Hin­wei­se zu den ein­zel­nen Auf­ga­ben:

  1. Ha­mil­ton-Krei­se

    Aus­ge­hend von der De­fi­ni­ti­on geht es in Auf­ga­be 1 zu­nächst um eine rein geo­me­tri­sche An­nä­he­rung an Ha­mil­ton­sche Kan­ten­zü­ge. Im b)- und d)-Teil wur­den zur Prä­zi­sie­rung Gra­phen ge­wählt, in denen Kan­ten­zü­ge exis­tie­ren, die jeden Kno­ten ent­hal­ten, aber nicht ge­schlos­sen sind. Dies kann bei der Aus­wer­tung des bin­nen­dif­fe­ren­ziert an­ge­leg­ten Zu­satz­auf­tra­ges the­ma­ti­siert wer­den.

  2. Be­wer­te­te Gra­phen

    Zur Ein­füh­rung wurde als Kon­text eine ein­fa­che Städ­te­tour ge­wählt und der be­wer­te­te Graph vor­ge­ge­ben6, um zügig zur Be­hand­lung eines ers­ten ein­fa­chen TSP zu ge­lan­gen.

  3. „TSP“ - Tra­vel­ling-Sa­les­man-Pro­blem

    Auch hier wurde ein ein­fa­ches TSP mit nur 4 Städ­ten ge­wählt, um den Fokus im Un­ter­richt nicht auf kom­bi­na­to­ri­sche Über­le­gun­gen zu set­zen. Fol­gen­der Hin­weis könn­te für Schü­le­rin­nen und Schü­ler in der Re­fle­xi­ons­pha­se in­ter­es­sant sein: Im Ge­gen­satz zu den leich­ter zu­gäng­li­chen Eu­ler­gra­phen ma­chen Ha­mil­ton­gra­phen den Ma­the­ma­ti­kern das Leben noch ziem­lich schwer. Es wurde noch kein ein­fa­cher Al­go­rith­mus ge­fun­den, mit dem man ent­schei­den kann, ob ein Ha­mil­ton­graph vor­liegt. In der Pra­xis in­ter­es­siert vor allem in be­wer­te­ten Gra­phen das Auf­fin­den des Ha­mil­tons­krei­ses mit nied­rigs­tem Wert mit ver­tret­ba­rem Re­chen­auf­wand. Eine Me­tho­de ist noch nicht be­kannt, ob­wohl viele Ma­the­ma­ti­ker mit Hoch­druck in die­sen Be­rei­chen for­schen. Das „TSP" ist mo­men­tan noch nicht ge­löst, es bleibt ein viel­leicht un­lös­ba­res Pro­blem. Die enor­me Menge an zu ver­glei­chen­den Ha­mil­ton­krei­sen macht dies ein­sich­tig: Wenn in einem voll­stän­di­gen Gra­phen mit n Kno­ten jeder Kno­ten mit jedem an­de­ren durch eine Kante ver­bun­den ist, so exis­tie­ren

    Abbildung Formel

    Ha­mil­ton­krei­se.

    Bei un­se­rem Ein­stiegs­bei­spiel waren es 3 Rou­ten (bzw. Ha­mil­ton­krei­se), die noch gut aus­ge­wer­tet wer­den kön­nen. Bei 5 Städ­ten sind es 12, bei 6 Städ­ten 60 Ha­mil­ton­krei­se. Bei 20 Städ­ten wären es un­glaub­li­che 1 216 451 004 088 320 000 Ha­mil­ton­krei­se ...7

  4. Iso­mor­phe Gra­phen

    Diese Auf­ga­be kann als ver­tie­fen­de Übung von allen Schü­le­rin­nen und Schü­lern be­ar­bei­tet wer­den. Sie dient als Puf­fer, gibt aber im Sinne der Dif­fe­ren­zie­rung auf dem Lö­sungs­blatt einen Aus­blick auf die „to­po­lo­gi­sche Äqui­va­lenz“ von Gra­phen. Wei­te­re klei­ne Auf­trä­ge zum „Um­zeich­nen“ der Ha­mil­ton­gra­phen auf dem Ar­beits­blatt könn­ten sich an­schlie­ßen.

    Auch der Rück­be­zug zum „Haus des Ni­ko­laus“ könn­te im Un­ter­richt auf­ge­grif­fen wer­den, indem Ver­for­mungs­schrit­te dis­ku­tiert und vi­sua­li­siert wer­den:

    Abbildung Graph 8

    So könn­te sich auch der „Kreis“ die­ser kur­zen Ein­füh­rung in die Gra­phen­theo­rie an die­ser Stel­le schlie­ßen.

    Für die an­schlie­ßen­de 4. Stun­de der Ein­heit wird die op­tio­na­le Be­hand­lung von Ad­ja­zenz­ma­tri­zen emp­foh­len, die in al­ters­an­ge­mes­ser Form als Nach­bar­schaft­s­ta­bel­len ein­ge­führt wer­den. Durch die nu­me­risch ba­sier­te Dar­stel­lung ver­schie­de­ner Gra­phen er­folgt dabei ein Per­spek­tiv­wech­sel, der ein ver­tief­tes Ver­stän­dis der Ei­gen­schaf­ten von Gra­phen er­mög­licht und da­durch den re­flek­tier­ten Um­gang mit Da­ten­struk­tu­ren im Be­reich der In­for­ma­tik un­ter­stützt.

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

5 a.a.O., statt „End-Ecken“ wird der Be­griff End­kno­ten emp­foh­len.

6 In An­leh­nung an das Bei­spiel im Ab­schitt „Eine bil­li­ge Rund­rei­se“, in Nitz­sche: „Gra­phen für Ein­stei­ger“, View­eg+Teub­ner, Wies­ba­den, 2009, 3. Auf­la­ge, S.52

7 A.a.O., S.53

 

 

4. Stun­de: Gra­phen als Ta­bel­len – Iso­mor­phie von Gra­phen

Ab­lauf und In­hal­te Hin­wei­se
  • Prä­sen­ta­ti­on der Haus­auf­ga­ben durch SuS, Er­läu­te­run­gen
  • Ko­gni­ti­ve Ak­ti­vie­rung mit Ta­fel­skiz­ze eines Gra­phen, evtl. auch dem Gra­phen auf dem AB: Was fällt euch an dem Gra­phen auf? Wie viele Eu­ler­sche Kan­ten­zü­ge ent­hält er? Fin­det ihr auch alle Ha­mil­ton­schen Krei­se?
  • Kon­zept der Nach­bar­schaft­s­ta­bel­le an die­sem Gra­phen an der Tafel ent­wi­ckeln, Fra­gen klä­ren, da­nach Ar­beits­blatt aus­tei­len mit Zu­sam­men­fas­sung
  • Auf­trag 1: EA /PA: Ad­ja­zenz­ta­bel­len er­stel­len (AB, Nr.1) in Stil­lar­beit Ta­bel­len aus­fül­len, dann in PA Zu­satz­auf­trag dis­ku­tie­ren, Prä­sen­ta­ti­on durch SuS, ggf. Kon­troll­fra­gen

  • Auf­trag 2: Iso­mor­phie cha­rak­te­ri­sie­ren (AB, Nr. 2)

    Ver­gleicht die drei Gra­phen rechts. Was genau ist gleich? Prä­sen­ta­ti­on durch SuS, Wei­ter­füh­rung: Dy­na­mi­sche Vi­sua­li­sie­rung mit Geo­Ge­bra

  • De­fi­ni­ti­on: Iso­mor­phie zwei­er Gra­phen
  • op­tio­nal: Ex­kurs zur Aus­sa­gen­lo­gik (vgl. Er­läu­te­run­gen)

  • Auf­trag 3: Ge­gen­bei­spie­le be­grün­den (AB, Nr. 2)

    Prä­sen­ta­ti­on durch SuS, ggf. Er­gän­zun­gen

  • Auf­trag 4: Graph zu Ta­bel­le er­fin­den (AB, Nr. 3)

    Prä­sen­ta­ti­on durch meh­re­re SuS.

  • Re­fle­xi­on Rück­schau zur Ver­net­zung der bei­den Dar­stel­lungs­for­men von Gra­phen (Bild, Ta­bel­le)

  • evtl. Übungs­auf­ga­ben aus Fun­dus, Haus­auf­ga­be
  • Ma­te­ri­al:

    AB Gra­phen als Ta­bel­le

    Übung Gra­phen als Ta­bel­le

  • Bin­nen­dif­fe­ren­zie­rung durch auf­trags­ge­steu­er­te Er­ar­bei­tung So­zi­al­form: EA/PA
  • zur Ak­ti­vie­rung wird ein klas­sen­spe­zi­fi­scher Bei­spiel­graph emp­foh­len, an dem das Kon­zept der Nach­bar­schaft­s­ta­bel­le ge­mein­sam ent­wi­ckelt wird. Das Bei­spiel auf dem AB kann dann zur Über­lei­tung ge­nutzt wer­den.
  • In der Wei­ter­füh­rung nach Auf­trag 2 kann die Iso­mor­phie mit der Datei 04_au­g_a­b_i­so­mor­phe_gra­phen.ggb dy­na­misch vi­sua­li­siert wer­den, siehe An­mer­kun­gen.
  • zu Auf­trag 3: Durch Be­grün­den der Nicht-Iso­mor­phie wer­den zen­tra­le Gra­phen­in­va­ri­an­ten in­tui­tiv er­fasst.
  • zu Auf­trag 4: Die In­ten­ti­on der Um­keh­rung der Auf­ga­ben­stel­lung ist in den Er­läu­te­run­gen be­schrie­ben.

Er­läu­te­run­gen

  1. Nach­bar­schaft­s­ta­bel­len und iso­mor­phe Gra­phen

    Vor­der­grün­dig geht es zu­nächst nur darum, das Kon­zept der Nach­bar­schaft­s­ta­bel­len zu ver­ste­hen und an 5 Bei­spie­len an­zu­wen­den. Gleich­zei­tig wird die Auf­ga­be aber auch zur Er­ar­bei­tung von Vor­stel­lun­gen zur Iso­mor­phie ge­nutzt. Für die schnel­le­ren SuS sind dazu Ent­de­ckun­gen mög­lich, die über den dif­fe­ren­zie­ren­den Zu­satz­auf­trag an­ge­regt wer­den.

    Hin­füh­rung zu einer al­ters­ge­rech­ten De­fi­ni­ti­on zur Iso­mor­phie von Gra­phen

    Nach den Prä­sen­ta­tio­nen der 5 Ta­bel­len schließt sich eine Wei­ter­füh­rungs­pha­se zur De­fi­ni­ti­on des Be­griffs iso­morph an. Geben Sie den Ent­de­ckun­gen der SuS hier Raum, wahr­schein­lich wer­den sie ei­gen­stän­dig auf die In­va­ri­anz zen­tra­ler Ei­gen­schaf­ten bei Ver­for­mung kom­men. Die Datei 04_au­g_a­b_i­so­mor­phe_gra­phen.ggb bie­tet die Mög­lich­keit, die Ver­for­mung der Gra­phen von Auf­ga­be 1 dy­na­misch zu vi­sua­li­sie­ren. Sie soll­te erst in der Zu­sam­men­füh­rungs­pha­se ein­ge­setzt wer­den, nach­dem die SuS ihre Sicht­wei­sen und Ideen ent­wi­ckeln konn­ten. Zur Wei­ter­füh­rung wird ab­schlie­ßend eine De­fi­ni­ti­on an der Tafel fest­ge­hal­ten, hier ein al­ters­an­ge­mes­sen re­du­zier­tes Bei­spiel: Alle für Gra­phen ty­pi­schen Ei­gen­schaf­ten wie An­zahl der Kno­ten, An­zahl der Kan­ten und Ord­nun­gen der Kno­ten müs­sen bei glei­cher Nach­bar­schafts­struk­tur über­ein­stim­men.

    Dazu kann man ggf. die Kno­ten eines der bei­den Gra­phen um­num­me­rie­ren bzw. um­be­nen­nen. Der As­pekt der Um­num­me­rie­rung kann, falls die SuS es noch nicht an­ge­spro­chen haben, durch die Ge­gen­über­stel­lung der Gra­phen d) und e) (bzw. c) und e)) er­ar­bei­tet wer­den.

    Die bei­den Gra­phen in c) und d) sind iso­morph zu­ein­an­der. Nur wenn die Be­zeich­nun­gen („label“) keine Rolle spie­len, sind sie auch iso­morph zum Gra­phen in e). Als ge­la­bel­te Gra­phen sind sie nicht iso­morph, da ihr „Nach­bar­schafts­ge­fü­ge“ nicht über­ein­stimmt.

    Zur Ab­run­dung könn­te man für Graph e) nach der ge­mein­sa­men Um­be­nen­nung der Kno­ten (Ver­tau­schen der Namen von A und D) er­neut eine Ta­bel­le er­stel­len las­sen, die dann iden­tisch zu den Nach­bar­schaft­s­ta­bel­len von c) und d) wäre.

    Abbildung Graph 9

    Zur Iso­mor­phie von Gra­phen könn­te man zuvor al­ters­an­ge­mes­sen fest­hal­ten: Die Datei 04_au­g_­ani­mier­te_­Um­for­mun­g_Haus_­de­s­_­Ni­ko­laus.ggb kann er­gän­zend oder al­ter­na­tiv ein­ge­setzt wer­den, um die Iso­mor­phie zwei­er Gra­phen aus­ge­hend vom be­kann­ten „Haus des Ni­ko­laus“ zu vi­sua­li­sie­ren.8

  2. Ver­tie­fung der De­fi­ni­ti­on

    Zur Un­ter­su­chung auf Iso­mor­phie be­trach­tet man so­ge­nann­te Gra­phen­in­va­ri­an­ten. So­bald eine zen­tra­le Ei­gen­schaft nicht über­ein­stimmt, kön­nen zwei Gra­phen nicht iso­morph sein. Im a), b) und c) -Teil reicht es aus, die of­fen­sicht­li­chen Ei­gen­schaf­ten Kno­ten- bzw. Kan­ten­an­zahl und Kno­ten­ord­nun­gen zu über­prü­fen. Im d) Teil reicht dies nicht, hier muss das Struk­tur­ge­fü­ge (der Zu­sam­men­hang zwi­schen den Kom­po­nen­ten) un­ter­sucht wer­den.

  3. Gra­phen zu vor­ge­ge­be­ner Ta­bel­le zeich­nen

    Die Um­keh­rung der Auf­ga­ben­stel­lung in Auf­ga­be 3 lie­fert aus di­dak­ti­scher Sicht den schö­nen Ne­ben­ef­fekt, dass die to­po­lo­gi­sche Äqui­va­lenz von Gra­phen und die zen­tra­le Be­deu­tung der Ma­tri­zen (bzw. in Klas­se 8 Ta­bel­len) wäh­rend der Be­ar­bei­tung in­tui­tiv er­fasst wer­den kön­nen. Durch den Dar­stel­lungs­wech­sel zwi­schen Bild und Ta­bel­le wird au­ßer­dem ein ver­tief­tes Ver­ständ­nis der be­reits ein­ge­führ­ten Be­grif­fe er­reicht. Ein wei­te­res Bei­spiel hier­zu fin­det sich bei den ver­tie­fen­den Übungs­auf­ga­ben (Nr. 2).

  4. Re­fle­xi­on – wei­te­re An­knüp­fungs­punk­te

    Pas­sen­de Fra­gen wur­den auf die­sem Ar­beits­blatt be­reits ein­ge­bun­den, soll­ten aber für die Lern­grup­pe mo­di­fi­ziert wer­den. An­de­re As­pek­te könn­ten eben­so in den Blick ge­nom­men und ver­tieft wer­den, z.B.:

    Woran er­kennt man einen iso­lier­ten Kno­ten?

    Warum ist diese Ta­bel­le sym­me­trisch zu einer ihrer Dia­go­na­len?

    Was ver­än­dert sich, wenn man zwei Kno­ten­na­men ver­tauscht?

    Wie viele und wel­che Ein­trä­ge müss­ten dann genau ge­tauscht wer­den?

    Wie sieht die Nach­bar­schaft­s­ta­bel­le eines voll­stän­di­gen Gra­phen aus?

8 Vgl. Er­läu­te­run­gen zur Iso­mor­phie von Gra­phen in der Datei 01_au­g_hin­ter­grund.odt auf Seite 6.

 

 

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

Un­ter­richts­ver­lauf: Her­un­ter­la­den [pdf][435 KB]

 

Wei­ter zu Aus­sa­gen­lo­gik