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

Euler-Kreis

Be­grif­fe: Graph, Kar­ten­graph, Kno­ten, Kante, Pfad, Zy­klus, Kreis, Zu­sam­men­hang, Brei­ten­su­che, Tie­fen­su­che

Als Ein­stieg in das Thema Gra­phen bie­tet es sich an, mit einem Bei­spiel zum Euler-Zug zu be­gin­nen. Der Euler-Kreis (Ach­tung: ei­gent­lich fal­sche Be­zeich­nung3 !) wurde schon in IMP in Klas­se 8 ein­ge­führt, bie­tet sich aber für eine ver­tief­te Be­hand­lung in der Kurs­stu­fe an. In Klas­se 8 wurde die Vor­aus­set­zung be­spro­chen, dass der Grad aller Kno­ten ge­ra­de sein muss, damit es einen ge­schlos­se­nen Euler-Zug gibt. Die zwei­te (of­fen­sicht­li­che) Be­din­gung, dass der Graph zu­sam­men­hän­gend sein muss, kann in der 8. Klas­sen­stu­fe nur schwer pro­ble­ma­ti­siert wer­den. In der Kurs­stu­fe wie­der­um kann genau dies den Ein­stieg in eine für die Im­ple­men­ta­ti­on eines Al­go­rith­mus not­wen­di­ge Sicht auf Gra­phen dar­stel­len. Die Schü­le­rin­nen und Schü­ler müs­sen sich in die Frosch­per­spek­ti­ve be­ge­ben: Nur we­ni­ge glo­ba­le Ei­gen­schaf­ten des Gra­phen (An­zahl Kno­ten, An­zahl Kan­ten) sind ver­füg­bar, an­sons­ten kann nur auf einen ein­zi­gen Kno­ten (ak­tu­el­ler Kno­ten) und seine Nach­barn zu­ge­grif­fen wer­den. In die­ser Sicht ist die Zu­sam­men­hang- Ei­gen­schaft eines Gra­phen alles an­de­re als of­fen­sicht­lich.

Eine Mög­lich­keit die­sen Zu­sam­men­hang zu tes­ten, be­steht darin per Tie­fen- oder Brei­ten­su­che alle von einem Kno­ten aus er­reich­ba­ren Kno­ten durch­zu­zäh­len und mit der Ge­samt­zahl der Kno­ten zu ver­glei­chen. Tie­fen- und Brei­ten­su­che soll­te den Schü­lern von Bäu­men be­kannt sein, wenn dies vor­her be­han­delt wurde. Die Er­wei­te­rung auf all­ge­mei­ne Gra­phen mit Zy­klen er­for­dert eine Mar­kie­rung der schon der ToDo-Liste hin­zu­ge­füg­ten und schon ab­ge­ar­bei­te­ten Kno­ten.

Der Un­ter­richt kann mit einem Ein­stiegs­bei­spiel (Schiffs­rou­ten - ko­pier­vor­la­gen/01_eu­l­er­zug.odt, Seite 1) star­ten. Bei die­sem ers­ten Bei­spiel soll­te die Mo­del­lie­rung des Pro­blems als Graph ge­mein­sam mit den Schü­le­rin­nen und Schü­lern durch­ge­führt wer­den (pra­e­sen­ta­ti­on/03_eu­l­er­zug.odp, Folie 2).

Die Be­griffs­bil­dung soll­te gleich von An­fang durch das An­le­gen eines Glos­sars (ko­pier­vor­la­gen/01_g­los­sar.odt) un­ter­stützt wer­den. Es ist wich­tig, den Wis­sens­vor­sprung durch den Be­such von IMP an die­ser Stel­le aus­zu­glei­chen, da das Thema Gra­phen im Brü­cken­kurs nicht vor­kommt und daher nicht allen Schü­le­rin­nen und Schü­lern die Be­grif­fe be­kannt sind. Alle Be­grif­fe sind in der Prä­sen­ta­ti­on pra­e­sen­ta­tio­nen/01_grund­be­grif­fe.odp er­läu­tert. Diese ist nicht als fort­lau­fen­de Prä­sen­ta­ti­on ge­dacht. Sie soll­ten die für ihren Un­ter­richt not­wen­di­gen Fo­li­en an den pas­sen­den Stel­len her­aus­su­chen. Die für das Ein­stiegs­bei­spiel "Schiffs­rou­ten" re­le­van­ten Be­grif­fe wer­den in der Prä­sen­ta­ti­on 03_eu­ler­kreis.odp auf den Fo­li­en 3-6 her­aus­ge­sucht.

