Graphentheorie

Neue Frage »

BanachraumK_5 Auf diesen Beitrag antworten »
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:



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 ?????

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

Danke.
papahuhn Auf diesen Beitrag antworten »
RE: Graphentheorie
Wie sieht eure Definition eines Graphen aus?
 
 
BanachraumK_5 Auf diesen Beitrag antworten »

Definition.:

Ein Graph ist ein Paar , 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
abgekürzt.

Nachbar ist, wenn , dann heißen u und v Nachbarn.
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
AD Auf diesen Beitrag antworten »

(erledigt)
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 mit , bei dem zwei Knoten und vier Knoten 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
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???
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 mit , bei dem zwei Knoten und vier Knoten haben. Ist G kreisfrei???


Bei eurer Definition kann ich diese Aufgabe auch nicht nachvollziehen.
BanachraumK_5 Auf diesen Beitrag antworten »

Lösung zur Aufgabe mit :

Offensichtlich ist G zusammenhängend wg. , wenn G nun auch kreisfrei wäre

würde gelten . (Weil G dann ja ein Baum)

In unserem Fall ist also gilt obige Formel nicht 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??
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.
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 »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »