www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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
Dt. Schulen im Ausland: Mathe-Seiten:

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

Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:47 Di 28.11.2006
Autor: informatikmaus

Aufgabe
Für n [mm] \in \IN [/mm] mit n [mm] \ge [/mm] 2 sei der Graph [mm] G_{n} [/mm] wie folgt definiert:
Knotenmenge von [mm] G_{n} [/mm] ist die Menge aller n-Tupel [mm] (x_{1},....,x_{n} [/mm] mit [mm] x_{i} \in [/mm] {0,1} für i = 1, ..., n. Zwei Knoten von [mm] G_{n} [/mm] sind genau dann durch eine Kante verbunden, wenn sich die entsprechenden n-Tupel an genau zwei Stellen unterscheiden.

a) Welchen Grad hat jeder Knoten von [mm] G_{n}? [/mm] (Kurze Begründung)

b) Wie viele Knoten und wie viele Kanten hat [mm] G_{n}? [/mm]

c) Man gebe eine (kurze) Begründung, wieso die Graphen [mm] G_{n} [/mm] für n [mm] \ge [/mm] 4 nicht planar sind.

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

meine ansätze zu dieser aufgabe:

würden zwei Knoten von [mm] G_{n} [/mm] genau dann durch eine Kante verbunden, wenn sich die entsprechenden n-Tupel an genau EINER (und nicht zwei) Stellen unterscheiden...

dann weiss ich dass a) der Grad jedes Knotens n ist ....

b) der Graph [mm] 2^{n} [/mm] Knoten hat und [mm] n*2^{n-1} [/mm] Kanten.

meine frage nun, wie komme ich von diesen formeln zu den formeln für den Graph dessen knoten dann mit einer kante verbunden sind, wenn sie sich genau an ZWEI und nicht einer Stelle unterscheiden?

zu c) warum diese nicht planar sind, dafür abe ich noch keine KURZE begründung gefunden.

        
Bezug
Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 15:02 Di 28.11.2006
Autor: mathiash

Moin zusammen,

[mm] G_n [/mm] hat offenbar genau [mm] 2^n [/mm] Knoten, und der Grad eines Knotens ist doch nichts anderes als die Zahl der zweielementigen Teilmengen von [mm] \{1,\ldots , n\}, [/mm] also

gleich [mm] \vektor{n\\2}, [/mm]

die Zahl der Kanten ist also gleich [mm] \frac{1}{2}\cdot 2^n\cdot [/mm] Knotengrad,

das kannst Du selber weiter ausrechnen.

Zur Nichtplanarität:

es reicht, den Fall n=4 zu betrachten, da offenbar der auf der Knotenmenge

[mm] \{(x_1,\ldots , x_4,0,\ldots , 0)\in\{0,1\}^n|x_1,\ldots , x_4\in\{0,1\}\} [/mm]

induzierte Teilgraph von [mm] G_n [/mm] isomorph zu [mm] G_4 [/mm] ist.

Nun musst Du also im [mm] G_4 [/mm] einen Teilgraphen finden, der [mm] K_{3,3} [/mm] oder [mm] K_5 [/mm] als Minor hat.

Gruss,

Mathias


> Für n [mm]\in \IN[/mm] mit n [mm]\ge[/mm] 2 sei der Graph [mm]G_{n}[/mm] wie folgt
> definiert:
>  Knotenmenge von [mm]G_{n}[/mm] ist die Menge aller n-Tupel
> [mm](x_{1},....,x_{n}[/mm] mit [mm]x_{i} \in[/mm] {0,1} für i = 1, ..., n.
> Zwei Knoten von [mm]G_{n}[/mm] sind genau dann durch eine Kante
> verbunden, wenn sich die entsprechenden n-Tupel an genau
> zwei Stellen unterscheiden.
>  
> a) Welchen Grad hat jeder Knoten von [mm]G_{n}?[/mm] (Kurze
> Begründung)
>  
> b) Wie viele Knoten und wie viele Kanten hat [mm]G_{n}?[/mm]
>  
> c) Man gebe eine (kurze) Begründung, wieso die Graphen
> [mm]G_{n}[/mm] für n [mm]\ge[/mm] 4 nicht planar sind.
>  Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
>  
> meine ansätze zu dieser aufgabe:
>  
> würden zwei Knoten von [mm]G_{n}[/mm] genau dann durch eine Kante
> verbunden, wenn sich die entsprechenden n-Tupel an genau
> EINER (und nicht zwei) Stellen unterscheiden...
>  
> dann weiss ich dass a) der Grad jedes Knotens n ist ....
>  
> b) der Graph [mm]2^{n}[/mm] Knoten hat und [mm]n*2^{n-1}[/mm] Kanten.
>  
> meine frage nun, wie komme ich von diesen formeln zu den
> formeln für den Graph dessen knoten dann mit einer kante
> verbunden sind, wenn sie sich genau an ZWEI und nicht einer
> Stelle unterscheiden?
>  
> zu c) warum diese nicht planar sind, dafür abe ich noch
> keine KURZE begründung gefunden.

