Kritischer Graph S.94f

Moderator: Effiziente Graphenalgorithmen

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Kritischer Graph S.94f

Beitrag von Dreamdancer »

Wenn man der Definition einer kritischen Kante nach geht, müssten beide eingehende Kanten des Knotens 2 kritisch sein, da für beide die <=-Relation gilt.

Nach der Definition eines kritischen Graphens dürfte damit der Knoten 2 nicht zum kritischen Graphen gehören, weil die Knoten höchstens eine eingehende kritische Kante haben dürfen.

Kann man davon ausgehen, dass man das "höchstens" weglassen kann? Wofür soll das gut sein? Auf Seite 94 ist Knoten 2 ja als kritisch markiert, allerdings nur eine von beiden eingehenden Kanten. Irgendwo ist da der Wurm drin.

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Kritischer Graph S.94f

Beitrag von Dreamdancer »

Beim nochmaligen Durchlesen würde ich sagen, dass durchaus beide eingehenden Kanten kritisch sind, aber eben nur eine zum kritischen Graphen gehört, eben wegen Definition (b).

Ich glaube so passt das.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Kritischer Graph S.94f

Beitrag von Stille »

So ist es. Man wählt in diesem Fall eine kritische Kante aus.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“