Pro­blem der to­po­lo­gi­schen Sor­tie­rung eines ge­rich­te­ten Graphs (op­tio­nal)

Be­grif­fe: ge­rich­te­te Kante, Zy­klus, Grad eines Kno­ten (Aus­gangs­grad, Ein­gangs­grad), Ab­hän­gig­keits­graph

Beim Euler-Kreis such­te man einen zy­kli­schen Pfad, der alle Kan­ten des Gra­phen um­fasst. Für viele an­de­re An­wen­dun­gen ist es aber auch schon in­ter­es­sant, ob es über­haupt einen Zy­klus gibt. Ein un­ge­rich­te­ter Graph ohne Zy­klen ist ein Baum, mit dem zum Bei­spiel Hier­ar­chi­en gut dar­ge­stellt wer­den kön­nen. In­ter­es­san­ter wird es, wenn man ge­rich­te­te Gra­phen ver­wen­det.

Bild­quel­le: Henne-Ei-Pro­blem: Ver­klem­mung bei to­po­lo­gi­scher Sor­tie­rung (ei­ge­ne Ab­bil­dung) ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt

Stellt man mit dem Gra­phen Ab­hän­gig­kei­ten von Ak­tio­nen dar (z.B. muss man zu­erst So­cken an­zie­hen, bevor man die Schu­he an­zieht), er­hält man einen Ab­hän­gig­keits­graph. Ent­hält der Graph keine Zy­klen, dann gibt es min­des­tens eine Rei­hen­fol­ge, in der man die Tä­tig­kei­ten durch­füh­ren muss, um alle Ab­hän­gig­kei­ten zu be­rück­sich­ti­gen. Man er­hält eine so­ge­nann­te to­po­lo­gi­sche Sor­tie­rung⁴ . Ent­hält der Graph Zy­klen, ist dies un­mög­lich, es ent­steht eine Ver­klem­mung, da für keine Ak­ti­on alle Vor­aus­set­zun­gen er­füllt sind. Re­le­vant ist dies z.B. beim Zu­griff auf Res­sour­cen von par­al­lel lau­fen­den Pro­zes­sen oder beim Ein­fü­gen in eine Da­ten­bank, bei der zu jedem Zeit­punkt die re­fe­ren­zi­el­le In­te­gri­tät ge­währ­leis­tet sein soll.

Diese Pro­blem­stel­lung stellt die Rich­tung einer Kante in den Vor­der­grund und führt eine neue In­ter­pre­ta­ti­on von Gra­phen (Ab­hän­gig­keits­graph) ein. Da ge­rich­te­te Kan­ten an an­de­ren Bei­spie­len deut­lich ge­macht wer­den kön­nen und Ab­hän­gig­keits­gra­phen nicht im Bil­dungs­plan ge­for­dert sind, kann diese An­wen­dung auch ent­fal­len. Es ist aber sinn­voll, wenn im Un­ter­richt nicht nur Kar­ten­gra­phen ein­ge­setzt wer­den, da dies die Viel­falt der An­wen­dungs­mög­lich­kei­ten nicht aus­rei­chend wie­der­gibt.

Ge­löst wird das Pro­blem, indem man bei jedem Kno­ten den Ein­gangs­grad als Wert ein­trägt. Wenn der Graph nicht zy­klisch ist, muss es min­des­tens einen Kno­ten geben, der den Wert 0 hat. Die­sen "ent­fernt" man aus dem Graph, d.h. man re­du­ziert die Werte aller von ihm ab­hän­gi­gen Kno­ten um 1. Da­durch muss es min­des­tens einen wei­te­ren Kno­ten mit Wert 0 geben. Dies wie­der­holt man, bis man alle Kno­ten ent­fernt hat. Die Rei­hen­fol­ge des Ent­fer­nens ist die to­po­lo­gi­sche Sor­tie­rung des Gra­phen.

Auch hier kön­nen Sie wie­der die ver­schie­de­nen Un­ter­richts­for­men zur Er­ar­bei­tung des Al­go­rith­mus ein­set­zen. Va­ri­ie­ren Sie die Un­ter­richts­form.

⁴ To­po­lo­gi­sche Sor­tie­rung be­zeich­net in der Ma­the­ma­tik eine Rei­hen­fol­ge von Din­gen, bei der vor­ge­ge­be­ne Ab­hän­gig­kei­ten er­füllt sind. Seite „To­po­lo­gi­sche Sor­tie­rung“. In: Wi­ki­pe­dia, Die freie En­zy­klo­pä­die. URL: https://​de.​wi­ki­pe­dia.​org/​w/​index.​php?​tit​le=Top​olog​isch​e_​Sor­tie­rung (ab­ge­ru­fen: 21. Sep­tem­ber 2020)

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

Wei­ter zu Pro­blem des kür­zes­ten Pfa­des in un­ge­wich­te­ten Gra­phen