Test auf Kreisfreiheit
Olaf Musch
Nils Schmeisser wrote:
> =
> Hallo,
> =
> gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
> repraesentierte Graph kreisfrei ist?
> =
Wenn ich mich recht erinnere (lang ist's her) gibt es bei gerichteten
Graphen f=FCr jeden Knoten v die Menge der erreichbaren Knoten v*, die
halt zun=E4chst =FCber eine Kante erreichbar sind.
Das kannst Du ja auch aus der Adjazenzmatrix herauslesen.
Danach mu=DFt Du die erreichbarkeitsmengen sukzessive erweitern.
Ungef=E4hr so:
- Von Knoten A kann ich in einem Schritt die Knoten D,H und J erreichen:
v*(A) =3D [ D, H, J ]
- Von Knoten H aus gilt:
v*(H) =3D [ J, M, X ]
- und f=FCr M
=
v*(M) =3D [ A, X ]
Wenn Du jetzt die Mengen sukzessive zusammenfa=DFt und v*(v*(A)) bildest,=
mu=DFt Du nur =FCberpr=FCfen, ob irgendwann A element von (v*^i)(A) ist.
Der Aufwand ist natuerlich, wie bei Graphen so =FCblich, im worst case
ekelhaft hoch ;-)
Aber so ungef=E4hr geht's.
Ich glaub, diese Erreichbarkeitsdefinition stammt irgendwo aus den
Petri-Netzen, aber das sind ja auch Graphen ;-).
Literatur: Graphentheorie, OperationsResearch, Petri-Netze
hab aber grad keine Titel im Kopf.
Ich hoffe, das hilft :-)
Olaf
-- =
Life is like a bouncing ball:
The harder the ball, the better the bounce.
Nils Schmeisser
Hallo,
gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
repraesentierte Graph kreisfrei ist?
Danke,
Nils
Thomas Uhl
Nils Schmeisser wrote:
> gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
> repraesentierte Graph kreisfrei ist?
Indem du eine Tiefensuche durchfuehrst, und schaust, ob du in
einem Pfad des Tiefensuchbaumes zweimal denselben Knoten besuchst.
Z.B. mit folgendem rekursiven (Pseudo-)Programm:
global adj[1..n,1..n]
global Markierung[1..n]
prozedur tiefensuche(Knoten i) {
wenn Markierung[i] = 1 dann
print "Kreis gefunden"
exit
sonst
setze Markierung[i]:=2
fuer alle j mit adj[i,j]=1
tiefensuche(j) {rekursion}
ende wenn
setze Markierung[i]:=1
ende prozedur
hauptprogramm
fuer i von 1 bis n
setze Markierung[i]:=0
fuer i von 1 bis n
wenn Markierung[i]=0 dann
tiefensuche(i)
print "Kein Kreis gefunden"
ende
Das Programm verwendet Markierungen fuer die Knoten:
0 : Der Knoten wurde noch nicht besucht
1 : Der Knoten wurde besucht
2 : Der Knoten befindet sich im aktuellen Tiefensuchpfad
--
Thomas Uhl "Computers are not intelligent
uh...@informatik.uni-karlsruhe.de ...they only think they are."
Andre Poenitz
Nils Schmeisser (ni...@schmeisser.com) wrote:
: Hallo,
:
: gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
: repraesentierte Graph kreisfrei ist?
:
: Danke,
: Nils
Fuer ungerictete Graphen: (und modulo Denkfehler meinerseits ;-)):
Ein kreisfreier Graph ist eine "Wald", hat damit Kantenzahl gleich
Anzahl(Knoten) - Anzahl(Komponenten). Die Anzahl der Komponenten
kriegst Du mit Breiten- oder Tiefensuche in Zeit O(m).
Andre'
--
Andre' Poenitz, TU Chemnitz-Zwickau, Fakultaet fuer Mathematik
poe...@mathematik.tu-chemnitz.de .......... +49 3727 58 1381
Josef Leydold
Andre Poenitz (poe...@mathematik.tu-chemnitz.de) wrote:
Geht es nicht noch ein bisschen einfacher?
in einem (zusammenhaengenden) Baum ist
Anzahl der Knoten = Anzahl der Kanten + 1
in einem "Wald" sollte daher gelten
Anzahl der Knoten > Anzahl der Kanten
ein Abzaehlen der Komponenten ist da IMHO nicht notwendig.
Josef
P.S. Sorry fuer das letzte posting. da hat mir mein editor einen streich
gespielt.
Andreas Brunner
Hallo Nils!
Antwort auf eine Message von Nils Schmeisser an All:
NS> gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
NS> repraesentierte Graph kreisfrei ist?
Nach den vielen komplexen Vorschlaegen. wenn es nur um Kreisfreiheit ja/nein
geht:
1. Suche in der Adjazenzmatrix eine Nullspalte.
2. Streiche diese Nullspalte und die entsprechende Zeile.
3. Wenn noch Nullspalten vorhanden sind, gehe zu 2)
Ist die Matrix am Ende des Algorithmus 'verschwunden', ist der Graph kreisfrei,
ansonsten existiert ein Zyklus.
Andreas
Nils Schmeisser
Josef Leydold wrote:
> in einem (zusammenhaengenden) Baum ist
> Anzahl der Knoten = Anzahl der Kanten + 1
>
B: > Anzahl der Knoten > Anzahl der Kanten
Es ist A->B, aber leider nicht notwendig auch B->A.
Beispiel: |0 0 0 0|
|0 0 1 1|
|0 1 0 1|
|0 1 1 0|
4 Knoten > 3 Kanten, aber der Subgraph aus 2,3,4 und zugehoerigen Kanten
ist ein Kreis.
Andre' hat mir "ubrigens die Augen ge"offnet (man sollte doch immer
gleich alles posten).
Der Grund meiner Anfrage "uberhaupt: Ich habe einen kreisfreine Graphen
und nehme eine Kante hinzu, ist er dann immer noch kreisfrei?
Laesst sich ja doch ganz simpel beantworten:
0. Markiere alle Knoten i mit i
1. Kante (i,j) soll hinzugef"ugt werden:
ist Markierung(i)==Markierung(j) -> Kreis
sonst f"uge Kante ein und markiere alle, mit i und j (inkl. i und
j) zusammenh"anhenden Knoten mit dem gleichen Wert
Also, nochmals danke fuer alle Hinweise.
Gruss,
Nils
--
Nils Schmeisser ni...@schmeisser.com (+49 351) 260 2207
Forschungszentrum Rossendorf e.V. Bautzner Landstrasse 128
01474 Schoenfeld-Weissig
-> Adding enough zeros using a computer may lead to. (Murphy) <-
David Kastrup
Nils Schmeisser <ni...@schmeisser.com> writes:
> Josef Leydold wrote:
>
> Andre' hat mir "ubrigens die Augen ge"offnet (man sollte doch immer
> gleich alles posten).
> Der Grund meiner Anfrage "uberhaupt: Ich habe einen kreisfreine Graphen
> und nehme eine Kante hinzu, ist er dann immer noch kreisfrei?
> Laesst sich ja doch ganz simpel beantworten:
> 0. Markiere alle Knoten i mit i
> 1. Kante (i,j) soll hinzugef"ugt werden:
> ist Markierung(i)==Markierung(j) -> Kreis
> sonst f"uge Kante ein und markiere alle, mit i und j (inkl. i und
> j) zusammenh"anhenden Knoten mit dem gleichen Wert
Das geht natürlich am effizientesten mit dem Algorithus von Tarjan,
dessen Optimalität unter einer Klasse von Problemen im Artikel von
Leeuwen/Tarjan "Worst-case analysis of set-union algorithms" in Jurnal
of the ACM, 1986 belegt sein sollte.
Eine Variante für ein geometrisches Problem (Finden zusammenhängender
Bereiche) ist in
http://www.neuroinformatik.ruhr-uni-bochum.de/ini/PEOPLE/dak/cluster.html
zu finden. Diese Variante minimiert nicht den Aufwand beim Verbinden
zweier Gebiete durch Umlabeln der geringeren Teilmenge und ist daher
bei Graphen im luftleeren Raum (ohne geometrische Beziehungen)
unterlegen. Für die Operation auf dem Raster ergeben sich jedoch
Vorteile, die dies praktischer gestalten.
--
David Kastrup Phone: +49-234-700-5570
Email: d...@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209
Institut für Neuroinformatik, Universitätsstr. 150, 44780 Bochum, Germany
Josef Leydold
Andre Poenitz (poe...@mathematik.tu-chemnitz.de) wrote:
: Nils Schmeisser (ni...@schmeisser.com) wrote:
: : Hallo,
: :
: : gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
: : repraesentierte Graph kreisfrei ist?
: :
: : Danke,
: : Nils
:
: Fuer ungerictete Graphen: (und modulo Denkfehler meinerseits ;-)):
: Ein kreisfreier Graph ist eine "Wald", hat damit Kantenzahl gleich
: Anzahl(Knoten) - Anzahl(Komponenten). Die Anzahl der Komponenten
: kriegst Du mit Breiten- oder Tiefensuche in Zeit O(m).
:
: Andre'
:
: --
: Andre' Poenitz, TU Chemnitz-Zwickau, Fakultaet fuer Mathematik
: poe...@mathematik.tu-chemnitz.de .......... +49 3727 58 1381
--
-----------------------------------------------------------------------------
Josef Leydold | University of Economics and Business Adminstration
| Department for Applied Statistics and Data Processing
-----------------------------------------------------------------------------
Augasse 2-6 | Tel. *43/1/31336-4695
A-1090 Vienna | FAX *43/1/31336-738
Austria | email Josef....@wu-wien.ac.at
=============================================================================
Alles Unglueck kam daher, dass die Denkenden nicht mehr handeln konnten,
und die Handelnden keine Zeit mehr fanden zu denken. (Marlen Haushofer)
Horst Kraemer
>gegeben sei eine Adjazenzmatrix. Wie bekomme ich raus, ob der davon
>repraesentierte Graph kreisfrei ist?
Falls Du an einer moeglicherweise nicht effizienten aber hoechst
originellen und eleganten Methode interessiert bist:
Angewandte Graphentheorie fuer Ingenieure ;-)
Betrachte die Adjazenz-Matrix als BOOLEsche Matrix und bilde die
BOOLEsche Potenz A^n. (oder vornehmer: die Potenz einer Matrix mit
Elementen aus GF(2)).
Funktioniert auch bei gerichteten Graphen und bewerteten Graphen, wenn
man Werte ungleich 0 als TRUE interpretiert.
Ein Graph mit n Knoten ist genau dann kreisfrei, wenn alle
Diagonalelemente von A^n FALSE sind. Der Wert A^m[i][j] zeigt an, ob
es einen Weg der Laenge L, 1<=L<=m, von i nach j gibt. Falls nur die
Kreisfreiheit interessiert, kann die sukzessive Berechnung der
Potenzen von A abgebrochen werden, wenn fuer ein m<=n die Matrix A^m
ein Diagonalelement mit dem Wert TRUE besitzt.
Die Multiplikation aus dem Kopf in Zaeh...
int boolmul (char A[N][N], char B[N)[N], char C[N][N])
/* C = A * B */
/* Gibt die logische VerORung der Diagonalelemente von C zurueck */
{
int i,j,k,b,c=0;
for (i=0;i<N;++i) {
for (j=0;j<N;++j) {
for (k=0;k<N;++k) if ( b = A[i][k] && B[k][j] ) break;
C[i][j] = b;
}
c ||= C[i][i];
}
return c;
}
cu
Horst
David Kastrup
Olaf Musch <Olaf....@gzs.de> writes:
> Nils Schmeisser wrote:
> >
> > Andre' hat mir "ubrigens die Augen ge"offnet (man sollte doch immer
> > gleich alles posten).
> > Der Grund meiner Anfrage "uberhaupt: Ich habe einen kreisfreine Graphen
> > und nehme eine Kante hinzu, ist er dann immer noch kreisfrei?
> > Laesst sich ja doch ganz simpel beantworten:
> > 0. Markiere alle Knoten i mit i
> > 1. Kante (i,j) soll hinzugef"ugt werden:
> > ist Markierung(i)==Markierung(j) -> Kreis
> > sonst f"uge Kante ein und markiere alle, mit i und j (inkl. i und
> > j) zusammenh"anhenden Knoten mit dem gleichen Wert
> >
> > Also, nochmals danke fuer alle Hinweise.
> >
> Vorsicht !
>
> Wenn 1. zutrifft, hast Du aber eine Schlinge (Eine Kante, die im
> gleichen Knoten i beginnt und endet) Und das ist nur der
> kleinstmögliche Kreis. Einen Kreis aus 2 oder mehr Kanten kannst
> Du damit aber nicht feststellen.
Kann das sein, daß wir schon auf Alarm geschaltet haben, bevor der
Satzteil "und markiere all, mit i und j zusammenhängenden Knoten mit
dem gleichen Wert" eine Chance hatte, ins Gehirn vorzudringen?
Olaf Musch
Nils Schmeisser wrote:
> =
> Andre' hat mir "ubrigens die Augen ge"offnet (man sollte doch immer
> gleich alles posten).
> Der Grund meiner Anfrage "uberhaupt: Ich habe einen kreisfreine Graphen=
> und nehme eine Kante hinzu, ist er dann immer noch kreisfrei?
> Laesst sich ja doch ganz simpel beantworten:
> 0. Markiere alle Knoten i mit i
> 1. Kante (i,j) soll hinzugef"ugt werden:
> ist Markierung(i)=3D=3DMarkierung(j) -> Kreis
> sonst f"uge Kante ein und markiere alle, mit i und j (inkl. i und
> j) zusammenh"anhenden Knoten mit dem gleichen Wert
> =
> Also, nochmals danke fuer alle Hinweise.
> =
Vorsicht !
Wenn 1. zutrifft, hast Du aber eine Schlinge (Eine Kante, die im
gleichen Knoten i beginnt und endet) Und das ist nur der
kleinstm=F6gliche Kreis. Einen Kreis aus 2 oder mehr Kanten kannst
Du damit aber nicht feststellen.
Das geht dann nur noch =FCber Tiefensuche bzw. =FCber Folgemengen-
Vereinigung.
Ciao