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

Aus­ge­wähl­te Gra­phen-Al­go­rith­men

Zy­klen­su­che

Um Zy­klen in Gra­phen zu fin­den, kann man Tie­fen- oder Brei­ten­su­che ver­wen­den. Ent­hält der Graph kei­nen Zy­klus, ist es ein Baum.

Ab­bil­dung 12: Zy­klen­su­che durch Brei­ten­su­che

Ab­bil­dung 13: Zy­klen­su­che durch Tie­fen­su­che

ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 1_gra­phen_hin­ter­grund.odt

Al­ter­na­tiv kann man auch eine re­kur­si­ve Im­ple­men­tie­rung wäh­len.

Zu­sam­men­hang eines Gra­phen:

Mit Tie­fen- oder Brei­ten­su­che lässt sich die An­zahl der er­reich­ba­ren Kno­ten in einem Gra­phen be­stim­men und durch Ver­gleich mit der Ge­samt­zahl der Kno­ten er­ken­nen, ob ein Graph zu­sam­men­hän­gend ist.

Euler-Zug

Ge­sucht ist ein ge­schlos­se­ner Kan­ten­zug im Gra­phen, so dass jede Kante genau ein­mal be­nutzt wird. Fälsch­li­cher­wei­se wird der Euler-Zug oft als Euler-Kreis be­zeich­net. Al­ler­dings darf in einem Kreis laut De­fi­ni­ti­on jeder Kno­ten nur ein­mal be­sucht wer­den. Beim "Euler-Kreis" al­ler­dings mehr­fach. Damit muss man ihn als kor­rek­ter­wei­se als ge­schlos­se­nen Euler-Zug oder Euler-Zy­klus be­zeich­nen.

Dies ist mög­lich, wenn der Graph zu­sam­men­hän­gend ist und der Grad jedes Kno­ten ge­ra­de ist. Damit ist die Exis­tenz nach­ge­wie­sen, aber noch nicht klar, wie der Kan­ten­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. Da dies aber nicht im Bil­dungs­plan vor­kommt, wird hier nur auf zwei Vi­de­os ver­wie­sen.

An­wen­dung Brief­trä­ger­pro­blem:

Im Ge­gen­satz zum Hand­lungs­rei­sen­den, der jede Stadt (Kno­ten) ein­mal be­su­chen soll, muss der Brief­trä­ger jede Stra­ße ein­mal ab­lau­fen, um die Brie­fe aus­zu­lie­fern. Dabei soll­te jede Stra­ße nur ein­mal be­nutzt wer­den. Das gilt ge­nau­so für Rou­ten der Müll­ab­fuhr oder Stra­ßen­rei­ni­gung.

We­ge­fin­de-Al­go­rith­men

Moo­res-Al­go­rith­mus A

Fin­den kür­zes­ter Wege in un­ge­wich­te­ten Gra­phen: Mit dem Al­go­rith­mus A von Ed­ward Moore wird per Brei­ten­su­che die Ent­fer­nung eines Kno­ten zu allen an­de­ren be­stimmt, indem man aus­ge­hen­de vom Start­kno­ten (Ent­fer­nung 0) bei jedem noch nicht be­such­ten Nach­bar­kno­ten als Ent­fer­nung die ei­ge­ne Ent­fer­nung+1 ein­trägt. Die neu be­such­ten Kno­ten wer­den in die ToDo- Liste der Brei­ten­su­che ein­ge­tra­gen.

Di­jk­s­tra - Al­go­rith­mus

Der Di­jk­s­tra-Al­go­rith­mus wurde schon in IMP in Klas­se 9 (siehe Hin­ter­grund dort) er­läu­tert. Eine gut ver­ständ­li­che Er­läu­te­rung fin­den Sie auch unter https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​di­jk­s­tra/​in­dex_​de.​html (Ab­ge­ru­fen 04.11.2020).

Bell­man-Ford - Al­go­rith­mus

Der Bell­man-Ford-Al­go­rith­mus geht ähn­lich vor wie der Di­jk­s­tra Al­go­rith­mus. Er ist unter https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​bell­man-​ford/​in­dex_​de.​html (Ab­ge­ru­fen: Nov. 2020) gut er­klärt. Wenn vom Start­kno­ten zu einem Kno­ten A ein Pfad ge­fun­den wurde, wird bei jedem Nach­bar­kno­ten N kon­trol­liert, ob der Weg über A zu N kür­zer ist als der bis­her kür­zes­te Weg zu N. Im Ge­gen­satz zum Di­jk­s­tra-Al­go­rith­mus ver­sucht man dabei nicht, die Be­ar­bei­tungs- rei­hen­fol­ge der Kno­ten so zu wäh­len, dass ein schon be­ar­bei­te­ter Kno­ten nicht er­neut un­ter­sucht wer­den muss. Statt­des­sen wer­den so viele Be­ar­bei­tungs­durch­gän­ge durch­ge­führt, dass nach­träg­li­che Än­de­run­gen an einem Kno­ten er­neut an alle Fol­ge­kno­ten wei­ter­ge­ge­ben wer­den kön­nen. In einem Durch­gang wird dabei jede Kante ein­mal be­trach­tet. Daher ver­wen­det man eine Schlei­fe über alle Kan­ten statt einer Schlei­fe über alle Kno­ten.

Wählt man als An­zahl der Durch­gän­ge die Kno­ten­zahl des Gra­phen, stellt man si­cher, dass der kür­zes­te Weg zu jedem Kno­ten ge­fun­den wurde. Im un­güns­tigs­ten Fall ver­läuft der längs­te kür­zes­te Weg zu einem Kno­ten über alle an­de­ren Kno­ten. Mehr Zwi­schen­schrit­te sind nicht

