Hausübung 3 - H1

jül
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 30. Okt 2007 01:21
Wohnort: Darmstadt
Kontaktdaten:

Hausübung 3 - H1

Beitrag von jül »

Dort ist von ungerichteten Graphen die Rede, und in den Teilaufgaben b und c wird dann
gefordert, dass der Graph azyklisch seien soll. Ist das nicht etwas
sinnlos, weil ich doch in einem ungerichteten Graphen nur eine Kante
brauche, um einen Zyklus herzustellen, oder?
Test my convictions, they'll run you through!

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Hausübung 3 - H1

Beitrag von mantra »

Ein Zyklus ist ein Pfad und ein Pfad ist kanteneinfach.

Wambolo
Computerversteher
Computerversteher
Beiträge: 381
Registriert: 18. Okt 2007 11:36

Re: Hausübung 3 - H1

Beitrag von Wambolo »

In der Literaturempfehlung steht, dass ein Zyklus im ungerichteten Graphen aus mindestens 3 Kanten besteht, wenn ich das richtig verstanden habe, somit wäre eine einfache Verbindung zwischen zwei Knoten kein Zyklus.
Interpreter/Parser reported on Nov 12, 2008 8:30:04 PM:
Number too big (102 > 42).

Mira`
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 27. Okt 2006 20:41

Re: Hausübung 3 - H1

Beitrag von Mira` »

Kann es so einen ungerichteten Graphen geben? Also spezielle die Kanten von A -- A , B -- B und C -- C? Ich habe bisher keine Definition gefunden, die soetwas verbietet, vermute aber eher, dass sowas nicht erlaubt ist.

Die passende Adjazenzmatrix würde ja so aussehen:

- A B C
A 1 1 1
B 1 1 1
C 1 1 1
Dateianhänge
Graph Beispiel
Graph Beispiel
test.gif (3.56 KiB) 980 mal betrachtet

Benutzeravatar
Panulli
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 110
Registriert: 20. Apr 2005 07:20

Re: Hausübung 3 - H1

Beitrag von Panulli »

Nein, kann es nicht...da es bei ungerichteten Graphen keine Schleifen gibt. D.h. die Diagonaleinträge sind immer "Null".
Grüßlich ULI

http://www.SGE4ever.de

Mira`
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 27. Okt 2006 20:41

Re: Hausübung 3 - H1

Beitrag von Mira` »

Danke für die Antwort.

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Hausübung 3 - H1

Beitrag von tmx-master »

Panulli hat geschrieben:Nein, kann es nicht...da es bei ungerichteten Graphen keine Schleifen gibt. D.h. die Diagonaleinträge sind immer "Null".
Hi Panulli,
wie kommst du darauf, dass es in ungerichteten Graphen keine Schlingen gibt? Natürlich gibt es das.

Jede ungerichtete Kante verbindet entweder zwei verschiedene Knoten u und v miteinander oder im Falle einer ungerichteten Schlinge einen Knoten v mit sich selbst.

Was spricht denn dagegen, bzw. wo hast du das gelesen?
Gruß TM

Benutzeravatar
taufrisch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 107
Registriert: 30. Sep 2007 02:42
Wohnort: 127.0.0.1

Re: Hausübung 3 - H1

Beitrag von taufrisch »

tmx-master hat geschrieben:Hi Panulli,
wie kommst du darauf, dass es in ungerichteten Graphen keine Schlingen gibt? Natürlich gibt es das.
Nope: 6 Graphen (Seite 1): Ein ungerichteter Graph \(G\) is ein Paar \((V, E)\). Dabei ist \(V\) eine endliche Menge, \(E\subset\{\{x, y\}:x, y\in V\quad x\neq y\}\).

Keine Schlingen in unseren ungerichteten Graphen :mrgreen:
Premature optimization is the root of all evil.

Don't anthropomorphize computers: They hate that.

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Hausübung 3 - H1

Beitrag von tmx-master »

Ok, im Cormen S. 1083 steht auch, dass in einem ungerichteten Graphen Schlingen nicht erlaubt sind. Eine Begründung gibt es jedoch nicht.

Hat jemand eine? Mit fällt nichts ein, was dagegen spricht.
Gruß TM

Mspringer
Nerd
Nerd
Beiträge: 555
Registriert: 19. Okt 2006 14:41
Wohnort: Darmstadt / Alzenau
Kontaktdaten:

Re: Hausübung 3 - H1

Beitrag von Mspringer »

Glaube das ist ne reine definitionssache. Ich hab auch rel. Lange versucht irgendwas genaueres darüber zu finden, aber die suche blieb leider Erfolglos ^^

tmx-master
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 253
Registriert: 25. Okt 2006 17:44

Re: Hausübung 3 - H1

Beitrag von tmx-master »

Mspringer hat geschrieben:Glaube das ist ne reine definitionssache. Ich hab auch rel. Lange versucht irgendwas genaueres darüber zu finden, aber die suche blieb leider Erfolglos ^^
Hi Mspringer,
danke für den Zuspruch. Ich denke auch, dass man das für ein Buch oder eine Vorlesung oder für sonstwas einfach festlegen kann bzw. muss, um sich dann bei der Beschreibung von Algos immer darauf beziehen zu können. Aber ansonsten könnte man das eben auch so definieren, dass es zugelassen werden kann. In der VL GDI II und im Cormen ist es eben nicht zugelassen.

Danke für die Antwort.
Gruß TM

Antworten

Zurück zu „Archiv“