Mathematik: zweifach zusammenhängend bei optimiertem Weg
Released by matroid on Mi. 26. August 2009 12:48:51 [Statistics]
Written by wkleff - 1113 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Da das Problem des minimalen zweifach zusammenhängenden Graphen auf einen explodierenden Algorithmus führt, wird die Forderung soweit abgeschwächt, dass das Problem mit einem nicht explodierenden Algorithmus zu lösen ist.

Es wird gezeigt, dass sich ein minimal einfach zusammenhängender Graph so zu einem zweifach zusammenhängenden Graphen erweitern lässt , dass die damit verbundene Verlängerung des Weges, den maximalen Zuwachs an Redundanz erbringt.

Verallgemeinert kann festgestellt werden, dass der gefundene Algorithmus auch greift, wenn die Ausgangsmenge nur zusammenhängend ist. Damit eignet sich der Algorithmus zur Erhöhung der Redundanz in bestehenden Netzen, bei gleichzeitiger Optimierung der zusätzlich erforderlichen Verbindungen.



Eingrenzung des Themas

Die Literaturangabe stelle ich an den Anfang des Beitrags, da der Anlass, sich mit dem Thema auseinanderzusetzen, das folgende Buch war:

Das Geheimnis des kürzesten Weges [1]
Ein mathematisches Abenteuer

von den Mathematikern Prof. Dr. Peter Gritzmann und Dr. René Brandenberg.

Mein Sohn hat es geschenkt bekommen - gelesen hat es meine Frau. Als ich Sie Graphen skizzieren sah, wurde meine Aufmerksamkeit auf das Buch gelenkt. Am unten zitierten Satz blieb ich hängen (Seite 153/154):

Einen Graphen, der auch dann noch zusammenhängend ist, wenn man
eine beliebige Kante entfernt, nennt man zweifach zusammenhängend.
Möchte man eine minimale zweifach zusammenhängende Teilmenge
bestimmen, hat man ein sehr schwieriges Problem.

Wie schwierig es ist, wird mit folgender Aussage deutlich:

Will man die Lösung des Problems durch Probieren finden,
so führt dieses zu einem explodierenden Algorithmus.

Das Ausprobieren überlässt man heute natürlich dem Computer, denn der hat auch mit x-tausend Rechenschritten kein Problem. Explodierend heißt aber, dass mit der Zunahme der Punkte im Graphen, die Anzahl der Rechenschritte schnell so groß wird, dass auch ein Computer nicht mehr in endlicher Zeit fertig wird. Ein Algorithmus explodiert zum Beispiel, wenn bei n Punkten des Graphen die Anzahl der Schritte

n! oder 2n beträgt (n! = n (n-1) (n-2) ...).

Wenn Probieren zum Ziel führen soll, müssen also die Forderungen abgeschwächt werden.

Ich habe mich deshalb zunächst darauf beschränkt, einen Algorithmus zu finden, der einen minimalen einfach zusammenhängenden Graphen so mit Kanten ergänzt, dass er bei minimalem Längenzuwachs zweifach zusammenhängend wird.

Die Suche nach dem Algorithmus beinhaltet zwei Forderungen:

Zum Einen, die Suche nach dem kürzestem Weg.

Zum Anderen, die Erhöhung der Redundanz im Graphen.

Redundanz ist das Äquivalent zu verbunden in dem Sinne, dass eine Kante bezüglich eines Knotens dann redundant ist, wenn der Knoten auch dann noch versorgt wird, wenn die Kante entfernt wird.

Durch Probieren erkennt man schnell, dass bei geschickter Wahl einer zusätzlichen Kante gleich mehrfache Redundanzen entstehen. Man kann mit der Wahl einer kurzen Kante manchmal mehr Redundanz erzeugen, als mit der nächst längeren.

Die Wechselbeziehung dieser beiden Forderungen, hat mich auf die Idee gebracht, einen Algorithmus zu entwickeln, in dem beide Forderungen über die Wichtung ausbalanciert werden können.

Bild

Der gefundene Algorithmus liefert dann zum Beispiel obiges Ergebnis, dabei sind die schwarzen Kanten, die des minimalen einfach zusammenhängenden Graphen*.

