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 Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

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

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieGraph in Partitionen teilen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
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.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]