Gra­phen mit ne­ga­ti­ven Kan­ten­ge­wich­ten: Der erste Graph ist nicht zu­läs­sig, da der rot mar­kier­te Kreis das Ge­wicht -1 hat. (ei­ge­nes Werk)

ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 1_gra­phen_hin­ter­grund.odt

mög­lich, da es im Nor­mal­fall nicht sinn­voll ist, einen Zy­klus (mehr­fach) zu durch­lau­fen. Nur bei Zy­klen, die ein ne­ga­ti­ves Kan­ten­ge­wicht haben, würde sich die Ge­samt­stre­cke durch den Zy­klus ver­kür­zen. Es würde sich loh­nen, den Zy­klus immer wie­der zu durch­lau­fen. Daher er­kennt man diese (ver­bo­te­nen) Zy­klen daran, dass ein wei­te­rer Durch­gang nach Be­en­di­gung des Al­go­rith­mus eine wei­te­re Ver­bes­se­rung der Wege brin­gen würde. Ein­zel­ne Kan­ten mit ne­ga­ti­ven Kan­ten­ge­wich­ten sind bei Bell­man-Ford er­laubt.

Dis­tanz-Vek­tor-Ver­fah­ren (Dy­na­mi­sches Rou­ting)

Die Lauf­zeit des Bell­man-Ford-Al­go­rith­mus ist schlech­ter als die des Di­jk­s­tra-Al­go­rith­mus. Seine große Stär­ke liegt aber darin, dass er auch funk­tio­niert, wenn man jeden Kno­ten als ei­gen­stän­di­gen Ak­teur be­trach­tet, der mit sei­nen Nach­bar­kno­ten kom­mu­ni­zie­ren kann. Er fragt seine Nach­barn immer wie­der nach deren Ent­fer­nung zu Start­kno­ten und passt seine ei­ge­ne Ent­fer­nung ge­ge­be­nen­falls an. Ma­chen das alle Kno­ten, stellt sich nach einer ge­wis­sen Zeit ein sta­bi­ler Zu­stand ein, in dem die kür­zes­ten Ent­fer­nun­gen vom bzw. zum Start­kno­ten be­kannt sind. Die Ge­samt­struk­tur des Gra­phen muss dazu nicht be­kannt sein. Jeder Kno­ten muss nur seine Nach­bar­kno­ten ken­nen.

Statt nur die Ent­fer­nung zu einem (Start)kno­ten ab­zu­fra­gen, kann man auch die Ent­fer­nun­gen zu allen Kno­ten ab­fra­gen. Das Rou­ting im In­ter­net funk­tio­niert nach die­sem Sys­tem. Hier tau­schen die Rou­ter In­for­ma­tio­nen über den Zeit­be­darf zu den Ziel-IP-Adres­sen aus und be­stim­men damit die güns­tigs­ten Rou­ting-Stre­cken.

Jeder Rech­ner/Rou­ter (Kno­ten des Gra­phen) kennt zu­nächst nur die Dis­tanz zu sei­nen un­mit­tel­ba­ren Nach­barn. Die Dis­tanz (Ge­wicht der Kante) ist ein be­stimm­tes Maß (=Me­trik):

  • die Pa­ket­ver­zö­ge­rung beim Trans­port (beim Pro­to­koll Hello)
  • die An­zahl der Hops (beim Pro­to­koll RIP – Rou­ting In­for­ma­ti­on Pro­to­col). Die An­zahl Hops gibt an, wie viele Rou­ter sich zwi­schen Ur­sprungs- und Ziel­rech­ner be­fin­den.

Wir wäh­len bei un­se­ren wei­te­ren Über­le­gun­gen die Ver­zö­ge­rung als Maß für die Dis­tanz. Jeder Rou­ter misst nun re­gel­mä­ßig die Zeit, die ein Paket braucht, um zu sei­nen Nach­barn und zu­rück zu ge­lan­gen. Diese Zei­ten hält er in einer Rou­ting­ta­bel­le fest.

In re­gel­mä­ßi­gen Ab­stän­den tau­schen die Nach­barn ihre Rou­ting­ta­bel­len aus (im AR­PA­net waren es 625ms), in denen steht, in wel­cher Zeit ir­gend­ein Ziel er­reicht wer­den kann. Aus den er­hal­te­nen Ta­bel­len wird eine neue Rou­ting­ta­bel­le mit wei­te­ren Zie­len und an­ge­pass­ten Wer­ten für den Zeit­be­darf be­rech­net.

Ziel Netz­mas­ke Gate­way Schnitt­stel­le Me­trik
92.​221.​2.​14 255.​255.​255.​255 127.​0.​0.​1 127.​0.​0.​1 0ms
10.​1.​1.​17 255.​255.​255.​255 127.​0.​0.​1 127.​0.​0.​1 0ms
92.​221.​2.​0 255.​255.​255.​0 92.​221.​2.​14 92.​221.​2.​14 1ms
10.​1.​0.​0 255.​255.​0.​0 10.​1.​1.​17 10.​1.​1.​17 1ms
0.​0.​0.​0 0.​0.​0.​0 10.​1.​1.​18 10.​1.​1.​17 3ms

Diese Ta­bel­le ist so zu lesen, dass die Da­ten­pa­ke­te an die Adres­sen 92.​221.​2.​14 und 10.​1.​1.​17 – also die ei­ge­nen IP-Adres­sen – an sich selbst wei­ter­ge­lei­tet wer­den müs­sen. Die IP-Adres­se 127.​0.​0.​1 kenn­zeich­net grund­sätz­lich den ei­ge­nen Rech­ner (lo­cal­host). Die Da­ten­pa­ke­te an alle IP-Adres­sen, die die Netz-ID 92.​221.​2.​0 und Netz­mas­ke 255.​255.​255.​0 haben, wer­den über die Schnitt­stel­le 92.​221.​2.​14 in das Netz 92.221.2.x wei­ter­ge­lei­tet. Ent­spre­chen­des gilt für Netz 10.1.x.x. Alle an­de­ren Ver­bin­dun­gen (Ziel 0.​0.​0.​0 / Sub­net 0.​0.​0.​0) wür­den an den nächs­ten Rou­ter mit der IP 10.​1.​1.​18 über die Schnitt­stel­le 10.​1.​1.​17 wei­ter­ge­ge­ben.

