Bipartite Graphen Kreissuche < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:15 Di 24.01.2006 | | Autor: | bernie19 |
Hallo,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
ich möchte in einen ungerichtenten bipartiten Grahen, der keine Bäume enthält alle unabhängigen Kreise mit minimalem Durchmesser suchen. Die Anzahl der unabhängigen Kreise ist: n := Kanten-Knoten+Komponenten
Also für einen Graphen mit 9 Knoten, 12 Kanten und 1 Komponente gibt es 4 unabhängige Kreise. Durch Linearkombination der unabhängigen Kreise kann dann jeder beliebigen Teilgraphen konstruieren.
Kennt jemand für mein Problem einen effizienten Algorithmus?
Danke.
|
|
| |
|
Guten Morgen,
also Du meinst wohl: Du hast einen Graphen, bei dem keine Zusammenhangskomponente
ein Baum ist, oder ?
Denn die ZushKomponenten enthalten natuerlich Bäume als Teilgraphen.
Kreise min. Laenge findet eine schlichte Breitensuche. und diese kannst Du also fuer jede
Komponente durchfuehren. Da musst Du allerdings noch ein paar details ergaenzen.
Besser noch:
Du koenntest auch fuer jede Komponente einen spannenden Baum berechnen.
Jede weitere Kante erzeugt dann einen Kreis. Diese Kreise sollten eine Kreisbasis bilden, oder ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:42 Di 24.01.2006 | | Autor: | bernie19 |
Die Kreisbasen kann ich bereits berechnen.
Das Problem, dass ich noch habe ist aus den Kreisbasen die Kreise mit minimaler Länge herauszfinden.
Also gegeben ist ein Graph:
Knoten: 3, 4, 5, 6, "d", "e", "f"
Kanten: {6,"d"},{6,"f"},{5,"d"},{5,"e"},{5,"f"},{4,"e"},{4,"f"},{3,"d"},{3,"e"}
Die Kreisbasen sind:
Kreis 1: {{5, "d"}, {5, "e"}, {3, "d"}, {3, "e"}}
Kreis 2: {{6, "d"}, {6, "f"}, {5, "e"}, {5, "f"}, {3, "d"}, {3, "e"}}
Kreis 3: {{6, "d"}, {6, "f"}, {4, "e"}, {4, "f"}, {3, "d"}, {3, "e"}}
ich brauche aber:
Kreis 1: {{5, "d"}, {5,"e"}, {3, "d"}, {3,"e"}}
Kreis 2: {{6, "d"}, {6, "f"}, {5, "d"}, {5, "f"}}
Kreis 3: {{4, "e"}, {4, "f"}, {5, "e"}, {5, "f"}}
|
|
|
| |
|
Hallo nochmal,
also verstehe ich es richtig: Du hast eine Kreisbasis gegeben, zB weil Du sie vorher konstruiert hast, und moechtest nun aus dieser ALLE Kreise minimaler Laenge bestimmen,
richtig ?
Also wie schon angemerkt, kann man, wenn Du nicht darauf bestehst, zur Ermittlung der Kreise minimaler Laenge eine Kreisbasis als Ausgangspunkt zu verwenden, eine Breitensuche im Graphen machen, diese findet Kreise minimaler Laenge.
Aus einer Kreisbasis kann man andererseits, wenn man die Kreise als Vektoren
[mm] aus\{0,1\}^{|E|} [/mm] darstellt, via Linearkombination in GF[2] alle Kreise konstruieren:
Die Addition zweier Vektoren in GF[2] entspricht dem Bilden der symmetrischen Differenz der beiden Kreise, und diese ist eine Vereinigung von Kreisen - kuerzerer Laenge- und isolierter Punkte.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:25 Mi 25.01.2006 | | Autor: | bernie19 |
Danke,
ich werde mal versuchen eine Breitensuche zu implementieren und die Kreisbasen minimaler länge suchen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:42 Di 24.01.2006 | | Autor: | mathiash |
Hallo,
ich habe den Artikel mal ins Informatik-Forum verschoben, dort passt er meiner
Ansicht nach besser hin.
Viele Gruesse,
Mathias
|
|
|
|
