Schwach zusammenhängend

24.03.2015, 18:55	lilalobina	Auf diesen Beitrag antworten »
Schwach zusammenhängend Edit (mY+): Titel gekürzt! Längere Abschnitte gehören in den Text! Meine Frage: Hallo ich sitze hier vor einer Aufgabe und komme nicht weiter: Sei $\begin{eqnarray} G:=(V, R, \alpha, \omega) \end{eqnarray}$ ein gerichteter, schwach zusammenhängender Graph mit $\begin{eqnarray} \|V\| \geq 2 \end{eqnarray}$ . Zu zeigen: $\begin{eqnarray} \exists v \in V : G - v \end{eqnarray}$ ist schwach zusammenhängend. Bei uns ist schwach zusammenhängend, dass der korrespondierende ungerichtete Graph zusammenhängend ist. Meine Ideen: Mein Beweis bis jetzt: o.E existieren keine Parralelen Pfeile und Schlingen (das Problem überträgt sich in den einfachen Graphen) o.E existiert kein Knoten mit Grad 1 sonst sind wir fertig Betrachte den längsten elementaren Pfad $\begin{eqnarray} P=(v_0, ..., v_k) \end{eqnarray}$ Ist P ein Kreis, können wir den ersten Knoten wählen da $\begin{eqnarray} v_0 \end{eqnarray}$ keine weiteren ein und ausgehenden Kanten hat (sonst ist P nicht maximal). P ist kein Kreis: Hat ein Knoten im Kreis den Grad zwei, so wählen wir diesen, da wir nur den Kreis öffnen, aber keine unzusammenhängenden Gebiete schaffen. Alle Knoten haben Grad größer 3: Mein weiteres Argument ist jetzt, das ich mich für einen Subgraphen der von P wegführt entscheide und wieder von vorne Anfange und am Ende bei einem Kreis landen muss (Graph ist endlich), da ich ja Blätter schon ausgeschlossen habe, also wähle ich den Knoten auf dem Kreis der Grad 2 hat. Was mein ihr? Ist der Weg richtig? Vielen Dank und liebe Grüße kgV: Latex korrigiert. Der End-Tag schreibt sich mit Slash: [/latex]

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »