Graph in Partitionen teilen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei G ein Graph. Zeige das die Knotenmenge von G eine Partition [mm] V=V_1\cup V_2 [/mm] b bestzt mit der Eigenschaft [mm] e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G) [/mm] |
Mir ist diese Folgerung unklar.
http://imageshack.us/photo/my-images/855/m8bg.jpg/
Hier habe ich einen Graphen gezeichnet mit 4 Knoten und einer Partition
Dann gilt aber [mm] 1+1\le [/mm] 1/2*3 was definitiv falsch ist. Wie ist diese Aufgabe nun zu verstehen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:41 Do 24.10.2013 | | Autor: | tobit09 |
Hallo Omikron123!
> Sei G ein Graph. Zeige das die Knotenmenge von G eine
> Partition [mm]V=V_1\cup V_2[/mm] b bestzt mit der Eigenschaft
> [mm]e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G)[/mm]
e(G) bezeichnet die Anzahl der Kanten von G?
> Mir ist diese
> Folgerung unklar.
>
> http://imageshack.us/photo/my-images/855/m8bg.jpg/
>
> Hier habe ich einen Graphen gezeichnet mit 4 Knoten und
> einer Partition
>
> Dann gilt aber [mm]1+1\le[/mm] 1/2*3 was definitiv falsch ist. Wie
> ist diese Aufgabe nun zu verstehen?
Die von dir gewählte Partition besitzt nicht die Eigenschaft [mm] $e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G)$.
[/mm]
Aber z.B. die Partition mit [mm] $V_1=\{v_1,v_4\}$ [/mm] und [mm] $V_2=\{v_2,v_3\}$ [/mm] sehr wohl.
Die Behauptung ist nicht, dass JEDE Partition die Eigenschaft [mm] $e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G)$ [/mm] hat, sondern nur, dass es zu jedem Graph MINDESTENS EINE Partition mit dieser Eigenschaft gibt.
Viele Grüße
Tobias
|
|
|
| |
|
Du hast vollkommen recht, diesen Fall habe ich übersehen.
Nun zum Beweis dieser Aussage: Ich habe mir überlegt ich versuche einen Algorithmus zu konstruieren der diese gewünschte Ungleichung immer erfüllt, also einen Algorithmus der nach einem bestimmten Muster zwei Partitionen von Knoten bestimmt.
Ich denke es müsste so funktionen, dass ich damit beginne den Grad der Knoten festzulegen. Danach teile ich Knoten in Kategorien ein, abhängig vom Grad der Knoten, also ich suche alle Knoten mit Grad 1, mit Grad 2 etc. Gehen wir davon aus, dass der maximale Grad gleich i ist. Dann wähle ich zwei Partitionen so, dass ich in die erste Menge alle Knoten mit Grad 1,...,i/2 gebe und und die zweite Partition alle Knoten mit Grad i/2+1,...,n.
Im Falle das i ungerade ist, nehme ich einfach den abgerundeten Wert.
Wie lässt sch jetzt überprüfen ob die Ungleichung gilt, bzw. ist der Algorithmus fehlerhaft?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:42 Do 24.10.2013 | | Autor: | tobit09 |
Vorweg schon einmal zwei Nachfragen:
Sind bei euch Mehrfachkanten zugelassen?
Dürfen Kanten auch von einem Knoten zu ihm selbst führen?
> Nun zum Beweis dieser Aussage: Ich habe mir überlegt ich
> versuche einen Algorithmus zu konstruieren der diese
> gewünschte Ungleichung immer erfüllt, also einen
> Algorithmus der nach einem bestimmten Muster zwei
> Partitionen von Knoten bestimmt.
>
> Ich denke es müsste so funktionen, dass ich damit beginne
> den Grad der Knoten festzulegen. Danach teile ich Knoten in
> Kategorien ein, abhängig vom Grad der Knoten, also ich
> suche alle Knoten mit Grad 1, mit Grad 2 etc. Gehen wir
> davon aus, dass der maximale Grad gleich i ist. Dann wähle
> ich zwei Partitionen so, dass ich in die erste Menge alle
> Knoten mit Grad 1,...,i/2 gebe und und die zweite Partition
> alle Knoten mit Grad i/2+1,...,n.
>
> Im Falle das i ungerade ist, nehme ich einfach den
> abgerundeten Wert.
>
> Wie lässt sch jetzt überprüfen ob die Ungleichung gilt,
> bzw. ist der Algorithmus fehlerhaft?
Letzteres. Betrachte etwa einen Graphen mit drei Knoten und einer Kante zwischen zwei der drei Knoten.
Man kann die Behauptung z.B. per Induktion nach der Knotenzahl $|V|$ zeigen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:01 Do 24.10.2013 | | Autor: | Omikron123 |
Nein, Mehrfachkanten sind nicht erlaubt (Damit meinst du z.B bei zwei Knoten [mm] v_1 [/mm] und [mm] v_2 [/mm] das es mehr als eine Kante zwischen diesen gibt, richtig?). Kanten dürfen auch nicht zu sich selbst führen (also keine Schlingen etc.)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:02 Do 24.10.2013 | | Autor: | tobit09 |
> Nein, Mehrfachkanten sind nicht erlaubt (Damit meinst du
> z.B bei zwei Knoten [mm]v_1[/mm] und [mm]v_2[/mm] das es mehr als eine Kante
> zwischen diesen gibt, richtig?). Kanten dürfen auch nicht
> zu sich selbst führen (also keine Schlingen etc.)
Genauso meinte ich das. Danke für die Aufklärung!
|
|
|
| |
|
Wie würde bei dir der Induktionsschritt aussehen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:09 Fr 25.10.2013 | | Autor: | tobit09 |
> Wie würde bei dir der Induktionsschritt aussehen?
Gelte die Behauptung für alle Graphen $G$ mit $|V|=n$ für ein festes [mm] $n\in\IN$.
[/mm]
Sei nun $G$ ein Graph mit $|V|=n+1$.
Wir müssen eine Partition [mm] $V=V_1\cup V_2$ [/mm] finden mit [mm] $e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G)$.
[/mm]
Da [mm] $|V|=n+1\ge [/mm] 1$ existiert ein Knoten [mm] $v\in [/mm] V$.
Sei [mm] $V':=V\setminus\{v\}$.
[/mm]
Also $|V'|=n$.
Nach Induktionsvoraussetzung angewandt auf $G':=G[V']$ existiert eine Partition [mm] $V'=V_1'\cup V_2'$ [/mm] mit
(1) [mm] $e(G'[V_1'])+e(G'[V_2'])\le\bruch12e(G')$.
[/mm]
Es gilt dabei
(2) [mm] $G'[V_1']=G[V_1']$ [/mm] und [mm] $G'[V_2']=G[V_2]$.
[/mm]
Außerdem gilt
(3) [mm] $e(G)=e(G')+\operatorname{grad}(v)$,
[/mm]
wie wir nun zeigen wollen:
Sei $E'$ die Kantenmenge von $G'$, $E$ die Kantenmenge von $G$ und [mm] $E_v$ [/mm] die Menge der Kanten von $G$, die den Knoten $v$ als einen der beiden zugehörigen Knoten haben.
Dann gilt [mm] $E=E'\cup E_v$ [/mm] und die Vereinigung ist disjunkt.
Damit folgt wie gewünscht [mm] $e(G)=|E|=|E'|+|E_v|=e(G')+\operatorname{grad}(v)$.
[/mm]
Sei für $i=1,2$ jeweils [mm] $E_{v,V_i}$ [/mm] die Menge der Kanten von $G$, die $v$ mit einem Knoten aus [mm] $V_i$ [/mm] verbinden.
Dann gilt [mm] $E_v=E_{v,V_1}\cup E_{v,V_2}$ [/mm] und diese Vereinigung ist disjunkt.
Somit folgt
(4) [mm] $\operatorname{grad}(v)=|E_v|=|E_{v,V_1}|+|E_{v,V_2}|$.
[/mm]
Sei für [mm] $V''\subseteq [/mm] V$ mit [mm] $E_{V''}$ [/mm] die Menge der Kanten innerhalb von $V''$ bezeichnet.
Also
(5) [mm] $|E_{V''}|=e(G[V''])$.
[/mm]
Es gilt für $i=1,2$ jeweils [mm] $E_{V_i'\cup\{v\}}=E_{V_i'}\cup E_{v,V_i'}$ [/mm] und diese Vereinigung ist disjunkt.
Somit folgt
(6) [mm] $|E_{V_i'\cup\{v\}}|=|E_{V_i'}|+|E_{v,V_i'}|$.
[/mm]
Es existiert ein [mm] $i\in\{1,2\}$ [/mm] mit
(7) [mm] $|E_{v,V_i'}|\le\bruch12\operatorname{grad}(v)$,
[/mm]
denn sonst wäre [mm] $|E_{v,V_1'}|,|E_{v,V_2'}|>\bruch12\operatorname{grad}(v)$ [/mm] und somit [mm] $|E_{v_1'}|+|E_{v,V_2}|>\bruch12\operatorname{grad}(v)+\bruch12\operatorname{grad}(v)=\operatorname{grad}(v)$, [/mm] was (4) widerspräche.
Sei $j$ die von $i$ verschiedene der beiden Zahlen $1$ und $2$.
Dann setzen wir
(8) [mm] $V_1:=V_i'\cup\{v\}$
[/mm]
und
(9) [mm] $V_2:=V_j'$.
[/mm]
Also gilt [mm] $V=V'\cup\{v\}=V_1'\cup V_2'\cup{v}=V_i'\cup V_j'\cup\{v\}=V_1\cup V_2$ [/mm] und diese Vereinigungen sind disjunkt.
Wir zeigen nun mittels (1) bis (9), dass wie gewünscht
[mm] $e(G[V_1])+e(G[V_2])\le \bruch{1}{2}e(G)$
[/mm]
gilt:
[mm] $e(G[V_1])+e(G[V_2])$
[/mm]
(5) [mm] $=|E_{V_1}|+|E_{V_2}|$
[/mm]
(8),(9) [mm] $=|E_{V_i'\cup\{v\}}|+|E_{V_j'}|$
[/mm]
(6) [mm] $=|E_{V_i'}|+|E_{v,V_i'}|+|E_{V_j'}|$
[/mm]
(7) [mm] $\le (|E_{V_i'}|+|E_{V_j'}|)+\bruch12\operatorname{grad}(v)$
[/mm]
[mm] $=(|E_{V_1'}|+|E_{V_2'}|)+\bruch12\operatorname{grad}(v)$
[/mm]
(5) [mm] $=(e(G[V_1']+e(G[V_2']))+\bruch12\operatorname{grad}(v)$
[/mm]
(2) [mm] $=(e(G'[V_1'])+e(G'[V_2']))+\bruch12\operatorname{grad}(v)$
[/mm]
(1) [mm] $\le\bruch12 e(G')+\bruch12\operatorname{grad}(v)$
[/mm]
[mm] $=\bruch12(e(G')+\operatorname{grad}(v))$
[/mm]
(3) [mm] $=\bruch12e(G)$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:40 Fr 25.10.2013 | | Autor: | Omikron123 |
Ich habe keine solche Antwort erwartete, vielen Dank für diesen ausführlichen Beweis, hat mir sehr weitergeholfen.
|
|
|
|
