Senken und Quellen eines Graphen ohne Kreise?

Neue Frage »

Asgaroth Auf diesen Beitrag antworten »
Senken und Quellen eines Graphen ohne Kreise?
Komme mal wieder bei Graphentheorie nicht weiter...

Sei ein gerichteter Graph, d. h., E ist eine endliche
nichtleere Menge von Ecken und eine beliebige Menge, die
gerichtete Kanten. Wenn ist, heißt (a, b) eine Kante von a nach b.
(Beachte: Schleifen und Zweiecke — — sind
möglich.)
Ein (gerichteter) Kreis in G ist eine Folge von paarweise verschiedenen Ecken
, so daß für und mit
.
Eine Quelle ist eine Ecke, zu der keine Kante hinführt. Eine Senke ist eine
Ecke, von der keine Kante wegführt.

Zeige:Wenn G keinen Kreis hat, hat G mindestens eine Quelle und mindestens
eine Senke.

MfG und auf Hilfe hoffend, Asgaroth
JochenX Auf diesen Beitrag antworten »

zu dem einen teil:
nehme an, es gäbe keine senke, d.h. du könntest von jedem knoten immer weitergehen (jeder knoten hätte ausgangskante)

dann kannst du also eine kette bilden, indem du immer von einem knoten zum nächsten gehst.......

dann bedenke: die eckenzahl ist endlich


edit: dass es eine quelle geben muss funzt völlig analog rückwärts
Asgaroth Auf diesen Beitrag antworten »

Das klingt sehr gut und logisch allerdings bin ich mir nicht sicher ob man das so machen kann da es ja auch Schleifen gibt, Zählt eine Ecke auch als Senke wenn sie nur abgehende Kanten hat welche zu ihr selbst führen? Ah ich hab gerade gesehen das eine Schleife auch ein Kreis ist also hat G keine Schleifen und damit ist wieder alles ok.
Danke Loed!
JochenX Auf diesen Beitrag antworten »

eine schleife ist zwar ein kleiner kreis, aber auch das soll es geben
Freude

mfg jochen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »