Produkt, Zshg, bipartit < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seien G, H Graphen mit $ |V(G)|, [mm] |V(H)|\ge [/mm] 2 $
z. z.:
1) G und H bipartit [mm] \Rightarrow [/mm] $ [mm] G\times [/mm] H $ unzusammenhängend
2) G und H zusammenhängend, G nicht bipartit [mm] \Rightarrow [/mm] $ [mm] G\times [/mm] H $ zusammenhängend |
Hallo!
1) Also bipartit heißt ja nun erstmal, dass die beiden Graphen zwei- oder gar einsfärbbar sind. Nun ist [mm] V(G\times H)=V(G)\times [/mm] V(H)
und (v,w) benachbart zu (x,y) in $ [mm] G\times [/mm] H $, wenn v zu x in G und w zu y in H benachbart ist. Irgendwie muss man jetzt zwei Tupel finden, die nicht benachbart sind....
2) Wie findet man denn nun von (v,w) nach (x,y) einen Kantenzug? Auf jeden Fall gibt es ja einen von v nach x und von w nach y, die sind im Allgemeinen aber nicht gleich lang, sodass man die "zusammenwurschteln" könnte...mmh?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Fr 06.05.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