An den Überschneidungen in diesem Beispiel wird deutlich, dass ein minimaler zweifach zusammenhängender Graph im allgemeinen keine Obermenge des minimalen einfachen Graphen ist. Mein Ansatz kann damit das Problem des minimalen zweifach zusammenhängenden Graphen nicht lösen!

Koordinaten des obigen Graphen (Kästchen von unten links gezählt):

Punkt

x

y

Punkt

x

y

 

1
2
3
4
5
6
7
8
9
10
11

15
11
29
14
1,5
5
3
2,5
25
31
3

41
38
35
33
28
28
27
26
26
25
24

12
13
14
15
16
17
18
19
20
21
22

28
4
7
10
8
9
20
1,5
9
12
23

23
22
19
18
17
14
14
13
11
9
5

 

* Als Punkte wurden in diesem Beispiel die deutschen Großstädte  genommen.


minimal einfach zusammenhängend

Für später noch anzustellende Überlegungen ist es von Vorteil, zunächst einmal den Algorithmus für den minimalen einfachen Graphen zu erzeugen. Einen Anhaltspunkt, wie dabei vorgegangen werden kann, liefert bereits die Theorie zum minimalen einfach zusammenhängenden Graphen.

Ein einfach zusammenhängender Graph hat bei n Knoten n-1 Kanten.

Die erste Kante verbindet 2 Knoten. Jede weitere Kante muss, wenn sie
verbunden sein soll, an einem Knoten ansetzen, der bereits zu einer Kante
gehört. Damit ist zur Einbindung jedes weiteren Knoten genau eine Kante
erforderlich, womit insgesamt n-1 Kanten benötigt werden.

Bei wenigen Knoten, lässt sich durch Skizzieren aller Möglichkeiten schnell ein einfach zusammenhängender Graph finden, dessen aufsummierte Kantenlängen kleiner als die der anderen - also minimal ist.

Dies legt nahe, den Beweis über die Existenz eines minimalen einfach zusammenhängenden Graphen für jede Anzahl von Knoten über die vollständige Induktion zu versuchen. Dabei wird angenommen, dass die Behauptung für n Knoten gilt. Es ist dann zu zeigen, das sie auch für n+1 Knoten gilt.

Auch wenn der zusätzliche Knoten (n+1) auf dem kürzesten Weg mit dem
bereits existierenden minimalen einfach zusammenhängenden Graphen
verbunden wird, so ist nicht klar, ob der neu entstandene Graph minimal ist.
Angenommen er ist nicht minimal, so kann der ursprüngliche Graph es
auch nicht gewesen sein, da die Ergänzung minimal gewählt wurde.

Der Widerspruch ist als Beweis ausreichend - indirekter Beweis.

Zum Aufbau eines Algorithmus, sollten die Knoten mit 1 beginnend fortlaufend durchnumeriert werden und bei den Kanten kann man sich darauf einigen, dass ihr erster Knoten immer die kleinere Zahl sein soll - zum Beispiel K(3,7).

Das gleiche soll für Verbindungen gelten, also das Aneinanderreihen von Kanten. Eine Verbindung V(3,7) könnte z.B. aus den Kanten K(3,5) und K(5,7) bestehen. Im Gegensatz zur Kante ist sie durch ihre Endpunkte nicht eindeutig definiert. Sie kann über die verschiedensten Punkte laufen, und damit je nach Weg verschiedene Längen besitzen. Dabei soll es verboten sein, zweimal über den selben Knoten zu gehen.

Im einfach verbundenen Graphen ist jeder Knoten mit jedem einmal verbunden, so dass es ohne Berücksichtigung der Richtung (kleine Zahl vorn), bei n Knoten (n-1) + (n-2) + ... + 2 + 1 Verbindungen gibt.

Wie schon gezeigt wurde, gehören zu diesen Verbindungen n-1 Kanten. Betrachtet man alle Kanten, die bei n Knoten eingezeichnet werden  könnten, so sind dies genauso viele - klar.

Das Programmieren eines Algorithmus als Datenbankanwendung ist wie kochen.

