matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieGraph in Partitionen teilen
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Graph in Partitionen teilen
Graph in Partitionen teilen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graph in Partitionen teilen: Idee
Status: (Frage) beantwortet Status 
Datum: 14:51 Mi 23.10.2013
Autor: Omikron123

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?





        
Bezug
Graph in Partitionen teilen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Graph in Partitionen teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:47 Do 24.10.2013
Autor: Omikron123

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?

Bezug
                        
Bezug
Graph in Partitionen teilen: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                
Bezug
Graph in Partitionen teilen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.)

Bezug
                                        
Bezug
Graph in Partitionen teilen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!

Bezug
                                                
Bezug
Graph in Partitionen teilen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:38 Do 24.10.2013
Autor: Omikron123

Wie würde bei dir der Induktionsschritt aussehen?

Bezug
                                                        
Bezug
Graph in Partitionen teilen: Antwort
Status: (Antwort) fertig Status 
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]

Bezug
                                                                
Bezug
Graph in Partitionen teilen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]