stark zusammenhängend == vollständig???

muehlenbetreiber
Erstie
Erstie
Beiträge: 14
Registriert: 11. Aug 2008 13:20

stark zusammenhängend == vollständig???

Beitrag von muehlenbetreiber »

In der Ferienübung Aufgabe G5 ist unter d) nach der Vollständigkeit und dem Zusammenhang gefragt. Dabie ist mir aufgefallen dass doch ein "stark zusammenhängender"(NICHT in der Aufgabe geragt) Graph genau so aussieht wie ein "vollsändiger".

Seh ich das richtig oder mache ich mir ein falsches Bild?

Schon jetzt vielen dank

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

Re: stark zusammenhängend == vollständig???

Beitrag von Tigger »

Die Aussage stimmt schon mal nicht, weil vollständig die Eigenschaft eines ungerichteten- und stark zusammenhängend die eines gerichteten Graphs ist.
- Vollständig bedeutet, dass jeder Knoten eines ungerichteten Graphen mit jedem anderen benachbart ist (direkt verbunden)
- zusammenhängend bedeutet, in einem ungerichteten Graph existiert von jedem zu jedem Knoten ein Pfad (Jeder Koten ist von jedem aus erreichbar)
- Stark zusmmenhängend ist das selbe wie Zusammenhängend, nur für gerichtete Graphen (Auch hier muss jeder Knoten von jedem erreichbar sein. Hier muss man beachten, das zwischen 2 Knoten ein Pfad in beide Richtungen existieren muss. Bei ungerichteten ist es ja der selbe Pfad)

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Re: stark zusammenhängend == vollständig???

Beitrag von secretmojo »

du meinst stark zusammenhängend ist das selbe wie vollständig nur für gerichtete Graphen :-)

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

Re: stark zusammenhängend == vollständig???

Beitrag von Tigger »

secretmojo hat geschrieben:du meinst stark zusammenhängend ist das selbe wie vollständig nur für gerichtete Graphen :-)
Nein. Bei einem vollständigem Graphen muss zwischen je 2 Knoten immer eine Kante verlaufen. Bei stark zusammenhängenden Graphen ist nur gefordert dass je 2 Kanten durch einen Pfad verbunden sein müssen, nicht aber das sie direkt mit einer Kante verbunden sein müssen. Man darf nicht benachbart (direkt verbunden) mit erreichbar (es existiert ein Pfad zwischen den Knoten) verwechseln.

secretmojo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 124
Registriert: 31. Jan 2007 19:30

Re: stark zusammenhängend == vollständig???

Beitrag von secretmojo »

ah stimmt, habs durcheinander gebracht. thnx

Antworten

Zurück zu „Archiv“