Zuerst werden die Zutaten bereitgestellt. Dies sind alle Kanten, die bei
den gegebenen n Knoten möglich sind. Sie werden in eine Tabelle gepackt,
dessen Index aus den Knotennummern gebildet wird. Zudem enthält jeder
Datensatz die Länge der Kante. Die Kanten werden nach ihrer Länge
aufsteigend geordnet, sodass die langen Kanten, die uns aufgrund der
Forderung nach dem kürzesten Weg nicht schmecken, nach unten kommen.

Zum Kochen des Eintopfs wird eine leere Tabelle Verbindungen
bereitgestellt, dessen Index wie bei den Kanten aufgebaut ist.

Der Kochvorgang läuft so ab - Man nehme aus der Tabelle Kanten die erste
(kürzeste) Kante in die Tabelle Verbindungen und füge alle Verbindungen
an, die sich damit bilden lassen. Deren Menge ist natürlich so lange leer,
wie sich keine zwei Kanten mit einem gemeinsamen Knoten im Topf
befinden. Sind alle möglichen Verbindungen aufgebaut, so ist die Suppe
fertig, und die n-1 Kanten im Topf sind die Lösung des Graphen mit dem
kürzesten Weg.

Dieser Algorithmus funktioniert nach dem Satz unter Greedy-Algorithmus und Matroide (siehe unten), weil speziell einfach zusammenhängende Graphen die Struktur aufweisen, die unten gefordert wird. Dies bedeutet aber noch lange nicht, dass ein solcher Algorithmus auch automatisch minimal ist.

Abgesehen von der Sortierung der Kanten nach ihrer Länge besteht der Trick bei diesem Algorithmus darin, dass durch die Hinzunahme aller Verbindungen und der Wahl des Index, die Kanten nicht in den Topf Verbindungen gelangen, die zu einem Spannbaum gehören, der dann nicht mehr den kürzesten Weg hat.

Der Greedy-Agorithmus und Matroide (aus [1])

Definition

Seien E eine endliche Menge und I eine nichtleere Menge von
Teilmengen von E. Das Paar (E, I) heißt Unabhängigkeitssystem,
wenn I abgeschlossen unter Inklusion ist, d.h. wenn gilt:

I I ∧  ⊂  I   ⇒  I   (1)

Die Elemente von I heißen unabhängige Mengen. Jede (inklusions-)
maximale unabhängige Menge von I heißt Basis. Gilt zusätzlich

Ip , Ip+1  ∧    | Ip | p     ∧   | Ip+1 | p + 1 

⇒  Ǝ Ip+1 \ Ip Ip ∪ {e } I   (2)

so heißt (E, I) Matroid.

Satz

