Graphentheorie < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:27 Fr 23.11.2007 | | Autor: | babsbabs |
| Aufgabe | | Man zeige, dass es in einem schlichten, gerichteten Graphen G = <V,E> immer zwei Knoten x,y [mm] \in [/mm] V, x [mm] \not=y, [/mm] gibt mit dem gleichen Weggrad d+(x) = d+(y), wenn es keinen Knoten x [mm] \in [/mm] V(G) mit Weggrad d+(x) = 0 gibt. |
Ich bitte um Hilfe bei dem Beispiel. Ich weiß zwar, was ein schlichter gerichteter Graph ist und Weggrade, aber ich weiß nicht wie ich die Eigenschaften in der Angabe zeigen soll.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:43 Fr 23.11.2007 | | Autor: | koepper |
Guten Abend Barbara,
> Man zeige, dass es in einem schlichten, gerichteten Graphen
> G = <V,E> immer zwei Knoten x,y [mm]\in[/mm] V, x [mm]\not=y,[/mm] gibt mit
> dem gleichen Weggrad d+(x) = d+(y), wenn es keinen Knoten
> x [mm]\in[/mm] V(G) mit Weggrad d+(x) = 0 gibt.
> Ich bitte um Hilfe bei dem Beispiel. Ich weiß zwar, was ein
> schlichter gerichteter Graph ist und Weggrade, aber ich
> weiß nicht wie ich die Eigenschaften in der Angabe zeigen
> soll.
Angenommen in einem schlichten gerichteten Graphen mit n Knoten hätten alle n Knoten unterschiedlichen Ausgangsgrad und keiner hätte Ausgangsgrad 0. Dann müßte es einen Knoten geben mit Ausgangsgrad größer oder gleich n (denn es gibt offenbar nur n-1 verschiedene Zahlen zwischen 1 und n-1). Aber das ist nicht möglich (wo sollten die vielen Pfeile alle hinzeigen?). Also war die Annahme falsch, was die Behauptung zeigt.
LG
Will
|
|
|
|