Be­trach­ten wir den Ab­lauf des Rou­ting­al­go­rith­mus in einem klei­nen Netz­werk mit den Rou­tern A, B, C und D. Wenn die Rou­ter ein­ge­schal­tet wer­den, so ken­nen sie nur die Dis­tanz zu ihren Nach­barn. Die Rou­ting­ta­bel­le hätte die fol­gen­de Form:

Im Fol­gen­den ist dar­ge­stellt, wie In­for­ma­tio­nen der Nach­barn die Rou­ting­ta­bel­le von A ver­än­dern. Dazu schi­cken die Nach­barn von A In­for­ma­tio­nen über ihre Rou­ting­ta­bel­len (= Dis­tanz­vek­tor).

Rou­ter B lie­fert z.B. (A = 2; B = 0; C = 1). A ad­diert die Dis­tanz zum Rou­ter B (Ent­fer­nung A-B ist hier 2) hinzu und er­hält damit die Ge­sam­tent­fer­nung um die an­de­ren Kno­ten zu er­rei­chen, wenn der Rou­ter B be­nutzt würde. Die Ent­fer­nung von A nach C über B ist also bei­spiels­wei­se die Summe aus der Ent­fer­nung A-B (=2) plus die Ent­fer­nung von B zu C (=1), also ins­ge­samt 3.

Am Ende wählt der Rou­ter A den­je­ni­gen Weg, der die kür­zes­te Dis­tanz zum Ziel lie­fert. In die­sem Bei­spiel ist der di­rek­te Weg von A nach C 4 Ein­hei­ten weit weg. Über Rou­ter B sind es 3 Ein­hei­ten. Daher wird der Rou­ting­ta­bel­len­ein­trag für Ziel C ge­än­dert. Statt des di­rek­ten Weges (4/C) wird der kür­ze­re „Umweg“ über B ver­wen­det (3/B). Für die an­de­ren Ziele wer­den ent­spre­chend die kür­zes­ten Wege be­stimmt. Man er­hält eine neue Rou­ting­ta­bel­le.

Wer­den die Rou­ting­ta­bel­len immer wie­der an die Nach­barn über­tra­gen, so stellt sich nach ei­ni­ger Zeit ein „sta­bi­ler Zu­stand“ ein, d.h. die Rou­ting­ta­bel­len än­dern sich nicht mehr. Hier­mit ist das Grund­prin­zip des Bell­man-Ford-Al­go­rith­mus um­ge­setzt.

In der Pra­xis ist das Ver­fah­ren ein wenig kom­pli­zier­ter, da bei die­sem Ver­fah­ren erst nach mehr­fa­chem Aus­tausch der Ta­bel­len ein sta­bi­ler Zu­stand im Netz er­reicht wird. Da­zwi­schen kann es auch pas­sie­ren, dass eine Rou­ting­schlei­fe ent­steht. Diese führt dazu, dass Da­ten­pa­ke­te immer im Kreis ge­schickt wer­den und diese Lei­tun­gen dann schnell ver­stop­fen. Um dies zu ver­hin­dern, hat man eine Time To Live (TTL) ein­ge­führt, die fest­legt, nach wie vie­len Hops das Paket ge­löscht wird. So kreist ein Paket nicht für immer und ewig.

In mo­der­nen Rou­ting-Pro­to­kol­len (BGP – Bor­der Gate­way Pro­to­col) wer­den sol­che Rou­ting­schlei­fen von vorn­her­ein ver­hin­dert. Trotz­dem ar­bei­tet das BGP im Prin­zip nach dem Dis­tanz-Vek­tor-Ver­fah­ren. Es gibt aber auch an­de­re Rou­ting­al­go­rith­men, die wie bei einem Rou­ten­pla­ner, die Ent­fer­nung zu allen Zie­len z.B. mit dem Di­jk­s­tra-Al­go­rith­mus selbst­stän­dig be­rech­nen (Link-State-Ver­fah­ren).

Un­ver­träg­lich­keits­gra­phen: Ko­lo­rie­rung von Gra­phen

Greedy-Algorithmus beim Problem des Handlungsreisenden, Start in Ulm, Zwischenstand nach 15 Schritten

Deutsch­land­kar­te_(Bunt).svg: Ste­fan-Xp [CC BY-SA 3.0], via Wi­ki­me­dia Com­mons

Ab­bil­dung 14: Bun­des­län­der in Deutsch­land

Land­kar­ten wer­den nor­ma­ler­wei­se ko­lo­riert, um ein­zel­ne Ge­bie­te gut un­ter­schei­den zu kön­nen. Dabei dür­fen be­nach­bar­te Ge­bie­te nicht in der­sel­ben Farbe ge­färbt wer­den. Die Ge­bie­te kön­nen als Kno­ten eines un­ge­rich­te­ten, un­ge­wich­te­ten Gra­phen mo- del­liert wer­den, eine Kante zwi­schen zwei Kno­ten zeigt, dass die Re­gio­nen eine ge­mein­sa­me Gren­ze haben. Die ge­naue Lage der Ge­bie­te und der Ver­lauf der Gren­zen spielt keine Rolle.

Der Graph ist damit ein Un­ver­träg­lich­keits- graph. Eine Kante drückt aus, dass die glei­che Farbe für die Kno­ten ver­bo­ten ist.

Das Kar­ten­fär­be­pro­blem und damit auch alle an­de­ren An­wen­dungs­si­tua­tio­nen, die mit einem Un­ver­träg­lich­keits­graph dar­ge­stellt wer­den kön­nen, kön­nen daher fol­gen­der­ma­ßen in ein Gra­phen-Fär­be­pro­blem um­for­mu­liert wer­den:

 

Graph Co­lo­ring Pro­blem

Finde eine Fär­bung der Kno­ten eines Gra­phen mit mög­lichst we­ni­gen Far­ben, so dass be­nach­bar­te Kno­ten nicht die glei­che Farbe haben.

Als Va­ri­an­te kann man auch ent­we­der nur da­nach fra­gen, wie viele Far­ben be­nö­tigt wer­den oder ob es zu einer be­stimm­ten An­zahl von Far­ben eine Fär­bung gibt.

Für Gra­phen von Land­kar­ten ist be­kannt, dass immer eine Fär­bung mit ma­xi­mal vier Far­ben mög­lich ist. Dies liegt daran, dass der da­zu­ge­hö­ri­ge Graph auf jeden Fall pla­nar ist.

Eine Va­ri­an­te des Pro­blems der Kar­ten­ko­lo­rie­rung stellt die Er­wei­te­rung um Ko­lo­ni­en dar: Mut­ter­staat und Ko­lo­nie sol­len die­sel­be Farbe haben. Die Ko­lo­ni­en und der da­zu­ge­hö­ri­ge Mut­ter­staat wer­den dabei als ein ein­zi­ger Kno­ten mo­del­liert, um si­cher­zu­stel­len, dass sie die glei­che Farbe be­kom­men. Die Kan­ten be­hal­ten ihre Be­deu­tung. Der da­zu­ge­hö­ri­ge Graph ist im All­ge­mei­nen nicht mehr pla­nar. Für die­ses Pro­blem ist keine all­ge­mein gül­ti­ge obere Schran­ke für die mi­ni­ma­le An­zahl der Far­ben be­kannt.

Gra­phen, die sich mit einer Farbe fär­ben las­sen, haben keine Kante. Ein bi­par­ti­ter Graph lässt sich mit zwei Far­ben fär­ben. Ein voll­stän­di­ger Graph mit n Kno­ten be­nö­tigt n Far­ben, ein Graph mit einer Cli­que aus m Kno­ten min­des­tens m Far­ben.

Al­go­rith­men

Das Graph-Ko­lo­rie­rungs­pro­blem ist im All­ge­mei­nen ein NP-voll­stän­di­ges Pro­blem. Daher kann man es ver­mut­lich nicht ef­fi­zi­ent op­ti­mal lösen. Back­tracking würde eine op­ti­ma­le Lö­sung ga­ran­tie­ren. Die An­zahl der Far­ben würde man bei n Kno­ten auf n fest­le­gen, da dies auf jeden Fall aus­reicht. Dann wür­den die Kno­ten re­kur­siv ab­ge­ar­bei­tet und für jeden Kno­ten alle Far­ben pro­biert. Die beste Lö­sung merkt man sich.

Als ef­fi­zi­en­tes Nä­he­rungs­ver­fah­ren steht ein Gree­dy-Al­go­rith­mus zur Ver­fü­gung. Schritt­wei­se wer­den die Kno­ten einer nach dem an­de­ren be­trach­tet und je­weils der Kno­ten so mit einer Farbe der höchs­ten Prio­ri­tät (diese wurde zuvor fest­ge­legt) ge­färbt, dass die Färbe-Regel nicht ver­letzt wird.

Graph-Co­lo­ring-Ap­pro­xi­ma­ti­ons­al­go­rith­mus (Gree­dy):

  1. Lege eine Farb-Prio­ri­täts­lis­te fest: 1. Farbe, 2. Farbe, 3. Farbe, …
  2. Be­trach­te der Rei­hen­fol­ge nach alle n Kno­ten → u sei der be­trach­te­te Kno­ten:
Färbe u mit der Farbe, die in der Prio­ri­täts­lis­te am höchs­ten ist und mit der noch kein ad­ja­zen­ter Kno­ten zu u ge­färbt ist.

 

Die Güte die­ses Al­go­rith­mus ist sehr schlecht. Beim einem bi­par­ti­ten Graph, bei dem jeder Kno­ten mit allen Kno­ten der an­de­ren Teil­men­ge ver­bun­den ist außer sei­nem di­rek­ten Ge­gen­über, be­nö­tigt der Al­go­rith­mus n/2 Far­ben, wenn man die Kno­ten in un­güns­ti­ger Rei­hen­fol­ge (siehe Num­me­rie­rung der Kno­ten) ab­ar­bei­tet, ob­wohl ei­gent­lich 2 Far­ben aus­rei­chen17 .

Bearbeitungsreihenfolge

Die Be­ar­bei­tungs­rei­hen­fol­ge (0->7) führt dazu, dass die gegenüber­liegenden Kno­ten immer in der glei­chen Farbe ge­färbt wer­den und diese Farbe für alle an­de­ren Kno­ten ver­bo­ten ist. ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 01_hin­ter­grund.pdf, be­ar­bei­tet

Quel­len

Er­klär­vi­deo zur Gra­ph­Co­lo­ring https://​www.​youtube.​com/​watch?​v=4FE79y_​JkCE

Er­klär­vi­deo Four Color Pro­blem: https://​www.​youtube.​com/​watch?​v=9-​ImS­Bdxx3k

Er­klär­vi­deo The Four Color Theo­rem: https://​www.​youtube.​com/​watch?​v=Ngb​K43j​B4rQ

Wi­ki­pe­dia: Fär­bung https://​de.​wi­ki­pe­dia.​org/​wiki/​Fär­bun­g_(Gra­phen­theo­rie)

