Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| 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.
|
|
| |
|
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.
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
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...
|
|
|
| |
|
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
|
|
|
| |
|
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
|
|
|
| |
|
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
|
|
|
| |
|
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.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Fr 01.12.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
