Senken und Quellen eines Graphen ohne Kreise? |
20.06.2005, 11:21 | Asgaroth | Auf diesen Beitrag antworten » |
Senken und Quellen eines Graphen ohne Kreise? 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 |
||
20.06.2005, 14:00 | 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 |
||
21.06.2005, 16:03 | 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! |
||
21.06.2005, 21:04 | JochenX | Auf diesen Beitrag antworten » |
eine schleife ist zwar ein kleiner kreis, aber auch das soll es geben mfg jochen |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|