aud 9 1 Minimaler Spannbaum (Färbungsalgorithmus)
Karsten Morisse
https://www.youtube.com/watch?v=BsMKIEYgSEU

Transkript (automatisch erstellt)

0:04 algorithmen auf graphen ist unser thema minimale spannbauer berechnen und zur motivation beispiele verbinde eine gewisse zahl von städten über eine
0:12 pipeline system welches eine möglichst geringe gesamtlänge besitzt also ziel wird immer sein dass jeder knoten von jedem anderen aus erreichbar ist ja und
0:19 hier irgendwie möglichst geringe gesamtlänge der strecke zwischen diesen daten oder wir haben irgendwelche elektrischen geräte die wir miteinander
0:26 verkabeln möchten ähnlich wie bei diesen pipelines und den stationen dazwischen die geräte die jetzt irgendwo zwischen zwei anderen sitzen die können sozusagen
0:34 vermitteln und möchten auch hier möglichst geringen kabel einsatz haben ausbau eines computernetzes auch da wird sozusagen verschiedene punkte die
0:40 möchten gerne miteinander kommunizieren und auch hier haben wir bestimmte kosten letztendlich an den verbindungsstrecken auch da geht es darum wie möglichst
0:48 minimale leitungs konfiguration zu ermitteln aufgabe jeder agent kennt einige seiner kollegen und kann sich mit diesen auch in verbindung setzen jedoch
0:56 besteht mit einer gewissen wahrscheinlichkeit die gefahr dass die kommunikation zwischen ag thi und j abgehört wird und wie können wir alle
1:02 agent mit anderen informationen versorgen so dass die gesamt wahrscheinlichkeit des abhörens möglichst gering ist das problem mit dem
1:09 wir es hier zu tun haben ist das problem des auffindens eines minimalen spannen baum sehen sie dass das identische problem ist alle drei also irgendwie zum
1:16 ausgleich wie hier sowas vorliegen er kann von mir das noch mit dem ebenfalls jeweils wert da dran
1:23 wir möchten erreichen dass jeder mit jedem kommunizieren kann aber halt nicht direkt das ist nicht so schlimm wenn das nicht funktioniert und das geht halt
1:30 auch im gehirn wege das problem das wir lösen müssen das msc problem minimum spanning tree mit minimaler spannbauer also das gehört eigentlich da oben rein
1:38 gegeben ist wir haben einen zusammenhängenden grafen bestehen aus einer menge von knoten v aus einer menge von kanten ehe und eine gewichts
1:45 funktion auf den kanten und wir suchen jetzt einen sogenannten auf spannenden baum also einem unter grafen von ge mit vollständiger knoten menge also enthält
1:53 alle knoten die auch in g drin sind aber nicht vollständig erkannten menge dieser graf ist ein baum sei es insbesondere kreisfrei und dass die summe der
2:00 erkannten gewichte der dann noch übrig gebliebenen kanten und minimale aber es besagt auch das heißt zwischen je zwei knoten gibt es soll genau einen weg und
2:11 aus dem grund schon ist das ding auch kreisfrei wenn es im kreis gebe gibt es zwei wege die man jetzt einfach mal so zu sagen die kann
2:18 die wir jetzt hin zu nehmen das ist noch keine spann baum dann müsste ich das noch hin mal ohne wenn ich das habe ist das einspannen baum nein warum nicht
2:27 weil ich dann kreist drin habe das ist also kein baum also auf spannende baum ist oder spannen baum also das allerdings müssen wir was wäre denn das
2:36 gewicht dieses spannenden wenn man nach zählen ist der minimalen ein genauso sie würden sozusagen vorschlagen dass dingen wegzunehmen
2:43 also kam der vorherigen schon minimal gewesen sein sohn und statt dem 15 können auch weglassen da können wir nämlich dekanter nehmen statt der zehn
2:54 auch die 4 nehmen ja genau darüber nach wie hinzu würde 26 30 ist das nicht eine spannende komme ich zu geben sieht schon ganz gut aus schon
3:03 jetzt die frage wie kann man das dann systematisch machen jetzt habt ihr ja wild geraten wie die ja ich stelle jetzt einfach drei verfahren stelle ich ihnen
3:09 eigentlich vor dass schäden zunächst ein anderes verfahren vor ort aus dem nicht aber die beiden anderen ableiten lassen und das ganze schimpft sich werbungs
3:14 algorithmus und um diesen färbung algorithmus vorzustellen brauchen wir noch einen begriff und zwar den begriff des schnittes im schnitt teilten grafen
3:22 immer auf in zwei teile geschnitten am grafen ge ist eine partition ist frau ohne es der knoten menge von ge also beispielsweise
3:31 wie so was dass wir sozusagen schnitt das wäre beispielsweise eine menge es also wieder über die menge frau ohne ist und eine kante kreuzt diesen schnitt
3:39 genau dann wenn der eine knoten in der eine menge ist und der andere knoten in der anderen menge das heißt in diesem beispiel hätten war 1234 kannten die
3:47 diesen schnitt kreuzen jetzt gucken wir an diesen werbungs algorithmus der ist eine stadt ist interessant und auch ganz ganz einfach werbungs algorithmus von
3:53 dacia ist wie gesagt ein ganz generische algorithmus da fahren wir einfach unsere kanten ein unter bestimmten richtlinien die werden irgendwie rot oder grün
4:02 gefärbt und wenn alle kannten gefärbt sind so bildet die menge der grünen kannten einen aufspannen baum minimalen gewichts deshalb gerade die eigenschaft
4:09 diese kanten färbung um die halt zu vollziehen dafür gibt es halt genau zwei regeln das eine ist die regel was andere die rote regeln und das ist nicht schwer
4:16 zu erraten dass mit der grünen regel kannte wohl grün gefärbt werden und mit der roten regel kanten roth die grünen kannten bestimmen später unseren baum
4:24 womit der grünen regel werden also kanten aufgenommen schritt für schritt wird unser wann baum erweitert ja und da bedienen bei uns der hilfe von schnitten
4:32 und mit der roten regel schließen wir halt kanten aus was wohl feststellen oder das ist eine kante die brauche ich definitiv nicht in einem spannend war
4:38 letztendlich geht es immer darum dass jeder knoten von jedem anderen erreichbar ist und wenn man kreis haben dann gibt es immer zwei wege zwischen
4:44 zwei knoten dann kann man wahlweise thorsten rausschmeißt nun schon den preis aufgelöst eine kante eliminiert was ist genau die rote regel gucken wir
4:52 mal genauer an die grüne regeln können wir immer dann anwenden es existiert ein schnitt im grad der von einer grünen kannte und mindestens einer ungefähr
5:00 gekreuzt wird und die regel fährt halt genau eine kante grün und zwar die kante minimalen gewichts in diesem chat die schnitte manchmal blau
5:08 das wäre zum beispiel ein schnitt ästhet einen schnitt im graf der von keiner grünen kannte und mindestens einer umgekehrten country kreuz wird das ist
5:15 hier beispielsweise der fall wenn ich jetzt diese regel an wende welche kannte würde ich dann einfärben wie sechs gefällt mir besser als die neuen v6 ist
5:21 kleiner als die neun vereine ungefähr bekannte minimalem gewicht sieht diesen schnitt kreuz die tante mit der elf mit der neuen mit der 10 und 6 sind die
5:30 kanten die diesen schnitt kreuzen und die minimalen gewichts die würden wir jetzt aufgrund dieser gegen hinzufügt jetzt erst mal die rote regeln es
5:37 existiert ein kreis im graf der keine rote kannte und mindestens eine ungefähr bekannte enthält das heißt wir müssen jetzt prüfen ob genau diese
5:45 voraussetzungen erfüllt ist man sich nicht einfach mal so im kreis ein beispielsweise was habe ich mir überlegt den mache ich mal so gestrichelt so das
5:53 ist ein kreis wer keine quote kannte enthält und mindestens eine ungefähr bekannte enthält das was wir jetzt leben gehabt haben ohne dieses blaue ist
6:00 irgendwie so eine momentaufnahme und ich muss jede kante einfärben rot heißt die gehört nicht zu unserem stammbaum dazu grün das ist halt gerade unser
6:06 spannenden das heißt wir müssen jetzt irgendwie mechanismus finden alle kanten zu färben wir haben keine rote wir haben ungefähr trainerinnen und jetzt werden
6:12 wir die aussuchen mit maximalen gewicht gewinnen rausschmeißen und das tun wir indem wir diese kante rot färben kreis in diesem beispiel würden die rot färben
6:19 die kante mit dem gewicht jetzt sind zwei ganz einfache regeln eigentlich idee ist halt wenn ich einen kreis habe was ich eben schon mal sagt dann gibt es
6:27 immer zwei wege zwischen zwei knoten die diesem kreis liegen die tollste kannte schmeiße ich jetzt einfach aber trotzdem kann ich diese beiden knoten noch
6:32 miteinander verbinden dieses rot färben und damit hinaus schmeißen macht uns die eigenschaften nicht kaputt dass wir zwei knoten miteinander verbinden können also
6:40 beispielsweise wenn wir jetzt diese regeln noch mal anwenden wollen also beispielsweise sind wir hätten auch diesen kreis nehmen können prüfen wir
6:45 einfach ist existiert ein kreis im graf das ist definitiven graf der keine rote und mindestens eine ungefähr bekannte enthält die elf und die zehen sind
6:52 ungefährt und die schmeißen mal getraut heißt die verbot so und jetzt der algorithmus solange noch eine der beiden regeln anwendbar ist wenn du die
7:00 grün-rote regel an das ist schon mal nicht schlecht was fällt uns denn da auf das heißt es nicht ganz genau festgelegt wie diese regeln angewendet werden jetzt
7:08 könnte natürlich das ding denn so implementieren und über irgendeinen zufalls komponente einer regel auswählen oder man macht aus diesem generischen
7:14 algorithmus halt irgendwie eine konkrete implementierung und hebt diesen nicht innenminister es auch was ist das zweite dann brechen wir das ding ab wenn keine
7:22 regel anwendbar ist oder eigentlich können was sogar noch verfeinern wenn die grüne regel nicht mehr anwendbar ist wir wollen einen minimalen spannen
7:28 bestimmen und das müssen wir noch überlegen das ist natürlich hinterher die grün gefärbten kanten gerade die eigenschaft haben einen solchen
7:34 minimalen spannend darzustellen wenn das der fall ist können wir das ding beenden wenn die grüne regel nicht mehr anwendbar ist
7:40 ja und behauptung behaupten kann man vieles aber wir müssen uns auch überlegen dass das auch wirklich der fall ist machen wir später fliegt man
7:47 jetzt im schnitt und sage ich fange es mit dieser grüne regel an ich färbe die kante 2 1 wie kriegt die farbe grün wunderbar
7:53 legen wir noch im schnitt hierdurch wir könnten beispielsweise hier ein durch legen um irgendwie von dieser knoten menge
7:58 hier zu der knoten menge zu kommen müssen wir über eine der geschnitten kanten hier gehen versuchen uns jetzt die kleinste aus das ist ja nicht die
8:05 idee von dieser grünen regel ist das wäre in diesem fall die sieben noch eine grüne regel wir könnten wir so machen wir haben den schnitt gefunden der keine
8:11 grüne und mindestens eine ungefähr bekannte enthält und da würde man jetzt die minimale aussuchen und das wäre die 3 und noch einen schnitt machen
8:20 das wäre dann das dingen dann haben wir noch den beispielsweise ist die firma wir ein bisschen auf hier
8:32 und was haben wir für gewicht 30 27 können wir dieses ding mal anwenden finden wir noch irgendeinen schnitt der nicht durch eine grüne kannte geht ich
8:41 sehe auch keinen können wir die rote regel normal wenn also wenn wir jetzt anwenden können mit roter regel was haben wir denn jetzt noch zu tun was
8:49 müssen wir jetzt überlegen ob er gut ist und die güte drückt sich aus natürlich irgendwann der laufzeit und in der korrektheit und wir müssen uns dann noch
8:55 irgendwie überlegen mensch wie kann man das denn implementieren wir werden das über eine in variante machen so eine in variante also in der bedingungen die an
9:02 ihm möglich ist nach jedem färbung schritt existiert im graf ein auf spannender baum minimalen gewichts der alle grünen und keine roten kanten
9:08 enthält also werden uns überlegen weil wir werden zeigen dass dieser färbung algorithmus sowie waren da geschrieben haben das ist ja genau diese in variante
9:15 enthält und wir werden zeigen dass solange noch nicht alle kannten gefärbt sind noch mindestens eine regel anwendbar ist das heißt wir werden das
9:21 ganze in zwei schritten machen und wenn man das alles gezeigt haben können wir sagen am ende des algorithmus definieren die grünen kannten einen auf spannenden
9:29 baum minimalen gewichts und zweitens muss man zeigen wenn wir die roboter regeln an wert dann gilt dieses jahr noch und wir
9:35 müssen noch zeigen ja solange noch nicht alle kannten gefärbt sind ist noch mindestens eine regel anwendbar da sind wir eingestellt
9:41 am ende haben wir dann die aussage dass die grünen kannten gerade ein aufspannen baum minimalen gewichts definiert der färbung des algorithmus erhält die
9:48 färbung in variante dem thema widmen als erstes kann man das mal mit seiner induktion probieren das heißt wir gucken uns jetzt die schritte einzeln an
9:55 wir können ja unendlich anzahl von schritten durchführen wenn du so ein induktives argument an also wenn vor ausführung eines währungs schritt ist
10:02 ein auf sparer bei minimalem gewicht existiert was wir steigen jetzt mitten rein gucken muss sagen so das gilt am anfang dann sagen wir haben das ding
10:09 jetzt irgendwie in einer gewissen art und weise gefärbt grüne kann ein paar rote kannten es gibt aber auch noch ungefähr bekannt
10:14 und dann gucken uns einfach an so wie sie das denn jetzt aus wenn wir an dieser stelle allgemeingültig sozusagen die hunde
10:19 obwohl die roten gilt halt diese aussage die wir nachweisen wollen diese färbung in variante immer noch und habe eigentlich allgemeingültig gezeigt das
10:26 mittel dann immer nachgeben schritt wie ist das denn mit dem induktions anfang wurde im ersten schritt ist die färbung sin variante trivialer weise erfüllt
10:33 daran minimalen spannen baum haben und hält er auch alle eingezeichneten grünen kannten das es gibt nämlich keinen aber minimale spannung gibt es immer aber da
10:41 wir noch keine einzige karte gefärbt haben sozusagen bei null anfangen gilt das also jetzt sagen wir haben eine reihe von schritten gemacht und jedem
10:47 schritt färben wir ja eine kante ein das haben wir gepennt kanten gefärbt und jetzt wollen wir die endlos erstes wir gucken uns jetzt endlos ersten schritt
10:54 an was gucken wir uns zwei fälle an einmal nämlich dass wir eine grüne regel anwenden und einmal dass man regeln in beiden fällen werden wir zeigen dass
11:01 dann unsere aussage immer noch gilt wir gucken uns jetzt als erstes den fall an das war die grüne regel anwenden also die situation vor der anwendung der
11:08 grünen regeln diese färbung in variante ist erfüllt es gibt also einen aufspannen bei minimalem gewicht der alle grünen und keine roten kann enthält
11:15 das ja das was er gegen eigentlich zeigen wollen und der induktions annahme gilt dass wir haben eine voraussetzung für die grüne wege es gibt einen schnitt
11:22 der von keiner grün kann und wenn es nur ungefähr bekannte gekreuzt wird nur wenn man jetzt diese grüne regel anwenden würden wir uns die ungefähr bekannte er
11:29 in wir jetzt einfach gern nehmen mit minimalem gewicht die sich mit kreuzt die farben war jetzt grün sondern es müssen wir unterscheiden diesen
11:36 minimalen spannbauer den gibt es ja immer ist ein graf habe und jetzt mit in meinem algorithmus drinstecke minimalen sparen warum gibt es aber besteht nicht
11:43 nur aus kannten sich eingefärbt habe da sind auch vielleicht ein paar kanten dabei die ich noch nicht gefärbt haben und die gilt es jetzt zu
11:48 identifizieren so und jetzt kann das aber sein wenn ich jetzt an dieser stelle bin ich finde diese grüne regel an und diesen schnitt weniger definiert
11:55 habe und diese ungefähr bekannte mit dem minimalen gewicht aber ich wieder zwei fälle die kann entweder zu dem baum gehören dem minimalen spannen bauen oder
12:01 sie war noch nicht wissen warum drin ich bin mittendrin in meinem algorithmus ein paar von diesen kanten sind grün gefärbt paar sind rot gefärbt habe ich einen
12:08 schnitt endlich fixiert mit einer ungefähren kannte der kann bestandteil sein des minimalen sprang baums muss es aber nicht so wenn der bestandteil ist
12:15 also schon in diesem minimalen schwankungen drin war dann wird sozusagen die anzahl der grünen kann um 1 erhöht ist weiterhin bestandteil
12:21 dieses spannen baums weil es ja eine kante mit minimalem gewicht war die kante war vorher um gefärbte kante des baums b und wie es andere gefährten
12:29 ändert nichts an dieser färbung in varianten die sagt ja gerade die grünen kannten definieren wir ende mai minimalen spannen war also
12:35 gefallen kann de war vor anwendung der regel dass ungefähr bekannte im baum b und bleibt durch die färbung nun als grüne kanton ein bisschen mehr arbeit
12:43 ist jetzt der fall wenn diese kannte vorher noch nicht in den baum drin war wir haben diese situation wir haben ein paar kanten grün gefärbt man diese dann
12:52 haben wir ein paar rote kannten ich habe noch irgendwie ein paar kanten wie male ich jetzt mal in blau noch dazu das sind kannten die
12:59 bestandteil meines minimalen spannen baum sind weil sie noch mal die kante gehört noch mit dazu sondern jetzt ist die aussage bei der
13:05 grün regel es gibt einen schnitt der von keiner grünen kannte und mindestens einer ungefähr bekannte gekreuzt wird das könnte jetzt beispielsweise sonst
13:12 nichts sonst jetzt erkannte einzuführen und sagen wir mal hier unten diese kannte das ist die kante minimalen gewichts in diesem
13:18 schnitt werden irgendwie mit e bezeichnet und jetzt müssen wir irgendwie zeigen wenn wir den einfärben dann gilt
13:24 weiterhin unsere färbung variante also er ist von diesen vier kanten haben dass er jetzt in gewicht auf gewählt ist dass diejenigen mit minimalem gewicht was
13:35 müssen wir jetzt tun damit wir trotzdem noch unsere gültigkeit haben der aussage es gibt eine minimale spannen warum der alle
13:40 grün und keine roten karten enthält wichtig war wie der fall wäre sagt gerade das noch nicht bestandteil und so ist minimal spannen bei uns war der war
13:47 vorher diese durch gezeichneten grünen linien und diese blauen linie wir haben den minimalen spannen bei der alle knoten miteinander verbindet so man
13:53 jetzt haben wir eine kante identifiziert hier über so einen schnitt es muss also zu diesem thema noch eine zweite kante geben ich will jetzt nicht austauschen
13:59 können diese blaue kannte das ist jetzt ein potenzieller kandidat war einfach austauschen weil er war ja so gewählt wird der minimales gewicht kann
14:06 sie hat also ein kleines gewicht als dieses dingen hier sehen wir jetzt einfach austauschen die kante hinzunehmen die dafür wegnehmen die
14:12 blauen aber immer noch in spandau wir können immer noch alle knoten miteinander verbinden wie ist das denn jetzt mit der gültigkeit unserer fans in
14:18 variante und wir haben jetzt ein minimal spannbauer der wiederum aus allen grünen besteht lust noch einige umgefärbt sind was sind diese blauen haben die ungefähr
14:25 ptn oder die anzahl der umgekehrten kanten reduziert die anzahl der grünen um 1 erhöht wenn wir jetzt nachweisen das ist genau unsere werbung in variante
14:33 dann haben wir genau induktions schritt vollzogen das gleiche machen für die rote rede wenn also eh zuvor nicht in b enthalten
14:39 war gibt es eine andere kannte die striche nennen wir niemals also war jetzt hier eben diese mag ich noch mal blau ein
14:45 gibt es eine andere ktg strich mit den eigenschaften kreuz denselben schnitt de das folgt einfach aufgrund der tatsache dass beh zusammenhängt ist und er ist
14:57 ungefährt roth kann sie nicht sein weil sonst wäre sie nicht bestandteil des minimalen spannen bei ausruhen kann sie nicht sein weil wir sonst die grüne
15:04 regel nicht hätten anwenden können und es muss gelten wie strich ist größer als w v aber egal so gewählt hatten aber die
15:13 kannte minimalen gerichts darauf geben im schnitt austausch argument für unsere werbung in variante also in diesem baum diese minimalen spannen baum denen wir
15:22 halt schrittweise aufbauen tauschen und jetzt strich aus durch und das ding wird dadurch günstiger möglich und hält zusätzlich eine grüne kannte mehr dass
15:29 er wichtig was wir gehen von über zu strich und beistrich wie sieht das denn aus bei der roten linie werbung schritt ist anwendung der roten
15:38 regel situation vor der anwendung der roten regel werbungs in variante gilt es gibt also einen ausspannen bauern geben in dem angesichts der alle grünen und
15:45 keine roten karten enthält und die voraussetzung für die rotherin lässt erfüllt das heißt es gibt einen kreis der keine rote karte und mindestens eine
15:51 ungefähr bekannt enthält und wenn wir jetzt diese regeln wenn dann nehmen wir die ungefähr bekannte maximalen gewichts die auf diesem kreis liegt in die firma
15:59 roth ein wieder zwei fälle die kante e das potenzial auch so eine blaue sein die wir da eben hatten wenn die zuvor nicht im baum drin war
16:05 über die roth ein das macht aber unserer aussage der färbung variante nichts kaputt da geht es ja nur um minimale spannen baum mit allen grün kann und
16:12 keinen roten karten und das bleibt in diesem fall erfüllt fall b schon spannender wenn diese kannte die wir jetzt rot einfärben in dem spannenden
16:19 rennen war dann müssen wir eine andere kante finden diese statt dieser kannte jeder aufnehmen können die aussage ist wir können die rote regel anwenden es
16:27 gibt einen kreis der keine rote kannte und mindestens ein ungefähr bekannte enthält und die regel sagt ja wir holen uns die kante auf diesem kreis mit
16:36 maximalen gewicht haus sei jetzt mal diese kannte die nennen wir wieder die hat zwar endpunkte die kante und das sage jetzt mal hier oben die knoten in
16:43 diesem spannenden liegen und die knoten die über diesen spann baum von diesem punkt aus erreichbar sind das sei dass man mit dieser menge dann
16:51 haben wir zwei knoten länge das sind die knoten über die kanten unseres spannen baums von diesen knoten aus erreichbar sind
16:57 von der anderen kannte von diesen liegen diese menge das sind ganz viele knoten endlich hunderttausende von toten beispielsweise aber diese situation
17:04 haben wir eine reihe von knoten lieber von diesen knoten hier unten aus erreichen können und das ist quasi eine menge dann haben wir unsere kannte die
17:11 wir jetzt mit hilfe der roten regeln identifiziert haben im schnitt 104 aufteilung der knoten länge in zwei teile nämlich die knoten längen die von
17:18 diesen knoten aus erreichbar sind und die knoten länge die von diesen knoten aus erreichbar sind was lässt uns diese rote regelwerk
17:25 anwenden es gibt einen kreis das heißt irgendwo gibt es dann auch noch eine kante wollen sie jetzt einfach mal hier oben hin den strich ich kann von mir aus
17:33 auch hier irgendwo her gehen irgendwie aus dieser menge aus dieser knoten menge gibt es noch eine kante wir werden diese andere menge zurück führt das heißt über
17:40 diese kannte die jetzt quasi im rahmen dieser roten regel ausgewählt wurde ist er nicht im schnitt definierten mensch nicht gucken uns jetzt mal an indiziert
17:47 einen schnitt wegen dieser kreis also wegen der anwendbarkeit der roten regel die kann ich rot sein nach anwendbarkeit und grün kann sie auch nicht sein da sie
17:56 sonst halt zu diesen baum b gehören würde und was gilt auch noch das wfp strich kleiner ist als w von e das war grad
18:04 nach auswahl so definierte anerkannte aus unserem baum die tauschen jetzt leer aus da wir neben mir zu zeigen in unserem baum b
18:11 pikante e aus gegen die kante strich werden die rot und trotzdem noch einen gültigen minimales spannender gucken uns nochmal
18:17 auch im sommer ein beispiel an unseren baum hören jetzt noch ein paar kanten zu die wir uns halt sozusagen dazu denken die eigentlich umgefärbt sind so jetzt
18:26 würden wir uns im kreis raussuchen ja das wäre jetzt irgendwie die anwendung der roten regel das könnte beispielsweise im kreis sein sondern das
18:33 haben wir diese beiden fälle entweder ist diese kannte bereits bestandteil dieses baumes das bekannte maximalen gewicht jedoch ungefähr sind also alle
18:41 vier konnten jetzt in diesem beispiel käme in frage wenn wir eine nehmen die nicht zu unseren baum wird zu zählen würden wenn das die maximale kannte wäre
18:48 würden wir einfach rot färben das würde nichts ändern das war eben dieser triviale fall und den fall dem aus jetzt gerade angeguckt haben wäre wenn wir
18:55 beweise dieser kannte wenn das die kante mit maximalen gewicht wäre dann kriegen wir darüber einschnitt wenn das wasser die kante wäre die mache ich jetzt mal
19:02 in die rot gestrichelt dann haben wir hier über so einschnitt weil die quoten die ich von diesen knoten aus erreichen kann
19:07 also wären also einmal der der der und der schnitt sehr dann so aus die würden wir jetzt rot färben und dann würden wir eine mit kleineren gewicht her nehmen
19:17 und die zu unserem schnitte zu zählen also die würden dann wieder blau gefärbt werden ja also beispielsweise kann dass
19:22 die kanten sein dass wir das was wir ausgewählt haben und das könnte dann das strich seien wichtig ist also das ist ausgewählt das ist eine kante maximalen
19:30 gewicht in diesem kreis wir finden jetzt auf jeden fall eine kann das haben wir uns gerade überlegt eine kante strich wird kleiner im gewicht die ungefähr
19:38 und die würden wir jetzt sozusagen uns zu unserem spannen baum hinzunehmen die würde im späteren schritt dann vielleicht grün gefärbt werden aber
19:44 wichtig ich jetzt schließt man ja eine kante aus und das ist diese karte hoben die würden wir jetzt hier neben schritt roth marxistischen e&e strich aus also
19:52 wir entfernen die jetzt gerade rot gefärbte kannte und füge ich hinzu und wichtig ist jetzt dieser neubau strich in klammern gleich b - e-plus strich
20:05 dann nehmen wir die kante weg und nehme die kante strich hinzu erfüllten wieder diese färbung in variante wir haben gezeigt diese färbung in
20:13 variante bleibt die ganze laufzeit erhalten das heißt wir haben einen auf spannenden baum der alle grünen kannten enthält und keine rote und egal welche
20:21 regeln wir anwenden das bleibt auch weiterhin gültig und jetzt müssen wir noch zeigen im zweiten teil so lange noch nicht alle
20:27 kannten gefärbt sind ist noch mindestens eine regel anwendbar das ist das was wir zeigen wollen folgendes liegt jetzt vor wir stecken
20:32 wieder mitten drin irgendwo in unserem algorithmus ziel ist es ja alle knoten miteinander zu verbinden wir starten quasi am anfang mit einzelnen grünen
20:40 knoten die werden wir über grüne kanten miteinander verbinden haben dann später den minimalen spangenberg von wäre im algorithmus drin stecken dann sieht das
20:46 vielleicht so aus wir haben einige kannten gefärbt einige kanten sind rot gefärbt und einige kanten sind ungefähr und jetzt können wir uns eine kante
20:54 hernehmen eine ungefähr bekannte und jetzt zwei fälle wenn uns diese kannte hier anschauen dann gehören beide endpunkte zum selben grünen baum
21:01 die menge der jetzt mit und kanten verbundenen knoten bilden einen grünen bauen oder es gibt den fall bei der endpunkte gehören zu verschiedenen
21:07 bäumen das wäre beispielsweise bei dieser kannte oder bei dieser kannte der fall oder auch weil dieser kannte da müssen wir jetzt angucken wie wir das
21:13 behandeln gucken uns erst den ersten voll an beide knoten liegen im selben baum also beispielsweise bei dieser kannte müssen
21:20 jetzt endlich zeigen für beide fälle die wir jetzt haben können wir noch eine unserer beiden regeln anwenden also beispielsweise hier diese kante da wäre
21:26 das ja der fall warum kommen die roten wänden schnitt kriegen wir nicht hin aber wir können den kreis definieren wir müssen ja im
21:34 kreis haben der mindestens eine ungefähr bekannt und keine rote karte enthält das ding war in dem fall immerhin das heißt in dem
21:41 finden wir immer die anwendbarkeit der roten regeln und falls 2 das wäre jetzt beispielsweise bei dieser kannte der fall
21:49 wir haben ja 1234 grüne bäume sozusagen wenn man die situation haben dass wir eine kante eine ungefähr bekannter habe deren endpunkt in zwei unterschiedlichen
22:00 bäumen liegen und dann finden wir mal ein schnitt so beispielsweise und würden jetzt eine dieser kanten hier jetzt in diesem fall ihr drei kanten würden uns
22:08 die minimale auswählen und eine davon irgendwie grün färben alle drei umgefärbt das ist der schnitt geht nur über ungefähr bekannten weil jetzt wenn
22:15 beispielsweise diese kannte hier wenn man jetzt aufgrund dieser überlegungen hier diese kante grün wäre ich ja diese kante von leben ausgegangen
22:23 war bisher immer ungefähr können weitermachen irgendwann würden wir die dann sozusagen als minimale identifizieren oder wir würden dann
22:29 irgendwann die andere regel anwenden können wenn wir jetzt mit so einem schnitt hier diese kannte als minimale identifizieren
22:34 würden dann würden wir halt grün färben oder aber wir würden beispielsweise jetzt in dem schritt diese kannte hier grün färben
22:41 dann kommt noch flüchtig kannte will die rot regel nehmen sagen bei diesem fall zwei müssen wir nicht notwendigerweise die kante färben
22:48 wir uns ja sozusagen rausgenommen haben aber irgendwann werden