www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Graphentheorie" - Grad von zwei Knoten
Grad von zwei Knoten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Grad von zwei Knoten: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

        
Bezug
Grad von zwei Knoten: Antwort
Status: (Antwort) fertig Status 
Datum: 08:07 Do 24.04.2008
Autor: Al-Chwarizmi


> 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


  


Bezug
                
Bezug
Grad von zwei Knoten: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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 :-)

Bezug
                        
Bezug
Grad von zwei Knoten: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Grad von zwei Knoten: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:40 Do 24.04.2008
Autor: die_conny

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

Bezug
                                        
Bezug
Grad von zwei Knoten: Antwort
Status: (Antwort) fertig Status 
Datum: 13:59 Do 24.04.2008
Autor: Bastiane

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] 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]

Bezug
                                                
Bezug
Grad von zwei Knoten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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 =)

Bezug
                                                
Bezug
Grad von zwei Knoten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:41 Do 24.04.2008
Autor: Al-Chwarizmi

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.



Bezug
                
Bezug
Grad von zwei Knoten: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:20 Do 24.04.2008
Autor: Al-Chwarizmi

gern geschehen;  es gilt also zuerst allfällige Voraussetzungen zu prüfen...

schönen Tag!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]