| Autor |
Beitrag |
    
Bärbel
| | Veröffentlicht am Montag, den 27. November, 2000 - 09:26: | 
|
Hallo,hab'noch 'ne 2.graphen Aufgabe.
Man zeige,daß in jedem Graphen zwei Knoten gleichen Grades existieren. |
Matroid (Matroid)
| | Veröffentlicht am Dienstag, den 28. November, 2000 - 19:37: |
|
Hallo Bärbel,
da habe ich auch eine Weile überlegt. Aber jetzt kann ich es beweisen.
Die Behauptung gilt nur Für Graphen ohne Schleifen und ohne Mehrfachkanten.
Sei G ein Graph ohne Schleifen und Mehrfachkanten mit n Ecken und k Kanten.
Seien d0,d1,...,dn die Grade der n Ecken.
Da G keine Schleifen und Mehrfachkanten hat, ist der maximale Grad eines Knotens gleich n-1.
Außerdem ist die Summe aller Grade gleich 2k (eine grade Zahl).
Wenn nun alle di verschieden wären, dann bleibt wegen di<n-1 nur eine Lösung, nämlich
0,1,2,...,n-1 für die Grade der n Knoten.
Die Summe der di ist dann aber gleich n*(n-1)/2. Und das ist eine ungerade Zahl. Damit haben wir einen Widerspruch und die Behauptng ist bewiesen.
Gruß
Matroid |
h.ludens
| | Veröffentlicht am Mittwoch, den 29. November, 2000 - 18:32: |
|
Hallo Matroid,
Überlegung am Beispiel :
Gegeben sei ein ungerichteter (also schleifen- und mehrfachkantenfreier) Kreisgraph mit n=5 Knoten und k=5 Kanten.
Sei die max. Gradsumme 2k und der max. Knotengrad n-1
Der max. Knotengrad wäre demnach n-1=4 und die Gradsumme 2k=10 (also wie behauptet gerade).
Nun wäre nach der Rechnung n*(n-1)/2 die Summe der voneinander verschiedenen d = 0+1+2+3+4 also auch 10 (und ebenfalls gerade), auch für andere Beispiele ((9*8)/2=36) erhalte ich gerade Ergebnisse, die Summenfolge alterniert zweistufig zwischen geraden und ungeraden Gliedern.
Da ich also offensichtlich den Hintergrund nicht korrekt verstanden habe, erläutere mir bitte,wie du die Gauss'sche Formel auf dieses Beispiel angewendet, und wo mein Denkfehler stecken könnte. (dies ist definitiv keine ironische Anmerkung sondern eine Bitte um Denkanstösse). |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 29. November, 2000 - 19:48: |
|
Stimmt, da war ich zu schnell. Danke für das Interesse und die Nachfrage.
Das Argument mit der Gauß-Formel muß ich also zurückziehen.
Aber so geht's:
Sei G ein Graph ohne Schleifen und Mehrfachkanten mit n Ecken und k Kanten.
Seien d0,d1,...,dn die Grade der n Ecken.
Da G keine Schleifen und Mehrfachkanten hat, ist der maximale Grad eines Knotens gleich n-1.
Außerdem ist die Summe aller Grade gleich 2k (eine gerade Zahl).
Wenn nun alle di verschieden wären, dann bleibt wegen di<n-1 nur eine Lösung, nämlich
0,1,2,...,n-1 für die Grade der n Knoten.
das ist aber unmöglich, denn da ein Knoten den Grad null hat, ist der maximale Grad jedes anderen Knotens ja nur n-2. |
Bärbel
| | Veröffentlicht am Donnerstag, den 30. November, 2000 - 19:48: |
|
Vielen Dank euch beiden,ohne euch wäre ich da nie drauf gekommen |
h.ludens
| | Veröffentlicht am Freitag, den 01. Dezember, 2000 - 06:55: |
|
Mir gefällt es so auch besser, dankeschön |
|
