Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Graphen - allgemeine Vorgehensweise
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Graphen - allgemeine Vorgehensweise
 
Autor Nachricht
at0m
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.04.2010
Beiträge: 2

BeitragVerfasst am: 02 Apr 2010 - 10:45:43    Titel: Graphen - allgemeine Vorgehensweise

Hallo an alle! Wink

Ich sitze gerade an einer Aufgabe (Anfang des Studiums) und habe eine Frage an alle Experten.

Und zwar geht es darum, einen Graphen zu zeichnen. Wahrscheinlich sehr simpel, denoch fehlt mir der Ansatz.


Folgendermaßen:
Es sei ein Graph G = ( V, E )
mit
V = { H, I, J, K, L, M }
und
E = { (H, I), (H, K), (I, L), (J, I), (J, M), (K, H), (L, K), (L, J), (M, J), (M, L) }

G soll nun graphisch dargestellt werden.

Erstes Problem: Da ich am Anfang nicht weiß, ob es ein gerichteter/ungerichteter Graph bzw. ein Baum wird, stellt sich bei mir die Frage, ob es eine Möglichkeit gibt, dieses im Vorfeld zu klären.

Zweites Problem: Wenn ich nun beginnen möchte zuerst die Knoten (von V) zu zeichnen um diese dann mit den Kanten (von E) zu verbinden weiß ich nicht genau, ob es eine bestimmte Struktur oder ein Muster gibt, wie ich damit anfange. Soll ich die Knoten vorerst "einfach in den Raum zeichnen", ohne eine Ordnung oder kann man auch dies bereits vor dem Zeichnen klären/ersehen?


Ich würde mich sehr freuen, wenn mir jemand helfen könnte und bedanke mich bereits im Voraus für die Unterstützung!

Gruß
at0m
just_phil
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 23.08.2008
Beiträge: 1006

BeitragVerfasst am: 02 Apr 2010 - 11:56:19    Titel:

Kann Zufall sein, aber die Aufgabe kommt mir verdammt vertraut vor, Du studierst nicht zufällig in Berlin?

Aufgrund der Tatsache, dass die Aufgabenstellung nichts darüber aussagt, würde ich generell von einem ungerichteten Graphen ausgehen. Da ein ungerichteter Graph auch nicht wirklich zwischen "oben" und "unten" unterscheidet, spielt es zunächst einmal keine Rolle, mit welchen Knoten und korrespondierenden Kanten Du beginnst, bzw. wo sie sich - wie Du schon sagst - im Raum befinden. Letzten Endes kannst Du das über mehrere Ebenen beispielsweise in eine Form bringen (wenn Du zum Beispiel feststellst, dass es sich um einen Binärbaum handelt; gleichrangige Blätter könnten dann auf einer Ebene stehen), aber mehr als eine optische Verbesserung wäre das nicht. Im Modell eines ungerichteten (und ungewichteten!) Graphen ist prinzipiell auch die Kantenlänge auf dem Papier unerheblich. Ob eine Kante nun 5cm oder plötzlich 10cm lang ist, spielt für den Menschen unter Umständen eine Rolle, ändert aber nichts am Sachverhalt.
at0m
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.04.2010
Beiträge: 2

BeitragVerfasst am: 02 Apr 2010 - 18:10:20    Titel:

Hi!

Vielen Dank für deine Antwort!
Ne, studiere nicht in Berlin aber die Aufgabe könnte eine typische Lehrbuchaufgabe sein, die man so am Anfang des Semesters vorgelegt bekommt. Very Happy Denke da sind viele ähnlich.

Habe nun mal versucht einen Graphen zu erstellen. Wäre der so richtig?

Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 02 Apr 2010 - 19:48:34    Titel:

Sieht gut aus, jedoch sehen manche Dozenten es ungerne, wenn gerichtete, beidseitige Verbindungen zwischen Knoten "in einem", also mit einem "Strich" und 2 Spitzen, gezeichnet werden -- stattdessen kann es u. U. besser sein, jede Kante "extra" zu zeichnen.

Davon abgesehen: du hast eine Menge von Tupeln = Kanten. Wenn du die Klammern also so richtig abgeschrieben hast, sind deine Kanten Tupel und damit hast du einen gerichteten Graphen. Wink

http://de.wikipedia.org/wiki/Graph_%28Graphentheorie%29 hat folgendes geschrieben:
gerichteten Graphen ohne Mehrfachkanten eine Teilmenge des kartesischen Produktes V \times V,
just_phil
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 23.08.2008
Beiträge: 1006

BeitragVerfasst am: 02 Apr 2010 - 20:09:01    Titel:

Smutje hat folgendes geschrieben:
Wenn du die Klammern also so richtig abgeschrieben hast, sind deine Kanten Tupel und damit hast du einen gerichteten Graphen. Wink


Das ist einleuchtend und richtig. Habe gerade nochmal geschaut. Diese Aufgabe habe ich im ersten Semester tatsächlich auch bearbeitet (lang ist's her) und ich hatte mir sogar die Notiz gemacht, dass beidseitige Verbindungen mit je(!) einem Pfeil dargestellt werden. Smutjes Ausführung ist also nichts hinzuzufügen.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Graphen - allgemeine Vorgehensweise
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum