Graphentheorie

09.07.2009, 18:27

BanachraumK_5

Graphentheorie

Hallo ich muss derzeit ein wenig Graphentheorie lernen, nun habe ich auf einem Übungsblatt von meinem Prof. zwei Aufgabe wo ich mir unsicher bin:

Aufgabe 1:

$\begin{eqnarray*} Gibt\ es\ einen\ Graphen\ mit\ den\ Knotengraden\ 1,1,2,4 \end{eqnarray*}$

Jetzt verstehe ich bei der Aufgabe erstmal eins nicht: Kann ich vorraussetzen das die Anzahl der Knoten gleich 4 ist? Oder muss ich annehmen, dass es mehr gibt und eben nur von 4 Stück die Grade bekannt sind??

Falls ich nun annehmen darf, das es nur 4 Knoten gibt, dann ist das doch eh ein Widerspruch da für jeden Grad ja maximal gilt $\begin{eqnarray*} deg(v) = n-1 \end{eqnarray*}$ ?????

Die zweite Aufgabe enthält ein ähnliches Problem, deshalb poste die wenn ihr mir geholfen habt.

Danke.

09.07.2009, 18:46

papahuhn

Auf diesen Beitrag antworten »

RE: Graphentheorie
Wie sieht eure Definition eines Graphen aus?

09.07.2009, 19:25

BanachraumK_5

Auf diesen Beitrag antworten »

Definition.:

Ein Graph ist ein Paar $\begin{eqnarray*} G := (V,E) \end{eqnarray*}$ , wobei V eine endliche Menge ist und E eine Menge zweielementiger Teilmengen von V. Die Elemente v. V heißen Knoten von G und die Elemente von E Kanten.

Definition 2:

Die Anzahl der Nachbarn eines Knotens v heißt Grad von v und wird mit
$\begin{eqnarray*} deg(v) \end{eqnarray*}$ abgekürzt.

Nachbar ist, wenn $\begin{eqnarray*} \left\{u, v\right\} \in E \end{eqnarray*}$ , dann heißen u und v Nachbarn.

09.07.2009, 19:40

kiste

Auf diesen Beitrag antworten »

Mit dieser Definition(sprich es existieren keine Schleifen) ist deine Begründung richtig, ansonsten wäre die Aufgabe einfach. Denn man kann leicht einen solchen Graphen konstruieren, ein Graph der dies immer erfüllt hat maximal Summe der Grade + Anzahl der Grade Knoten Augenzwinkern

09.07.2009, 19:41

Auf diesen Beitrag antworten »

(erledigt)

09.07.2009, 19:52

BanachraumK_5

Auf diesen Beitrag antworten »

Ja O.K. aber das macht mich ein wenig unsicher, denn im Tutorium haben wir diese Aufgabe ganz anderst gelöst.

z.b. haben wir ein ähnliche Aufgabe mit den Graden 1, 2, 2, 4 aus der Tatsache gelöst, dass in einem Graphen ein gerade Anzahl von Knoten ungeraden Grades existieren.

Ist doch aber total unsinnig, wenn der Grad(v)=4 dabei ist, weil das ja ein Widerspruch zu der Tatsache ist, das deg(v) = n-1 maximal sein kann??

Anderes Beispiel:

Es sei $\begin{eqnarray*} G := (V,E) \end{eqnarray*}$ mit $\begin{eqnarray*} |V| = 6 \end{eqnarray*}$ , bei dem zwei Knoten $\begin{eqnarray*} deg(v) = 6 \end{eqnarray*}$ und vier Knoten $\begin{eqnarray*} deg(v) = 4 \end{eqnarray*}$ haben. Ist G kreisfrei???

Auch hier wäre die Aufgabe ja sehr sehr unsinnig, aber wir haben im Tutorium einen richtigen Beweis geführt???

Verstehe ich nicht und Schleifen haben wir definitiv nicht im Skript. Dann würde ja der Prof. falsche Aufgaben stellen?? immerhin ist so eine Aufgabe auch letztes Jahr in der Klausur gewesen und in der Musterlösung steht auch was anderes als $\begin{eqnarray*} deg(v) = n-1 \end{eqnarray*}$

09.07.2009, 19:55

BanachraumK_5

Auf diesen Beitrag antworten »

Schaut euch bitte mal das Blatt an http://www.math.uni-frankfurt.de/~riener/dm0906.pdf

Ist die letzte Aufgabe. Das macht doch wirklich keinen Sinn die Aufgabe so zu stellen???

09.07.2009, 20:08

papahuhn

Auf diesen Beitrag antworten »

Zitat:

z.b. haben wir ein ähnliche Aufgabe mit den Graden 1, 2, 2, 4 aus der Tatsache gelöst, dass in einem Graphen ein gerade Anzahl von Knoten ungeraden Grades existieren.

Ist doch aber total unsinnig, wenn der Grad(v)=4 dabei ist, weil das ja ein Widerspruch zu der Tatsache ist, das deg(v) = n-1 maximal sein kann??

Ja, aber der Satz gilt auch für Graphen, in denen es Schlingen und Mehrfachkanten geben kann, und dort wird der Beweis ebenfalls so geführt. Von daher nur halb unsinnig.

Zitat:

Es sei $\begin{eqnarray*} G := (V,E) \end{eqnarray*}$ mit $\begin{eqnarray*} |V| = 6 \end{eqnarray*}$ , bei dem zwei Knoten $\begin{eqnarray*} deg(v) = 6 \end{eqnarray*}$ und vier Knoten $\begin{eqnarray*} deg(v) = 4 \end{eqnarray*}$ haben. Ist G kreisfrei???

Bei eurer Definition kann ich diese Aufgabe auch nicht nachvollziehen.

09.07.2009, 20:19

BanachraumK_5

Auf diesen Beitrag antworten »

Lösung zur Aufgabe mit $\begin{eqnarray*} |V| = 6 \end{eqnarray*}$ :

Offensichtlich ist G zusammenhängend wg. $\begin{eqnarray*} |E| > |V| \end{eqnarray*}$ , wenn G nun auch kreisfrei wäre

würde gelten $\begin{eqnarray*} |E| = |V| - 1 \end{eqnarray*}$ . (Weil G dann ja ein Baum)

In unserem Fall ist $\begin{eqnarray*} |E| = 16 \end{eqnarray*}$ also gilt obige Formel nicht $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ Widerspruch.

Wieso schreiben wir nicht gleich das es so einen Graphen nicht geben kann? Vlt. will der Prof. die Türen offen halten, damit man die Beweise auch im allgemeineren (also mit Schleifen) verstehen kann??

09.07.2009, 20:36

papahuhn

Auf diesen Beitrag antworten »

Ich weiss es nicht. Vielleicht wurde in früheren Semestern die andere Definition benutzt, und deren Übungsaufgaben werden immer noch als Basis für die aktuelle Vorlesung genommen. Wenn man diese Aufgaben formalisieren würde, könnte man eigentlich immer "ja" als Antwort geben.
Für alle Graphen mit unmöglichen Eigenschaften sind halt alle Aussagen wahr. Ich würde mal beim Assi nachfragen.

09.07.2009, 22:44

BanachraumK_5

Auf diesen Beitrag antworten »

Die Sache ist, dass deg(v) = n -1 (maximal)

nirgendswo im Skript steht. Wahrscheinlich darf ich das einfach nicht folgern, denn der Prof. hat die Lösung selber so an die Tafel geschrieben und es auch so erklärt, das kann kein Zufall sein.

Neue Frage »

Antworten »

Graphentheorie

Verwandte Themen