CSUn­plug­ged: Graph Co­lou­ring – The Poor Car­to­gra­pher. URL: http://​csun­plug­ged.​org/​graph-​co­lou­ring/

Gro­ßer et al: Das Vier­far­ben­pro­blem – "mehr als Malen nach Zah­len". Ma­the­Pris­ma. URL: http://​ma­the­pris­ma.​de/​Mo­du­le/​4FP/​index.​htm

Com­pu­ting Sci­ence In­si­de: Graph Co­lo­ring. Uni­ver­si­ty of Glas­gow. URL: http://​csi.​dcs.​gla.​ac.​uk/​work­shop-​view.​php?​work­sho­pID=6

Mi­ni­ma­le Do­mi­nie­ren­de Menge (Mi­ni­mal Do­mi­na­ting Set - MDS)

In der Gra­phen­theo­rie ist eine Do­mi­nie­ren­de Menge eines Gra­phen eine Teil­men­ge, für die gilt, dass jeder Kno­ten, der nicht in D ent­hal­ten ist, ad­ja­zent zu min­des­tens einem Kno­ten aus D ist.

Die Do­mi­na­ti­ons­zahl ist die An­zahl Kno­ten in einer mi­ni­ma­len Do­mi­nie­ren­den Menge für G.

Das Do­mi­na­ting Set Pro­blem be­trifft die Frage, ob die Do­mi­na­ti­ons­zahl für einen ge­ge­be­nen Gra­phen G und höchs­tens k ist, wobei k in der Pro­blem­stel­lung fest­ge­legt wird. Dies ist ein über­ra­schend schwe­res Pro­blem. Es ist ein klas­si­sches NP-voll­stän­di­ges Entscheidungs­problem in der Kom­ple­xi­täts­theo­rie (Garey & John­son 1979). Daher kann man davon aus­ge­hen, dass es kei­nen ef­fi­zi­en­ten Al­go­rith­mus gibt, der eine Mi­ni­ma­le Do­mi­nie­ren­de Menge für einen vor­ge­ge­be­nen Gra­phen fin­det.

