Untergraph?!?

20.06.2005, 16:26

Asgaroth

Untergraph?!?

Mal wieder Thema Graphentheorie...

1. Sei $\begin{eqnarray*} G = (E,K) \end{eqnarray*}$ ein zusammenhängender Graph, $\begin{eqnarray*} a \in G \end{eqnarray*}$ .

Zeigen Sie, daß
es ein aufspannender Untergraph U von G gibt, mit $\begin{eqnarray*} d_U(e) \end{eqnarray*}$ ungerade für
alle $\begin{eqnarray*} e \end{eqnarray*}$ in $\begin{eqnarray*} E \end{eqnarray*}$ \ { $\begin{eqnarray*} a \end{eqnarray*}$ }. (Hinweis: Betrachte $\begin{eqnarray*} Z_i \end{eqnarray*}$ die zusammenhängende Komponenten
von $\begin{eqnarray*} G \end{eqnarray*}$ \ { $\begin{eqnarray*} a \end{eqnarray*}$ }, und wähle zu jedem $\begin{eqnarray*} i \end{eqnarray*}$ $\begin{eqnarray*} a_i \in Z_i \end{eqnarray*}$ , der zu a benachbart
ist.)
2. Für $\begin{eqnarray*} U, a \end{eqnarray*}$ wie in 1 gilt $\begin{eqnarray*} d_U(a) \end{eqnarray*}$ gerade $\begin{eqnarray*} \leftrightarrow |E| \end{eqnarray*}$ ungerade.

MfG und mal wieder auf Hilfe hoffend Asgaroth

20.06.2005, 16:50

JochenX

Auf diesen Beitrag antworten »

hmmm, wollte das eigentlich schon beim anderen thread sagen
ist das nicht eher informatik?

da haben wir ein eigenes board für

20.06.2005, 18:38

sqrt(2)

Auf diesen Beitrag antworten »

Die Graphentheorie wird zwar in der Informatik gerne verwendet (weil man viele Algorithmen darauf zurückführen kann), ist aber ein Teil der Mathematik (siehe http://de.wikipedia.org/wiki/Graphentheorie).

20.06.2005, 21:22

Tobias

Auf diesen Beitrag antworten »

Kannst du mal bitte $\begin{eqnarray*} d_U(e) \end{eqnarray*}$ definieren? Ist das der Grad der Ecke? Ist ein Untergraph bei euch das Tupel (E, K') mit K' ist Teilmenge von K?

Könntest du die Behauptung mal an folgendem Graph belegen:

code:
1: 2: 3: 4: 5: 6: 7: 8:	X--------X \| \| \| \| \| \| \| \| X--------X

Wenn du hier einen aufspannende Graphen brauchst, dann darfst du max. eine Kante weglassen. Welche du weglässt ist aufgrund der Symmetrie egal. Aber wenn man eine weglässt, dann hat man zwei Kanten mit geradem Grad.

Oder habe ich etwas falsch verstanden?

21.06.2005, 13:22

Asgaroth

Auf diesen Beitrag antworten »

Also ich studiere zwar Informatik, aber die Vorlesung heisst Dikrete Algebraische Strukturen und gehört zu den Mathevorlesungen! Der Professor ist auch ein Matheprof. Wo ist denn das Infoboard?

@ Tobias:

Ja, also $\begin{eqnarray*} d_U(E) \end{eqnarray*}$ ist der Grad der Ecke bzw die Valenz.

und "Untergraph" ist bei uns so definiert:

"Ein Graph $\begin{eqnarray*} G' = (E' ; K') \end{eqnarray*}$ heißt Untergraph von $\begin{eqnarray*} G = (E; K) \end{eqnarray*}$ , falls $\begin{eqnarray*} E' \subseteq{} E \end{eqnarray*}$ und $\begin{eqnarray*} K' \subseteq{} K \end{eqnarray*}$ gilt.
Man sagt dann auch, daß $\begin{eqnarray*} G \end{eqnarray*}$ den Graphen $\begin{eqnarray*} G' \end{eqnarray*}$ enthält. $\begin{eqnarray*} G' \end{eqnarray*}$ heißt induzierter Untergraph,
falls zusätzlich $\begin{eqnarray*} K' = K\bigcap \Re_2 (E') \end{eqnarray*}$ gilt, d.h. $\begin{eqnarray*} G' \end{eqnarray*}$ enthält alle zwischen Ecken aus $\begin{eqnarray*} E' \end{eqnarray*}$ in $\begin{eqnarray*} G \end{eqnarray*}$ vorhandenen Kanten. Zu jeder Teilmenge $\begin{eqnarray*} E' \end{eqnarray*}$ gibt es genau einen induzierten Untergraphen
mit Eckenmenge $\begin{eqnarray*} E' \end{eqnarray*}$ , dieser wird mit $\begin{eqnarray*} G[E'] \end{eqnarray*}$ bezeichnet. $\begin{eqnarray*} G' \end{eqnarray*}$ heißt aufspannender Untergraph von $\begin{eqnarray*} G \end{eqnarray*}$ , falls $\begin{eqnarray*} G' \end{eqnarray*}$ ein Untergraph von $\begin{eqnarray*} G \end{eqnarray*}$ mit $\begin{eqnarray*} E = E' \end{eqnarray*}$ ist. (Insbesondere ist $\begin{eqnarray*} G \end{eqnarray*}$ der einzige auf spannende induzierte Untergraph von sich selbst.)"

(Das $\begin{eqnarray*} \Re \end{eqnarray*}$ sieht hier im Script eher aus wie ein P oder B, hab das Symbol aber in meinem TeX Kochbuch nicht gefunden, allerdings ists wohl egal..)

P.S.: Habe mir gerade alles nochmal angeschaut, was ist denn eigentlich das
a? Das ist nur eine Ecke des Graphen für die letztendlich beim Untergraphen $\begin{eqnarray*} d_U(a) \neq ungerade \end{eqnarray*}$ gilt oder?
Ansonsten würde es ja keinen Sinn machen denn an dem Beispiel von Tobias oben sieht man ja, dass wenn man eine Kante wegnimmt nicht alle Ecken des aufspannenden Untergraphen einen ungeraden Grad haben.

Neue Frage »

Antworten »

Untergraph?!?

Verwandte Themen