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

Mi­ni­mal span­nen­de Bäume (mi­ni­mal span­ning tree)

Be­grif­fe: Mi­ni­ma­ler Spann­baum, ge­wich­te­ter Graph, Zu­sam­men­hangs­kom­po­nen­te

Der Bil­dungs­plan schreibt vor, einen Al­go­rith­mus zur Be­stim­mung eines mi­ni­mal span­ning trees zu be­han­deln (Krus­kal oder Prim). Es ist sinn­voll, die­sen Al­go­rith­mus am Ende der Ein­heit an­zu­sie­deln, da es sich bei den bei­den vor­ge­schla­ge­nen Al­go­rith­men um Gree­dy-Al­go­rith­men han­delt, die aber im Ge­gen­satz zu den an­de­ren Gree­dy-Al­go­rith­men keine Nä­he­rungs­lö­sung, son­dern die op­ti­ma­le Lö­sung lie­fern. Damit wird die Ein­heit zu den Gra­phen ab­ge­run­det.

Zu bei­den Al­go­rith­men gibt es im In­ter­net jede Menge Vi­de­os und Er­klä­run­gen. Al­ler­dings sind diese Be­schrei­bun­gen un­ge­nau oder nicht so leicht in Code um­zu­set­zen:

Krus­kal:

Hier wird meis­tens la­pi­dar ge­sagt, dass eine Kante nicht hin­zu­ge­fügt wer­den darf, wenn da­durch der Graph einen Zy­klus be­kommt. Das ist in der Ad­ler­per­spek­ti­ve leicht zu er­ken­nen, in der Frosch­per­spek­ti­ve aber nicht. Daher ist es bei der Im­ple­men­tie­rung nicht so ein­fach, einen Zy­klus zu er­ken­nen. Dazu müss­te man jedes Mal eine Tie­fen- oder Brei­ten­su­che durch­füh­ren.

Al­ter­na­tiv kann man die Kno­ten ein­fär­ben und diese Far­ben nut­zen, um zu er­ken­nen, ob ein Zy­klus vor­liegt. Jede Zu­sam­men­hangs­kom­po­nen­te des neu ent­ste­hen­den mi­ni­mal span­ning trees (wäh­rend der Aus­füh­rung des Al­go­rith­mus ist es noch ein Wald) be­kommt eine ei­ge­ne Farbe. Ist der ganze Graph in einer Farbe ein­ge­färbt, ist der mi­ni­mal span­ning tree ge­fun­den. Die Kno­ten wer­den nach ein­fa­chen Re­geln (siehe Auf­ga­ben­blatt) ein­ge­färbt. Beim Zu­sam­men­füh­ren zwei­er Zu­sam­men­hangs­kom­po­nen­ten wer­den alle Kno­ten der zwei­ten Kom­po­nen­te mit der Farbe der ers­ten Kom­po­nen­te ein­ge­färbt. Dies kann man ent­we­der mit Tie­fen- oder Brei­ten­su­che oder mit einer Schlei­fe über alle Kno­ten, bei der jeder Kno­ten einer be­stimm­ten Farbe um­ge­färbt wird, be­werk­stel­li­gen. Au­ßer­dem wird durch das Ein­fär­ben der Zu­sam­men­hangs­kom­po­nen­ten die grund­sätz­li­che Ar­beits­wei­se des Al­go­rith­mus bes­ser sicht­bar.

Ein Gree­dy-Al­go­rith­mus ist der Krus­kal-Al­go­rith­mus, da in jedem Schritt die güns­tigs­te Kante aus­ge­wählt wird, die nicht zu einem Zy­klus führt.

Prim (ge­spro­chen wie "Primm"):

Bei die­sem Al­go­rith­mus wird in der Li­te­ra­tur oft mit Schnit­ten durch den Graph ar­gu­men­tiert. Man müss­te also erst mal klä­ren, was ein Schnitt über­haupt ist. Dar­auf kann man aber auch ver­zich­ten. Wich­tig ist nur, dass man nicht wie bei Krus­kal viele ein­zel­ne Teil­bäu­me all­mäh­lich zu einem Baum zu­sam­men­führt, son­dern hier einen Baum suk­zes­si­ve er­wei­tert. Diese Er­wei­te­rung er­folgt durch Hin­zu­fü­gen der kür­zes­ten Kante, die einen Kno­ten aus dem bis­he­ri­gen Baum mit einem Kno­ten aus dem rest­li­chen Gra­phen ver­bin­det. Diese Auf­tei­lung in zwei (nicht leere) Kno­ten­men­gen heißt Schnitt. Die­ser Schnitt wird für den Be­weis der Kor­rekt­heit be­nö­tigt, der in der Schu­le aber keine Rolle spielt.

Mar­kiert man jeden Kno­ten, den man dem Baum hin­zu­fügt, sucht man also die kür­zes­te Kante, bei der genau einer der an­lie­gen­den Kno­ten mar­kiert ist. Da auch hier immer die kür­zes­te Kante ge­wählt wird, ist auch Prim ein Gree­dy-Al­go­rith­mus.

Zur Er­ar­bei­tung eines der Al­go­rith­men könn­te man die Schü­le­rin­nen und Schü­ler gut mit dem Gra­phen­tes­ter den fer­ti­gen Al­go­rith­men un­ter­su­chen und ihn be­schrei­ben las­sen. Das Hil­fe­fens­ter des Gra­phen­tes­ters bie­tet dabei zu­sätz­li­che Un­ter­stüt­zung. Dann wen­den die Schü­le­rin­nen und Schü­ler den Al­go­rith­mus auf einen wei­te­ren Gra­phen an, um ihr Ver­ständ­nis zu fes­ti­gen.

Zur Er­fül­lung des Bil­dungs­plans reicht es dabei, einen der bei­den Al­go­rith­men zu un­ter­su­chen. Schnel­le Schü­le­rin­nen und Schü­ler kön­nen aber auch beide Al­go­rith­men ana­ly­sie­ren. Eine schö­ne Er­gän­zung bie­tet der Bezug zum Tra­ve­ling Sa­les­man Pro­blem, da beide Al­go­rith­men nur leicht ver­än­dert wer­den müs­sen (siehe Hin­ter­grund.odt), um als Nä­he­rungs­al­go­rith­mus für das TSP zu die­nen.

 

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

 

Wei­ter zu Wei­te­re Übun­gen