[Über­setzt aus Wi­ki­pe­dia: https://​en.​wi­ki­pe­dia.​org/​wiki/​Do­mi­na­tin­g_​set ]

Al­go­rith­mus

Auch hier bie­tet es sich an, für eine op­ti­ma­le Lö­sung mit Back­tracking an das Pro­blem her­an­zu­ge­hen. Jeder Kno­ten kann zur do­mi­nie­ren­den Menge da­zu­ge­hö­ren oder nicht. Damit gibt es zwei Mög­lich­kei­ten, die beim Back­tracking ge­tes­tet wer­den müs­sen. Die kleins­te ge­fun­de­ne do­mi­nie­ren­de Menge wird ge­spei­chert.

Gree­dy-Nä­he­rungs­lö­sung: Man un­ter­sucht alle bis­her noch nicht über­deck­ten Kno­ten und be­stimmt die An­zahl der Kno­ten, die von dem je­wei­li­gen Kno­ten über­deckt wür­den. Dann wählt man den­je­ni­gen Kno­ten aus, der die meis­ten Kno­ten über­deckt. In der Pra­xis ist es sinn­voll zu mar­kie­ren, wel­che Kno­ten schon über­deckt sind, damit nicht jedes Mal alle Nach­barn dar­auf ge­tes­tet wer­den müs­sen, ob sie zur do­mi­nie­ren­den Menge ge­hö­ren.

Lo­ka­le Suche: Man wählt zu­nächst zu­fäl­lig so lange neue Kno­ten aus und fügt sie der do­mi­nie­ren­den Menge hinzu, bis alle Kno­ten über­deckt sind. Da­nach über­prüft man, ob es Kno­ten gibt, die aus der do­mi­nie­ren­den Menge ent­fernt wer­den kön­nen.

Ge­ne­tisch: Man ge­ne­riert In­di­vi­du­en zu­nächst als zu­fäl­li­ge Teil­men­gen der Kno­ten­men­ge. Dabei müs­sen diese nicht not­wen­di­ger­wei­se do­mi­nie­ren­de Men­gen sein. Man könn­te diese Teil­men­ge aber leicht zu einer do­mi­nie­ren­den Menge er­wei­tern, indem alle rest­li­chen Kno­ten, die noch nicht von der Teil­men­ge über­deckt wer­den, hin­zu­ge­fügt wer­den. Da­durch be­kommt man auf jeden Fall eine do­mi­nie­ren­de Menge.

Wenn man die An­zahl der Kno­ten in der do­mi­nie­ren­den Menge mi­ni­mie­ren will, ist das gleich­be­deu­tend damit, dass man die An­zahl der über­deck­ten Kno­ten ma­xi­mie­ren möch­te. Daher kann man die An­zahl der über­deck­ten Kno­ten als Be­wer­tung eines In­di­vi­du­ums be­nut­zen. Für die Re­kom­bi­na­ti­on wählt man eine be­lie­bi­ge Kno­ten­num­mer m aus. Das neu ge­ne­rier­te In­di­vi­du­um ent­hält dann alle Kno­ten, die in der Teil­men­ge des Va­ters ent­hal­ten waren und eine Num­mer klei­ner m haben, und alle Kno­ten, die in der Teil­men­ge der Mut­ter ent­hal­ten waren und eine Num­mer grö­ßer gleich m haben. An­schlie­ßend wählt man ei­ni­ge In­di­zes aus und fügt den Kno­ten hinzu, wenn er bis­her nicht in der Teil­men­ge ent­hal­ten war oder ent­fernt ihn, wenn er ent­hal­ten war18 .

Links

Wi­ki­pe­dia: Mi­ni­mal Do­mi­na­ting Set https://​en.​wi­ki­pe­dia.​org/​wiki/​Do­mi­na­tin­g_​set

CS Un­plug­ged: Do­mi­na­ting Sets – Tou­rist Town. http://​csun­plug­ged.​org/​do­mi­na­ting-​sets/

Asym­me­tri­sche Ver­schlüs­se­lung mit ex­ak­ten do­mi­nie­ren­den Men­gen

Gra­phen mit einer ex­ak­ten do­mi­nie­ren­den Menge könn­ten theo­re­tisch als Pu­blic Key für asym­me­tri­sche Ver­schlüs­se­lun­gen ein­ge­setzt wer­den und schla­gen damit eine Brü­cke zum Teil­ge­biet der Kryp­to­lo­gie. Im Bil­dungs­plan taucht diese Ver­bin­dung aber nicht auf und ist hier nur als Hin­ter­grund für den Leh­rer ge­dacht.

Eine ex­ak­te do­mi­nie­ren­de Menge ist eine Menge von Kno­ten, die den Gra­phen genau über­deckt. Kein Kno­ten ist also Nach­bar von zwei Kno­ten der do­mi­nie­ren­den Menge. Dabei ist der Graph der öf­fent­li­che Schlüs­sel und die ex­ak­te do­mi­nie­ren­de Menge das Ge­heim­nis, also der pri­va­te Schlüs­sel. Es ist nur mit gro­ßem Auf­wand (ex­po­nen­ti­el­le Lauf­zeit) mög­lich, aus dem öf­fent­li­chen Schlüs­sel das Ge­heim­nis zu be­rech­nen. Dies ist ty­pisch für die asym­me­tri­sche Ver­schlüs­se­lung, bei der die Si­cher­heit nicht dar­auf be­ruht, dass es un­mög­lich ist, die Ver­schlüs­se­lung zu bre­chen, son­dern le­dig­lich der Zeit­auf­wand zu groß ist.

Möch­te man nun eine Nach­richt (eine Zahl) ver­schlüs­seln, muss man sie zu­fäl­lig in ein­zel­ne Sum­man­den auf­tei­len und an jeden Kno­ten einen die­ser Sum­man­den schrei­ben. Dann ad­diert man bei jedem Kno­ten K die Zahl selbst plus alle Zah­len der Nach­bar­kno­ten und trägt das Er­geb­nis beim Kno­ten K ein. Dies stellt dann die ver­schlüs­sel­te Nach­richt dar.

Bei­spiel:

un­ver­schlüs­sel­te Nach­richt: 70

Auf­tei­lung auf 8 Sum­man­den: 70 = 10 + 5 + 7 + 9 + (-6) + 20 + 9 + 16

Programmierparadigmen

Bild­quel­le: Pro­gram­mier­pa­ra­dig­men von ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 01_hin­ter­grund.pdf, be­ar­bei­tet

Kennt man das Ge­heim­nis des Gra­phen, also die ex­ak­te über­de­cken­de Menge, muss man le­dig­lich die Zah­len an die­sen Kno­ten in der ver­schlüs­sel­ten Nach­richt ab­le­sen und ad­die­ren, um die Nach­richt zu ent­schlüs­seln (31+39 = 70), da an die­sen Kno­ten die Summe aller an­de­ren Kno­ten ein­ge­tra­gen und kein Kno­ten dop­pelt be­rück­sich­tigt wurde.

Man kann die ver­schlüs­sel­te Nach­richt auch an­grei­fen, indem man ein li­nea­res Glei­chungs­sys­tem mit n Un­be­kann­ten und n Glei­chun­gen (bei einem Gra­phen mit n Kno­ten) auf­stellt, um aus der ver­schlüs­sel­ten Nach­richt wie­der die ver­teil­ten Zah­len zu er­mit­teln.

Programmierparadigmen

Bild­quel­le: Pro­gram­mier­pa­ra­dig­men von ZPG In­for­ma­tik [CC BY-SA 4.0 DE], aus 01_hin­ter­grund.pdf, be­ar­bei­tet

Die­ses Glei­chungs­sys­tem lässt sich nach dem Gauß­ver­fah­ren in O(n3) lösen. Damit ist die­ser An­griff ef­fek­ti­ver als das Er­mit­teln der über­de­cken­den Menge. Die nor­ma­le Ent­schlüs­se­lung ist aber in O(n) durch­führ­bar. Damit kann durch eine aus­rei­chend große Zahl von Kno­ten eine hohe Si­cher­heit er­reicht wer­den. Der Auf­wand ist im Ver­gleich zum üb­li­chen RSA Ver­fah­ren aber zu groß. Das Ver­fah­ren ver­an­schau­licht aber das Prin­zip der asym­me­tri­schen Ver­schlüs­se­lung gut.

Einen ge­eig­ne­ten Gra­phen er­zeugt man, indem man zu­nächst die Kno­ten der exakt do­mi­nie­ren­den Menge zeich­net. Dann ver­teilt man eine be­lie­bi­ge Zahl von wei­te­ren Kno­ten und ver­bin­det jeden von die­sen mit genau einem der do­mi­nie­ren­den Menge. Da­nach kön­nen be­lie­big viele Kan­ten zwi­schen die­sen wei­te­ren Kno­ten ein­fü­gen (aber nicht mehr zu einem Kno­ten der do­mi­nie­ren­den Menge).

Links

Prä­sen­ta­ti­on Pu­blic Key Kryp­to­lo­gie, Dr. Lucia Di Caro (ETH Zü­rich) am Schwei­zer Tag der In­for­ma­tik 2020, URL:https://​www.​abz.​inf.​ethz.​ch/​wp-​con­tent/​uploads/​2020/​03/​Work­shop_​16_​Pub​licK​eyKr​ypto​logi​e.​pdf

Mi­ni­ma­ler Spann­baum (Mi­ni­mal Span­ning Tree – MST)

Man sucht in einem ge­wich­te­ten Gra­phen mit po­si­ti­ven Ge­wich­ten die­je­ni­gen Kan­ten, die alle Kno­ten ver­bin­den und deren Ge­samt­ge­wicht mög­lichst klein ist. Es ist klar, dass Zy­klen nicht auf­tre­ten kön­nen, da man dann eine Kante weg­las­sen könn­te und eine bes­se­re Lö­sung hätte. Daher ist die Lö­sung auf jeden Fall ein Baum. Ent­hält der Baum alle Kno­ten des ur­sprüng­li­chen Gra­phen nennt man ihn Spann­baum. Ge­sucht ist also ein mi­ni­ma­ler Spann­baum.

Mi­ni­mal span­nen­de Bäume:

Jeder mi­ni­ma­le Spann­baum ist ein zu­sam­men­hän­gen­der und zy­klen­frei­er Graph mit mi­ni­ma­lem Kan­ten­ge­wicht.

Mi­ni­ma­le Spann­bäu­me sind nicht nur für Gas- und Strom­net­ze nütz­lich, sie hel­fen auch, Pro­ble­me in Rech­ner­net­zen, Te­le­fon­net­zen, Pipe­lines, Flug­rou­ten und beim Ent­wurf von Com­pu­ter­chips zu lösen. All­ge­mein kann man sagen, dass Mi­ni­ma­le Spann­bäu­me immer dann in­ter­es­sant sind, wenn das Er­rich­ten der Rou­ten teuer, das Ver­wen­den der Rou­ten aber bil­lig ist. Al­ler­dings müs­sen bei der Rou­ten­pla­nung immer ver­schie­de­ne, häu­fig sich wi­der­spre­chen­de In­ter­es­sen be­rück­sich­tigt wer­den – zum Bei­spiel der Kom­fort einer Route, die be­nö­tig­te Zeit und die Kos­ten. Daher ist der MST-Al­go­rith­mus keine große Hilfe bei der Rou­ten­pla­nung, da es aus­schließ­lich ein Kri­te­ri­um mi­ni­miert: die Ge­samt­län­ge aller Stra­ßen oder Flug­stre­cken. Trotz­dem er­kennt man bei der Be­rech­nung eines MST für die größ­ten deut­schen Städ­te einen Teil des real exis­tie­ren­den Au­to­bahn­net­zes.

Mi­ni­ma­le Spann­bäu­me sind auch nütz­lich als ein Schritt auf dem Weg zur Lö­sung an­de­rer (schwie­ri­ge­rer) Pro­ble­me auf Gra­phen, wie zum Bei­spiel das „Pro­blem des Hand­lungs­rei­sen­den“ (Tra­ve­ling Sa­les­man Pro­blem, TSP).

Ob­wohl das Pro­blem nicht so ein­fach zu sein scheint, ist es nicht NP-voll­stän­dig. Es gibt ef­fi­zi­en­te Al­go­rith­men, um einen mi­ni­ma­le Spann­baum in po­ly­no­mi­el­ler Zeit zu fin­den.

Al­go­rith­men

Hier wer­den die Grund­prin­zi­pi­en zwei­er ver­schie­de­ner Al­go­rith­men zur Lö­sung des MST-Pro­blems skiz­ziert:

Der Prim-Al­go­rith­mus:

Die­ser Al­go­rith­mus lie­fert ga­ran­tiert einen MST.

Idee: Man be­trach­tet einen Teil­baum (zu Be­ginn einen be­lie­bi­gen Kno­ten) und be­stimmt die kür­zes­te Kante von die­sem Baum zum rest­li­chen Gra­phen. Diese Kante (zu­sam­men mit dem End­kno­ten) fügt man dem MST hinzu. Dies wie­der­holt man bis alle Kno­ten im MST ent­hal­ten sind. Es er­gibt sich fol­gen­der Al­go­rith­mus:

  1. Sor­tie­re die Liste alle Kan­ten nach ihrem Ge­wicht.
  2. Nimm einen be­lie­bi­gen Kno­ten k und mar­kie­re ihn.
  3. Suche die kür­zes­te Kante, die einen mar­kier­ten und einen nicht mar­kier­ten Kno­ten ver­bin­det.
  4. Mar­kie­re diese Kante und ihren noch nicht mar­kier­ten End­kno­ten.
  5. Wie­der­ho­le Schrit­te 3 und 4 bis alle Kno­ten mar­kiert sind (also n-1 mal).

Der Al­go­rith­mus hat po­ly­no­mi­el­le Lauf­zeit, da das Sor­tie­ren der Kan­ten in po­ly­no­mi­el­ler Lauf­zeit mög­lich ist (es gibt bei n Kno­ten höchs­ten m=n2 viele Kan­ten) und da­nach in jedem Schritt ein Kno­ten hin­zu­ge­fügt wird. Das Su­chen der kür­zes­ten Kante, die einen nicht mar­kier­ten mit einem mar­kier­ten Kno­ten ver­bin­det, ist in O(m) mög­lich.

Der Krus­kal-Al­go­rith­mus

Auch die­ser Al­go­rith­mus lie­fert ga­ran­tiert einen MST.

Idee: Die Kan­ten mit den kleins­ten Ge­wich­ten müs­sen im MST ent­hal­ten sein, wenn da­durch nicht ein Zy­klus ent­steht. Daher kann man die Kan­ten nach auf­stei­gen­den Ge­wich­ten durch­lau­fen und kon­trol­lie­ren, ob durch Hin­zu­nah­me zum Teil­graph der Kante ein Zy­klus ent­steht. Der Teil­graph ist zu­nächst (meist) ein Wald und wird all­mäh­lich zu einem Baum er­gänzt.

Um sich die auf­wän­di­ge Zy­klen­su­che zu er­spa­ren, kann man auch jeden Baum des Wal­des in einer Farbe fär­ben. Dann kann man an der Kno­ten­far­be er­ken­nen, zu wel­chem Baum ein Kno­ten ge­hört. Es er­gibt sich fol­gen­der Al­go­rith­mus:

  1. Sor­tie­re alle Kan­ten des Gra­phen nach auf­stei­gen­den Ge­wich­ten.
  2. Be­trach­te nach­ein­an­der alle Kan­ten der Sor­tie­rung nach (be­gin­ne also mit der Kante mit dem kleins­ten Ge­wicht)
    • Sind die End­kno­ten im glei­chen Baum (ihre Farbe ist ge­setzt und gleich), dann lö­sche die Kante, sonst mar­kie­re sie.
    • Ist die Farbe bei­der Kno­ten noch nicht ge­setzt, färbe beide in einer neuen Farbe.
    • Ist die Farbe eines Kno­ten noch nicht ge­setzt, färbe ihn in der Farbe des an­de­ren.
    • Sind beide ge­färbt und die Farbe un­ter­schei­det sich, dann färbe einen der Bäume kom­plett in der Farbe des an­de­ren.19

Der Al­go­rith­mus hat po­ly­no­mi­el­le Lauf­zeit, da das Sor­tie­ren in po­ly­no­mi­el­ler Lauf­zeit (es gibt höchs­ten n2 viele Kan­ten) mög­lich ist und da­nach in jedem Schritt eine Kante ab­ge­ar­bei­tet wird.

Beide Al­go­rith­men sind Gree­dy-Al­go­rith­men. Sie tref­fen in jedem Schritt die beste Wahl, die mo­men­tan zur Ver­fü­gung steht. Ob­wohl so­wohl der Prim- als auch der Krus­kal-Al­go­rith­mus so „kurz­sich­tig“ und gie­rig sind, ohne Rück­sicht dar­auf zu neh­men, wel­che Aus­wir­kun­gen die ge­trof­fe­ne Ent­schei­dung für den wei­te­ren Ver­lauf hat, lösen beide das MST-Pro­blem. Sie lie­fern nicht nur eine Nä­he­rungs­lö­sung, wie es beim Graph-Co­lo­ring-Al­go­rith­mus der Fall ist.

Beide Al­go­rith­men las­sen sich mit leich­ten Ver­än­de­run­gen auch be­nut­zen, um eine Nä­he­rungs­lö­sung für das Tra­ve­ling Sa­les­man Pro­blem zu su­chen:

Der Prim-Al­go­rith­mus ver­ein­facht sich, da die kür­zes­te Kante von einem mar­kier­ten zu einem un­mar­kier­ten Kno­ten für das TSP nicht im gan­zen bis­he­ri­gen Baum ge­sucht wer­den muss, son­dern am Ende der Route lie­gen muss. Man muss also nur die aus­ge­hen­den Kan­ten des Rou­te­n­en­des zu allen noch nicht mar­kier­ten Kno­ten be­trach­ten (vgl. TSP-Gree­dy im Gra­phen­tes­ter). Am Ende wird die Rund­rei­se durch eine Kante zwi­schen den bei­den Blät­tern des "Baums" ge­schlos­sen.

Der Krus­kal-Al­go­rith­mus ist etwas kom­pli­zier­ter, da man beim Zu­sam­men­füh­ren zwei­er Teil­bäu­me oder Ver­grö­ßern eines Teil­baums dar­auf ach­ten muss, dass keine in­ne­re Kno­ten son­dern nur Blät­ter ver­wen­det wer­den dür­fen. Au­ßer­dem muss zum Schlie­ßen der Rund­rei­se am Ende ein­mal er­laubt wer­den, einen Kreis zu bil­den.

Matching-Al­go­rith­men

Da Matching-Al­go­rith­men im Bil­dungs­plan nicht vor­kom­men, wer­den die Al­go­rith­men hier nicht näher be­leuch­tet. Sie sind aber trotz­dem span­nend, da sie viele reale Pro­ble­me um­fas­sen und quasi das Ge­gen­stück zum Fär­ben eines Un­ver­träglickeits­gra­phen bil­den. Eine gute Dar­stel­lung des Hop­croft-Karp-Al­go­rith­mus für bi­par­ti­tes Matching und des Blos­s­om-Al­go­rith­mus für be­lie­bi­ge Gra­phen fin­det man bei der TUM Mün­chen. Dort kann man auch mit ver­schie­de­nen Gra­phen ex­pe­ri­men­tie­ren.

Hop­croft-Karp-Al­go­rith­mus: https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​matchings-​hop­croft-​karp/​in­dex_​de.​html

Blos­s­om-Al­go­rith­mus von Ed­monds: https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​matchings-​blos­s­om-​al­go­rithm/​in­dex_​de.​htmlAb­ge­ru­fen 25.11.2020

 

17 Gree­dy Co­lo­ring in Wi­ki­pe­dia, freie En­zy­klo­pä­die, https://​en.​wi­ki­pe­dia.​org/​wiki/​Gree­dy_​co­lo­ring (12.05.2020)

18 Nä­he­res dazu: Cu Nguy­en Giap und Dinh Thi Ha, https://​www.​res​earc​hgat​e.​net/​pu­bli­ca­ti­on/​277013536_​Par­al­lel_​Ge­ne­tic_​Al­go­rith­m_​for_​Mi­ni­mum_​Do­mi­na­tin­g_​Set_​Pro­blem

19 Dies ist der schwie­ri­ge Teil des Al­go­rith­mus, wenn er ef­fi­zi­ent im­ple­men­tiert wer­den soll. Dazu ver­wen­det man so­ge­nann­te „Dis­joint-Set“-Da­ten­struk­tu­ren (vgl. https://​en.​wi­ki­pe­dia.​org/​wiki/​Dis­joint-​set_​data_​struc­tu­re ).

 

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

 

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