Der Per­spek­tiv­wech­sel von der Adler- zur Frosch­per­spek­ti­ve ist bei der Über­prü­fung des Gra­des der Kno­ten ein­fach, da man oh­ne­hin jeden ein­zel­nen Kno­ten be­trach­ten muss (Folie 7). Beim Zu­sam­men­hang des Gra­phen (Folie 8) sind sie­ben Ab­bil­dun­gen vor­han­den, auf denen je einer der sie­ben Kno­ten fo­kus­siert und in Frosch­per­spek­ti­ve dar­ge­stellt ist. Hier ist nicht of­fen­sicht­lich, wie man nur mit die­sen Bil­dern fest­stel­len kann, ob der Graph zu­sam­men­hän­gend ist. Der Al­go­rith­mus kann nun auf die oben be­schrie­be­nen Wei­sen im Un­ter­richt er­ör­tert wer­den:

  • Selbst­ent­de­ckend: Die­Schü­ler­und­Schü­le­rin­nen­be­kom­men­eine­Lis­te­mit­Fä­hig­kei­ten des Froschs und müs­sen damit einen Al­go­rith­mus ent­wer­fen. Dabei reicht es nicht aus, die sie­ben Bil­der zu haben, da man nicht weiß, wel­ches Bild zu einem Nach­bar­kno­ten ge­hört. Daher kann hier ent­we­der die un­plug­ged-Ver­si­on oder der Ex­pe­ri­men­tier­mo­dus des Gra­phen-Tes­ters zum Ein­satz kom­men (03_zu­sam­men­han­g_bei­spiel1.csv und 04_zu­sam­men­han­g_bei­spiel2.csv).
  • Der Pseu­do­code oder die tex­tu­el­le Be­schrei­bung wird vor­ge­ge­ben und die Schü­ler voll­zie­hen das Ver­fah­ren un­plug­ged oder im Gra­phen­tes­ter nach. Bei­des kann auch als ge­stuf­te Hilfe ver­wen­det wer­den, wenn mit der selbst­ent­de­cken­den Va­ri­an­te ge­star­tet wird. (ko­pier­vor­la­gen/01_eu­ler­kreis.odt, Seite 4 und 5).
  • Die Schü­ler sol­len im Si­mu­la­ti­ons­mo­dus des Gra­phen­tes­ters den Al­go­rith­mus für Brei­ten- und/oder Tie­fen­su­che auf die Bei­spiel­da­tei­en an­wen­den, den Al­go­rith­mus be­schrei­ben und über­le­gen, wie man die­sen Al­go­rith­mus nut­zen kann, um her­aus­zu­fin­den, ob der Graph zu­sam­men­hän­gend ist. Das Hil­fe­fens­ter des Gra­phen­tes­ters kann schwä­che­ren Schü­lern bei der Be­schrei­bung hel­fen. Den Ab­schluss könn­te die Kom­men­tie­rung des Quell­tex­tes des Al­go­rith­mus bil­den. (ko­pier­vor­la­gen/ 01_eu­ler­kreis.odt, Seite 6).

Die fer­ti­ge Im­ple­men­ta­ti­on des Al­go­rith­mus zum Nach­weis der Exis­tenz eines Euler-Zuges soll­te als Ab­schluss der Stun­de ge­zeigt wer­den.

Wei­ter­füh­ren­de Fra­gen kön­nen Sie als Ver­tie­fung ein­set­zen und bei­spiels­wei­se auch als Haus­auf­ga­ben ver­wen­den.

GFS

Der Un­ter­richts­ent­wurf be­han­delt nur einen Al­go­rith­mus, um die Exis­tenz eines Euler-Zuges nach­zu­wei­sen. Damit ist noch nicht klar, wie der Euler-Zug ge­fun­den wer­den kann. Die Al­go­rith­men von Hier­hol­zer oder Fleu­ry lösen die­ses Pro­blem. Dies wäre eine mög­li­che Er­gän­zung, die sich gut für eine GFS eig­net:

 

3 Im all­ge­mei­nen Sprach­ge­brauch wird das Pro­blem des ge­schlos­se­nen Euler-Zuges oft als Euler-Kreis be­zeich­net, ob­wohl ein Kreis jeden Kno­ten nur ein­mal ent­hal­ten darf und in einem Euler-Zug im All­ge­mei­nen die Kno­ten mehr­fach be­sucht wer­den. Daher wird hier nur der Be­griff Euler-Zug ver­wen­det.

 

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

 

Wei­ter zu Pro­blem der to­po­lo­gi­schen Sor­tie­rung (op­tio­nal)