Graphentheorie |
09.07.2009, 18:27 | BanachraumK_5 | Auf diesen Beitrag antworten » | ||||
Graphentheorie 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. |
||||||
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 , 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. |
||||||
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 |
||||||
09.07.2009, 19:41 | AD | 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 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 |
||||||
Anzeige | ||||||
|
||||||
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 » | ||||
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.
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 : 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?? |
||||||
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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|