Grad von zwei Knoten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:48 Do 24.04.2008 | | Autor: | dieanne |
| Aufgabe | | Zeigen Sie, dass in einem Graphen G=(V,E) zwei Knoten v,w [mm] \in [/mm] V existieren, für die d(v)=d(w) gilt. |
Hallo,
für mich ist dieses Thema noch neu. Die Aussage ist mir völlig klar und ich kann mir auch ungefähr vorstellen wieso das gilt. Aber wie "beweise" ich sowas mit kurzen knappen Worten? Kann mir das jemand bei dieser Aussage vielleicht mal zeigen? Ich habe das Problem nämlich noch an anderen Stellen.
Vielen Dank!
|
|
| |
|
> Zeigen Sie, dass in einem Graphen G=(V,E) zwei Knoten v,w
> [mm]\in[/mm] V existieren, für die d(v)=d(w) gilt.
> Hallo,
>
> für mich ist dieses Thema noch neu. Die Aussage ist mir
> völlig klar und ich kann mir auch ungefähr vorstellen wieso
> das gilt. Aber wie "beweise" ich sowas mit kurzen knappen
> Worten? Kann mir das jemand bei dieser Aussage vielleicht
> mal zeigen? Ich habe das Problem nämlich noch an anderen
> Stellen.
>
> Vielen Dank!
Hallo dieanne,
stimmt die Behauptung denn wirklich? (fehlt vielleicht noch eine zusätzliche Voraussetzung?)
Der Grad eines Knotens ist doch die Anzahl der von ihm ausgehenden Kanten, oder...
Ich stelle mir zwei (Gegen-) Beispiele vor:
1.) Der Graph mit [mm] V = [ v_1 ][/mm] und [mm]E = [ ][/mm], d.h. ein einziger isolierter Punkt, ohne Kanten.
Es gibt nur diesen Knoten mit [mm]d(v_1) = 0[/mm] . Kein zweiter Punkt vorhanden.
Falls dies gar zu einfach sein sollte, ein Beispiel mit drei Knoten:
2.) [mm]V = [ v_1, v_2, v_3 ][/mm] und E = [mm][ e_1, e_2, e_3, e_4 ][/mm], wobei an den einzelnen Knoten die folgenden Kanten hängen:
[mm] v_1: e_1 [/mm] Grad 1
[mm] v_2: e_1, e_2, e_3 [/mm] Grad 3
[mm] v_3: e_2, e_3, e_4 [/mm] (doppelt) Grad 4
[mm] (e_4 [/mm] sei eine "Schleife")
(oder sind solche Beispiele verboten?)
Gruß al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:16 Do 24.04.2008 | | Autor: | dieanne |
Ja, wir haben den Grad eines Knotens als die Summe der eingehenden und ausgehenden Kanten definiert.
In der Vorlesung wurde die Vereinbarung getroffen, dass wir immer von endlichen Graphen ohne parallele Kanten und Schlaufen sprechen, also zählt dein zweites Beispiel nicht.
Was mit dem isolierten Punkt ist, weiß ich nicht. Zählt es denn als Graph, wenn es keine Kanten hat?
Wie könnte ich das den sonst beweisen? Daher die Aufgabenstellung das ja verlangt wird es sicherlich eine kurze Begründung geben, aber das mit dem isolierten Punkt frage ich heute in der Vorlesung nochmal 
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:23 Do 24.04.2008 | | Autor: | Zaed |
Hallo, ich würde hier versuchen mit dem Schubfachrinzip vorzugehen. Betrachte einen Graphen mit n Knoten, so dass jeder Knoten einen anderen Grad hat. D.h. Knoten 1 hat den Grad 0 , Knoten 2 den Grad 1, ..., Knoten n hat den Grad n-1. Was fällt nun auf? Kann vielleicht etwas mit Knoten 1 nicht stimmen, wenn Knoten n den Grad n-1 hat? :D
Ich bin hier davon ausgegangen, dass ihr ungerichtete Graphen ohne Schlaufen betrachtet! Für gerichtete Graphen stimmt die Aussage nicht (schließlich zählt man da eingehende und ausgehende Kanten) ^^
Gruß, Robert
|
|
|
| |
|
Hallo! ich sitze vor der selben Aufgabe ;)
also ich verstehe, wie du das mit dem schubfachprinzip meinst. denn wenn ein knoten den grad n-1 hat und ein anderer den grad null, das geht nicht, also das schließt sich aus (denn der knoten mit grad n-1 müsste ja auch mit dem isolierten knoten verbunden sein). somit gibt es nur n-1 kategorien, aber n knotengrade, und somit müssen laut schubfachprinzip in einer kategorie 2 knoten sein.
jetzt war meine überlegung, ob diese begründung sich wirklich für jeden grafen anwenden lässt? also wenn ich nun davon ausgehe, dass ich keinen knoten mit grad 0 oder grad n-1 etc. habe... kann ich dann einfach sagen, dass es dann ja noch weniger kategorien geben muss, und somit laut verallgemeinertem schubfachprinzip eben wieder mindestens in einer kategorie mindestens 2 knotengrade enthalten sind?
vielen dank im voraus, die_conny
|
|
|
| |
|
Hallo die_conny!
> jetzt war meine überlegung, ob diese begründung sich
> wirklich für jeden grafen anwenden lässt? also wenn ich nun
Den Graph in der Mathematik schreibt man übrigens mit "ph". Ich glaube nicht, dass sich das mit der Rechtschreibreform geändert hat. 
> davon ausgehe, dass ich keinen knoten mit grad 0 oder grad
> n-1 etc. habe... kann ich dann einfach sagen, dass es dann
> ja noch weniger kategorien geben muss, und somit laut
> verallgemeinertem schubfachprinzip eben wieder mindestens
> in einer kategorie mindestens 2 knotengrade enthalten
> sind?
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]") Wir haben ja exakt n Knoten und deswegen auch exakt n Knotengrade, aber egal, wie viele Kanten wir haben, wir haben höchstens n-1 verschiedene Knotengrade. Deswegen passt das nicht.
Das ist eben das Schubfachprinzip, wenn du n Sachen verteilen willst, dann ist es egal, ob du n-1 Schubladen oder deutlich weniger hast, du musst immer irgendwo mehr als eins rein tun.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:05 Do 24.04.2008 | | Autor: | die_conny |
vielen dank für die ganz schnelle antwort!!!
okay, ich denke, ich hab es jetzt verstanden =)
|
|
|
| |
|
hallo, ich hab nochmals in die Fortsetzung der Diskussion reingeschaut
Ich denke, jetzt wird auch klar, warum die folgenden 3 Voraussetzungen für den Beweis wesentlich sind:
1.) der Graph muss mindestens 2 Knoten haben
2.) zwischen 2 beliebigen Knoten [mm] v_i [/mm] und [mm] v_j [/mm] gibt es höchstens eine Verbindungskante
3.) Loops (Kante von [mm] v_i [/mm] nach [mm] v_i) [/mm] sind verboten
Wegen Voraussetzung 2.) können von einem Knoten [mm] v_i [/mm] höchstens (n-1) Kanten abgehen (nämlich maximal eine zu jedem der übrigen Knoten). Dies erst macht die Anwendung des Schubfachprinzips möglich. Allerdings muss man sich noch klar machen, weshalb ein Graph z.B. mit 5 Knoten und den Graden 0,1,2,3,4 (das wären 5 verschiedene Grade!) unmöglich ist. Isolierte Punkte also Punkte vom Grad 0 auch noch grundsätzlich auszuschliessen ist wohl nicht notwendig. In wichtigen Beweisen der Graphentheorie (z.B. Eulerscher Polyedersatz) verwendet man ja Induktion mit Verankerung beim trivialen Graph bestehend aus einem isolierten Punkt.
Gruß al-Ch.
|
|
|
| |
|
gern geschehen; es gilt also zuerst allfällige Voraussetzungen zu prüfen...
schönen Tag!
|
|
|
|