Sei (E, I) ein Unabhängigkeitssystem. (E, I) ist genau
dann ein Matroid, wenn der Greedy-Algorithmus für jedes
c: E - [0,eine bezüglich c minimale Basis findet.


Der Algorithmus als Pseudocode
im Fall minimal einfach zusammenhängend

Open Recordsets: Verbindungen, Kanten

MoveFirst RS-Kanten

Do Until RS-Kanten = EOF

RS-Verbindungen addnew Kante
Do Until Count(Verbindungen) nicht mehr wächst

Verbindungskombinationen anfügen

if (Count(Verbindungen)=Count(Kanten)) then goto Ende

Loop

RS-Kanten MoveNext

Loop

Die Abfragen bauen die Verbindungen sukzessive auf. Es sind drei, denn ist K1-K2 eine Verbindung der Knoten K1 und K2, so ergeben sich die Kombinationen

K2 - K1 = K1’ - K2’ mit K2 < K2’ ,
K1 - K2 = K2’ - K1’ mit K1 < K1’   und
K1 - K2 = K1’ - K2’ mit K1 < K2’   mit jeweils

n-2
∑  i ((n-1)-i) Datensätzen.
i=1

Bei n = 107 steigt deren Anzahl auf über 200-tausend, wo heute die Grenze beim PC mit Access liegen dürfte. Am Beispiel von Seite 1 mit 22 Knoten rechnet mein PC (Dual-Core, 2 GHz) etwa 3 Sekunden. Rechnet man diese Zeit aufgrund der Durchläufe und der Anzahl von Datensätzen auf 1000 Knoten hoch, so kommt man auf eine sehr ernüchternd wirkende Zahl von rund 2.500 Stunden.

Anekdote zur Addition der Zahlen von 1 bis n - siehe links. Der Lehrer des kleinen Gauß hatte mal wieder keine Lust Unterricht abzuhalten und dachte sich, wenn ich die Zahlen von 1 bis 100 addieren lasse, sind die Kinder erst einmal beschäftigt. Doch Gauß hatte die Lösung umgehend, indem er 1+100 = 101 mal 50 = 5050 rechnete (erzählt von meinem Volksschullehrer).


Erweiterung zu zweifach zusammenhängend

Der minimale einfach zusammenhängende Graph (Fall 1) soll mit möglichst geringem Längenzuwachs zu einem zweifach zusammenhängenden Graphen erweitert werden (Fall 2).

Wie schon im Fall 1 geht man wieder von der Tabelle aller möglichen Kanten aus, wobei die bereits verwendeten Kanten gelöscht werden können. Die so aus Kanten entstandene neue Abfrage nenne ich Kanten2. Der entscheidende Schritt liegt auch hier in der Sortierung der Kanten. Im Fall 1 waren die Kanten nach ihrer Länge aufsteigend sortiert, wobei die Länge als Wichtung angesehen werden kann.

Im Fall 2 werden die Kanten wie schon im Fall 1
nach ihrem Gewicht geordnet.

Das Gewicht ist im Fall 2 der Quotient zweier Polynome, die im
Zusammenhang mit der Kante und deren Verbindungen stehen. 

Haben Sie bitte Verständnis dafür, dass ich sie hier nicht angebe, denn mit dem Aufbau des Algorithmus wird schon genug verraten. Möchten Sie mehr erfahren, so nehmen Sie bitte Kontakt zu mir auf!

Der Fall 2 weist gleich einen wesentlichen Unterschied zum Fall 1 auf.

Da die Wichtung nicht nur von der Kante selbst, sondern auch durch ihr
Umfeld beeinflusst wird, ist sie nach jeder Wahl einer neuen Kante neu
zu berechnen, d.h. die Sortierung ändert sich dynamisch beim
Durchlaufen des Algorithmus.

Im Fall 1 reicht zur Wichtung (Sortierung) der Kanten deren Länge. Im Fall 2 kommen die Länge der Verbindung und die Anzahl der Kanten hinzu, über die sie läuft. Also ist die Tabelle Verbindungen um diese Felder zu ergänzen. Mit Hilfe einer Inklusionsverknüpfung (LEFT JOIN) können diese Werte auch in Kanten2 zur Berechnung der Wichtung herangezogen werden. Zudem muss der Index der Tabelle Verbindungen, der aus der Kombination der Knotennummern besteht, um die Fachheit erweitert werden; also 1 für 1-fach zusammenhängend und 2 für 2-fach. 

Einfach bzw. zweifach ist ein wichtiges Schlüsselkriterium - denn,
wenn im Fall 1 die Verbindungslänge noch eindeutig ist, gibt es im Fall 2
mit dem Anwachsen der Lösungsmenge immer mehr alternative Wege,
so dass man sich bei nur einem zur Verfügung stehenden Datensatz auf
die Speicherung des kürzesten Weges beschränken muss.

Die Entscheidung für den kürzesten Weg kann bei endlicher Rechengenauigkeit auch falsch ausfallen, was mit steigender Knotenzahl zu einem Problem der Fehlerrechnung wird. Im Beispiel von Seite 1 reicht noch eine einfache Abschätzung aus, die so aussieht, dass der maximale Fehler über die Anzahl der jeweils beteiligten Kanten abgeschätzt wird.

Wie schon im Fall 1, möchte ich wieder zu einem Unabhängigkeitssystem kommen, das durch das Anfügen einer weiteren Kante aus Kanten2 nicht verletzt wird. Dies kann der Dreifachschlüssel (K1, K2, fach) allein nicht leisten. Betrachtet man das Beispiel aus dem ersten Abschnitt, so ist die folgende verschärfte Forderung nahe liegend.

Jede eingefügte Kante, darf mit keiner bereits existierenden
zweifachen Verbindung einen gemeinsamen Knoten haben.

Da der Algorithmus, wie schon im Fall 1, die Verbindungen sukzessive aufbaut, sind zur Speicherung der Verbindungslänge und der Anzahl von Kanten jeweils zwei Felder notwendig (Länge1, Länge2, KA1, KA2). Dies ist anlog zur schriftlichen Addition zu sehen, wo man sich auch die Zehnerstellen merken muss.

Nach der Hinzunahme einer neuen Kante in Verbindungen, werden wieder
alle abhängigen Kanten (Verbindungen) hinzugefügt. Abhängig heißt hier,
dass die Kante Teil eines Polygons ist, dessen übrige Kanten einfach sind.

Der Weg muss sich also zu einem Rundwanderweg schließen. Bei Rundwanderwegen gibt es oft eine alternative kürzere Runde. Aufgrund der Forderung, dass alle übrigen Kanten einfach sind und der speziellen Eigenschaften des einfach verbundenen Graphen ist die Runde eindeutig, also auch ihre Länge.

Damit die Schlüsselverletzung greifen kann, müssen natürlich noch
die zweifachen Verbindungen angefügt werden, die sich als Kombination
zweifacher Verbindungen ergeben.

Unter der Voraussetzung, dass im einfach verbundenen Graphen jetzt
über zweifache Kanten abgekürzt werden darf, müssen die Lägen aller
einfachen Verbindungen neu berechnet werden; und zwar solange, bis
der kürzeste Weg gefunden wurde (Schleife mit Fehlerabschätzung).

Der Algorithmus ist damit vollständig beschrieben. Was jetzt noch fehlt, ist der Bezug zum grünen Kästchen. Im Fall des minimalen einfach zusammenhängenden Graphen (Fall 1) habe ich nur in einem Satz darauf hingewiesen, denn der Zusammenhang kann in der Graphentheorie als bekannt vorausgesetzt werden.

Da ich mir im Fall 2 nicht sicher bin, ob dieser von mir auf einem Schmierblatt durch Probieren gefundene Algorithmus schon bereits irgendwo behandelt worden ist, sollte ich noch näher darauf eingehen.

Die durch den Algorithmus zusätzlich eingefügten Kanten eliminieren nacheinander alle freien Äste des Spannbaums durch Kreisbildung; und zwar jeweils zwei, solange noch zwei zur Verfügung stehen. Bei ungerader Anzahl freier Äste kann zum Schluss nur noch einer eliminiert werden. Die vorgenommene Wichtung hat darauf prinzipiell keinen Einfluss. Sie ist nur dafür verantwortlich, dass möglichst geschickt - im Sinne des kürzesten Weges - vorgegangen wird. Es handelt sich also um einen Greedy-Algorithmus. Somit bilden die roten Kanten ein Unabhängigkeitssystem, für das (2) gilt - siehe grünes Kästchen im Abschnitt “minimal einfach zusammenhängend”. Achtung - aus der Graphentheorie ist bekannt, dass die Kanten der Polygone, die durch die roten Kanten entstehen,  kein Unabhängigkeitssystem bilden.

Da der Algorithmus auf der Lösungsmenge des einfach zusammenhängenden Graphen aufsetzt (Fall 1), und dafür der Satz  im grünen Kästchen - Der Greedy-Agorithmus und Matroide - ebenfalls gilt, könnte man das Ganze als Kombination von Greedy-Algorithmen ansehen, dessen Basen disjunkt sind.

Interessant ist in diesem Zusammenhang, dass die Summe von
Matroiden, und speziell die direkte (disjunkte) Summe wieder ein
Matroid ist. Dies hat in Bezug auf den im Fall 2 verwendeten Algorithmus
die Konsequenz, dass er auch im Fall 1 gelten muss!

Bereinigt man den obigen Algorithmus um die SQL-Abfragen und Schleifendurchläufe, die bis zum vollständigen Aufbau des einfach zusammenhängenden Graphen nicht zum Tragen kommen, so ergibt sich der Algorithmus von Seite 2 - q.e.d..


Der Algorithmus als Pseudocode
im Fall zweifach zusammenhängend

Open RS-Verbindungen (RS=Recordset)

Do

Open RS-Kanten2 -> Verbindungen (LEFT JOIN)

MoveFirst RS-Kanten2

Do Until RS-Kanten2 = EOF

If (RS-Kanten2 hat mit einem RS-Verbindungen WHERE fach=2
einen gemeinsamen Knoten) then goto weiter

RS-Verbindungen addnew Kante

Do Until Count(Verbindungen WHERE fach=2) nicht mehr wächst

Polygonverbindungen anfügen
Kombinationen anfügen
Parameteraktualisierung

Loop (bezieht sich auf 2-fach)

Do Until ”kürzester Weg”

Parameteraktualisierung

Loop (bezieht sich auf 1-fach)

If Count(Verbindungen WHERE fach=2) = Count(Kanten) then goto Ende

Exit Do

weiter:

RS-Kanten MoveNext

Loop

Close RS-Kanten2

Loop

Das SELECT Kanten2 wurde geschickterweise so aufgebaut, dass die Kanten aus Kanten2, die bereits als 2-fache Verbindung zu Verbindungen hinzugefügt wurden, in Kanten2 nicht mehr enthalten sind.

Die aktualisierten Parameter werden über den LEFT JOIN auch dem Recordset Kanten2 übergeben. Damit erfolgt beim erneuten Öffnen des Recordsets Kanten2 automatisch wieder die Neuberechnung der einzelnen Gewichte, was wiederum deren Umsortierung nach sich zieht.

Alle Verbindungen, die Teil eines Polygons mit 2-facher Kante sind, werden als zweifache Verbindung angefügt - siehe “Polygonverbindungen anfügen” im Pseudocode. Dies ist notwendig, um das System auch unter 2-fach abzuschließen. Da diese Verbindungen bereits als 1-fache Verbindungen existieren, ergibt sich deren Aufbau wie folgt:

           K1      -     K2  2-fach 
             |               |
           K1      -     K2  1-fach
           /                 \
        K1’- K2’- K2’’- K1’’ 1-fach

Angefügt werden nun die Verbindung’ und die Verbindung’’, und zwar mit fach = 2. Ohne eine Verbindung auszulassen, kann angenommen werden, dass die Verbindung’ oder die Verbindung’’ oder beide Kanten sind (sukzessiver Aufbau).

Achtung - die obige Abfolge der Knoten ist jedoch nur als Beispiel anzusehen, da sich insgesamt 6 mögliche Kombinationen ergeben.

Es ist klar, dass der Algorithmus dann zum Ende kommt, wenn die Anzahl aller theoretisch möglichen Verbindungen gleich der Anzahl aller erzeugten Verbindungen mit fach = 2 ist, denn mehr Verbindungen kann es nicht geben. Es handelt sich dabei auch tatsächlich um einen zweifach verbundenen Graphen, da die Verbindungen mit fach = 2 alle Teil eines Polygons sind, das durch den Kreisschluss zweifach zusammenhängend ist.


\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: automatisch eingefügt und unbearbeitet :
zweifach zusammenhängend bei optimiertem Weg [von wkleff]  
Da das Problem des minimalen zweifach zusammenhängenden Graphen auf einen explodierenden Algorithmus führt, wird die Forderung soweit abgeschwächt, dass das Problem mit einem nicht explodierenden Algorithmus zu lösen ist.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 1113
 
Aufrufstatistik des Artikels
Insgesamt 118 externe Seitenaufrufe zwischen 2012.01 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com10.8%0.8 %
https://google.de2722.9%22.9 %
http://google.de6655.9%55.9 %
https://google.com1311%11 %
http://google.com32.5%2.5 %
http://google.ch21.7%1.7 %
http://search.sweetim.com21.7%1.7 %
http://search.conduit.com10.8%0.8 %
https://www.ecosia.org10.8%0.8 %
http://r.duckduckgo.com10.8%0.8 %
http://www.bing.com10.8%0.8 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 1 Aufruf in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.05.21 23:55https://matheplanet.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 90 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2021-2022 (27x)https://google.de/
2013-2017 (16x)http://google.de/url?sa=t&rct=j&q=
2020-2022 (13x)https://google.com/
201203-07 (12x)http://google.de/url?sa=t&rct=j&q=zweifach zusammenhängend
201201-01 (6x)http://google.de/url?sa=t&rct=j&q=kürzester weg matroid
201302-02 (4x)http://google.de/url?sa=t&rct=j&q=graphenfall mathematik gauss
201205-05 (4x)http://google.de/url?sa=t&rct=j&q=zusammenhängende erweiterung graphen
201202-02 (4x)http://google.de/url?sa=t&rct=j&q=zweifach zusammenhängende graphen
201206-06 (4x)http://google.de/url?sa=t&rct=j&q=zusammenhängend mathe

[Top of page]

"Mathematik: zweifach zusammenhängend bei optimiertem Weg" | 6 Comments
The authors of the comments are responsible for the content.

Re: zweifach zusammenhängend bei optimiertem Weg
von: gaussmath am: Mi. 26. August 2009 15:10:56
\(\begingroup\)Hallo, ich finde den Artikel sehr interessant. Danke dafür! Wie kriegt man diese Animation hin (Graph baut sich suk. auf) ? Grüße, gaussmath\(\endgroup\)
 

Re: zweifach zusammenhängend bei optimiertem Weg
von: valentin am: Mi. 26. August 2009 18:47:05
\(\begingroup\)Hallo wkleff, du schreibst: "Der minimale einfach zusammenhängende Graph (Fall 1) soll mit möglichst geringem Längenzuwachs zu einem zweifach zusammenhängenden Graphen erweitert werden (Fall 2)." Angewandt auf dein Städtebeispiel sollte dann aber doch in etwa folgende Lösung herauskommen: Bild und nicht das, was das Applet bei dir zeichnet. Vielleicht habe ich aber auch etwas ganz falsch verstanden? Beste Grüße. \(\endgroup\)
 

Re: zweifach zusammenhängend bei optimiertem Weg
von: PeterTheMaster am: Mi. 26. August 2009 19:47:28
\(\begingroup\)die laenge des graphen nimmt oben um 4 zu, bei dir um 5. da beide zweifach zusammenhaengend sind, ist also obiger eher eine loesung als deiner. den artikel habe ich nicht gelesen, nur am anfang ist mir aufgefallen, dass einmal 2n steht wo wohl 2^n stehen sollte, und kurz davor sagst du, ein computer koennte das nicht in endlicher zeit loesen, was natuerlich nicht stimmt, du solltest das endlich durch uebersichtlich oder so ersetzen.\(\endgroup\)
 

Re: zweifach zusammenhängend bei optimiertem Weg
von: DominikM am: Do. 27. August 2009 08:16:38
\(\begingroup\)@gaussmath: ich glaube, dass die animation mit flash nach der gleichen Technik wie ein animiertes gif gestaltet wurde.\(\endgroup\)
 

Re: zweifach zusammenhängend bei optimiertem Weg
von: valentin am: Do. 27. August 2009 08:59:33
\(\begingroup\)Hallo PTM, mit Länge ist hier sicherlich nicht die Zahl der Kanten gemeint, sondern die Summe der euklidische Distanzen. Und die ist in meinem Bild deutlich kleiner als in der Animation. Will man einfach nur irgendeinen zweizusammenhängenden Graphen mit minimaler Kantenzahl ausrechnen, so ist das Problem banal, denn jeder Kreis ist eine Kantenminimale Lösung des Problems. Viele Grüße. \(\endgroup\)
 

Re: zweifach zusammenhängend bei optimiertem Weg
von: PeterTheMaster am: Do. 27. August 2009 19:40:59
\(\begingroup\)hm, irgendwie geht das fuer mich nicht aus der beschreibung hervor. waere dann nicht von gewichteten kanten die rede oder so? ich sehe auch nicht, warum das problem dann banal waere, man hat doch sicherlich immernoch allerhand moeglichkeiten durchzuprobieren, oder?\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]