Zusammenhang < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei G = (V, K, [mm] \delta [/mm] : K [mm] \to [/mm] V [mm] \bar{x} [/mm] V) ein vollstaendiger Graph und es sei K = [mm] K_1 \cup K_2 [/mm] eine Zerlegung seiner Kantenmenge K.
Zeigen Sie:
[mm] G\cap K_1 [/mm] oderG [mm] \cap K_2 [/mm] ist zusammenhaengend. |
Hi!
Okay, ich weiss was zusammenhaengeng und was vollstaendig ist:
Ein Graph heisst zusammenhaengend, wenn je zwei Knoten verbindbar sind.
Ein Graph heisst vollstaendig, wenn er knotenregulaer vom Grad |V|-1 ist.
Aber da hoert es auch schon auf.
Wie fange ich ueberhaupt an??? Alles Hinweise wuerden mir helfen.
Vielen Dank im Voraus.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:19 Sa 28.10.2006 | | Autor: | Bastiane |
Hallo margarita,
> Es sei G = (V, K, [mm]\delta[/mm] : K [mm]\to[/mm] V [mm]\bar{x}[/mm] V) ein
> vollstaendiger Graph und es sei K = [mm]K_1 \cup K_2[/mm] eine
> Zerlegung seiner Kantenmenge K.
> Zeigen Sie:
> [mm]G\cap K_1[/mm] oderG [mm]\cap K_2[/mm] ist zusammenhaengend.
> Hi!
> Okay, ich weiss was zusammenhaengeng und was vollstaendig
> ist:
> Ein Graph heisst zusammenhaengend, wenn je zwei Knoten
> verbindbar sind.
> Ein Graph heisst vollstaendig, wenn er knotenregulaer vom
> Grad |V|-1 ist.
> Aber da hoert es auch schon auf.
> Wie fange ich ueberhaupt an??? Alles Hinweise wuerden mir
> helfen.
Evtl. würde ein Widerspruchsbeweis helfen: Angenommen, weder [mm] G\cap K_1 [/mm] noch [mm] G\cap K_2 [/mm] ist zusammenhängend. Was müsste dann gelten? Da könnte dann nachher ein Widerspruch rauskommen und die Aussage wäre bewiesen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo und guten Morgen,
Bastianes Vorschlag aufgreifend könntest Du zB betrachten:
Wenn weder [mm] G\cap K_1 [/mm] noch [mm] G\cap K_2 [/mm] zush. sind, so seien
[mm] (V_1,V_2) [/mm] ein Cut, von dem keine Kante in [mm] K_1 [/mm] ist,
[mm] (U_1,U_2) [/mm] ein Cut, von dem keine Kante in [mm] K_2= \{\{u,v\}|u,v\in V,u\neq v\}\setminus K_1 [/mm] ist,
betrachte dann die vier Mengen [mm] V_i\cap U_j, i,j\in \{1,2\}. [/mm] Zeichne Dir zB V als Rechteck, den Cut [mm] (V_1,V_2) [/mm] als horizontale Linie
und den anderen Cut als vertikale Linie, so dass die vier Teilmengen die Mengen [mm] U_i\cap V_j [/mm] sind.
Gruss,
Mathias
|
|
|
|