Bezug
                
Bezug
Graphen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:03 Di 28.11.2006
Autor: informatikmaus

vielen dank das du meinem gehirn auf die sprünge geholfen hast mathias :)

Zahl der Kanten ist also gleich  [mm] \frac{1}{2}\cdot 2^n\cdot [/mm]  Knotengrad

wenn man das weiter ausrechnet ist das dann

[mm] \bruch{2^{n}*n*(n-1)}{2} [/mm]  ?

"es reicht, den Fall n=4 zu betrachten, da offenbar der auf der Knotenmenge

$ [mm] \{(x_1,\ldots , x_4,0,\ldots , 0)\in\{0,1\}^n|x_1,\ldots , x_4\in\{0,1\}\} [/mm] $

induzierte Teilgraph von $ [mm] G_n [/mm] $ isomorph zu $ [mm] G_4 [/mm] $ ist.

Nun musst Du also im $ [mm] G_4 [/mm] $ einen Teilgraphen finden, der $ [mm] K_{3,3} [/mm] $ oder $ [mm] K_5 [/mm] $ als Minor hat. "

wir hatten die themen induzierter teilgraph, isomorph und minor nicht, aber danke für den ansatz, ich werde mich da mal durcharbeiten.

Gruß Sarah



Bezug
                        
Bezug
Graphen: Antwort und Frage
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:51 Di 28.11.2006
Autor: Bastiane

Hallo informatikmaus!

> vielen dank das du meinem gehirn auf die sprünge geholfen
> hast mathias :)

Das macht er doch gerne... ;-)
  

> Zahl der Kanten ist also gleich  [mm]\frac{1}{2}\cdot 2^n\cdot[/mm]  
> Knotengrad
>  
> wenn man das weiter ausrechnet ist das dann
>  
> [mm]\bruch{2^{n}*n*(n-1)}{2}[/mm]  ?

Mmh, also ich erhalte: [mm] \bruch{1}{2}*2^n*\vektor{n\\2}=2^{n-1}*\bruch{n!}{2!(n-2)!}=2^{n-1}*\bruch{n(n-1)}{2}=2^{n-2}(n^2-n) [/mm]
  

> "es reicht, den Fall n=4 zu betrachten, da offenbar der auf
> der Knotenmenge
>  
> [mm]\{(x_1,\ldots , x_4,0,\ldots , 0)\in\{0,1\}^n|x_1,\ldots , x_4\in\{0,1\}\}[/mm]
>  
> induzierte Teilgraph von [mm]G_n[/mm] isomorph zu [mm]G_4[/mm] ist.
>  
> Nun musst Du also im [mm]G_4[/mm] einen Teilgraphen finden, der
> [mm]K_{3,3}[/mm] oder [mm]K_5[/mm] als Minor hat. "
>  
> wir hatten die themen induzierter teilgraph, isomorph und
> minor nicht, aber danke für den ansatz, ich werde mich da
> mal durcharbeiten.

Wenn ich mich recht erinnere, bedeutet isomorph einfach nur, dass du quasi den gleichen Graph nur anders angeordnet zeichnest. Das heißt, du nummerierst beispielsweise die Knoten durch, damit du weißt, welcher Knoten welcher ist, und dann ist es egal, ob du Knoten 1 nach oben auf dein Blatt Papier oder nach links oder auf die Rückseite (;-)) zeichnest, solange du ihn mit den gleichen Kanten verbindest. So kannst du ja z. B. den [mm] K_4 [/mm] planar zeichnen, auch wenn man ihn wahrscheinlich meistens so zeichnen würde, dass man die erstmal ein Quadrat zeichnet und dann noch zwei Diagonalen. Dann schneiden sich die beiden Diagonalen aber in der Mitte, und um ihn planar zu zeichnen, musst du eine Diagonale nicht als Diagonale zeichnen, sondern "außen rum", wenn du verstehst, was ich meine!? :-)

Und in dem Fall hier dürfte es wohl so sein (was genau "induziert" bedeutet, weiß ich auch nie, aber ich glaube, es ist einfach der Teilgraph, der halt nur einen Teil der Knoten enthält und einen Teil der Kanten), dass du den Graph [mm] \{(x_1,\ldots , x_4,0,\ldots , 0)\in\{0,1\}^n|x_1,\ldots , x_4\in\{0,1\}\} [/mm] genauso zeichnen kannst wie den [mm] K_4, [/mm] denn er ist ja quasi nur der [mm] K_4 [/mm] nur mit ein paar Komponenten mehr, die aber alle =0 sind. Und schätzungsweise ist dann das Prinzip dieses Beweises, dass der Graph nicht planar sein kann, wenn er einen nicht planaren Teilgraphen enthält (das ist ja auch irgendwie logisch ;-)), und wenn der Teilgraph schon den [mm] K_{3,3} [/mm] oder den [mm] K_5 [/mm] enthält, dann kann dieser ja auch nicht planar sein.

Aber was ein Minor ist, das kann Mathias mir hier am besten auch gleich mal erklären. Da muss ich in der Vorlesung irgendwie geschlafen haben. :-)

Viele Grüße
Bastiane
[cap]

Bezug
                                
Bezug
Graphen: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 22:26 Di 28.11.2006
Autor: informatikmaus

danke :) ich werde meine rechnung noch mal überprüfen

hat den dieser graph einen nicht planaren teilgraphen? [mm] K_{4} [/mm] ist doch planar... wenn man die diagonale aussen rum zeichnet...

Bezug
                                        
Bezug
Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 23:35 Di 28.11.2006
Autor: Bastiane

Hallo informatikmaus!

> danke :) ich werde meine rechnung noch mal überprüfen
>  
> hat den dieser graph einen nicht planaren teilgraphen?
> [mm]K_{4}[/mm] ist doch planar... wenn man die diagonale aussen rum
> zeichnet...  

Ich glaube, es ging hier nicht um den [mm] K_4 [/mm] sondern um den [mm] G_4, [/mm] und der hat ja nach Teilaufgabe a) (oder wars b)?) [mm] 2^n [/mm] Knoten. Sorry, falls ich hier etwas verwechselt haben sollte.

Viele Grüße
Bastiane
[cap]

Bezug
                                                
Bezug
Graphen: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 09:59 Mi 29.11.2006
Autor: informatikmaus

und [mm] G_{4} [/mm] mit [mm] 2^{n} [/mm] Knoten ist nicht planar?

welche kurze begründung dafür gibt es.

entschuldigung dass ich da nich durchsteige

Bezug
                                                        
Bezug
Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:10 Mi 29.11.2006
Autor: Bastiane

Hallo informatikmaus!

> und [mm]G_{4}[/mm] mit [mm]2^{n}[/mm] Knoten ist nicht planar?
>  
> welche kurze begründung dafür gibt es.

Naja, das ist ja gerade zu zeigen, dass das nicht planar ist. Und wie Mathias schon sagte, kannst du das machen, indem du zeigst, dass dieser Graph entweder den [mm] K_{5} [/mm] oder den [mm] K_{3,3} [/mm] als Minor enthält. Allerdings habe ich Mathias weitere Versuche, einen solchen zu finden, heute gesehen, es sah nicht danach aus, als würde er in nächster Zeit noch einen finden... Hast du dir mal den [mm] G_4 [/mm] aufgemalt? Ansonsten mach das mal. Und dann forsche nochmal nach, was denn Minor bedeutet, und dann kannst du, wenn du Lust hast, dich ja mal auf die Suche nach dem [mm] K_{5} [/mm] oder dem [mm] K_{3,3} [/mm] machen. Ich hatte dazu keine Lust, das war mir etwas zu unübersichtlich und ich hatte keine Idee, wie man das strukturiert machen könnte.
Wenn ihr allerdings das Wort Minor noch nicht hattet, geht es vielleicht auch anders - was habt ihr denn überhaupt zur Planarität gemacht? Wie zeigt ihr, dass ein Graph planar ist oder nicht?

Viele Grüße
Bastiane
[cap]

Bezug
                                                                
Bezug
Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:49 Mi 29.11.2006
Autor: informatikmaus

ich habe das jetzt so gemacht: nach dieser regel:

für einen planaren graphen G=(V,E) mit |V| [mm] \ge [/mm] 3 Knoten gilt |E| [mm] \le [/mm] 3 * |V| - 6.

[mm] G_{4} [/mm] hat 16 Knoten und 48 Kanten

somit 48 [mm] \le [/mm] 42 was nicht stimmt.

und da [mm] G_{4} [/mm] ein Teilgraph von [mm] G_{n} [/mm] mit n > 4 ist und nicht planar ist, sind somit auch alle anderen [mm] G_{n} [/mm] mit n > 4 nicht planar.



Bezug
                                                        
Bezug
Graphen: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 10:20 Fr 01.12.2006
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de