Behandeln ungerichteter Diagramme als Unterkategorie gerichteter Diagramme

10

In etwa ist ein ungerichteter Graph einem gerichteten Graphen sehr ähnlich, bei dem für jede Kante (v, w) immer eine Kante (w, v) vorhanden ist. Dies deutet darauf hin, dass es möglicherweise akzeptabel ist, ungerichtete Diagramme als Teilmenge gerichteter Diagramme anzuzeigen (möglicherweise mit der zusätzlichen Einschränkung, dass das Hinzufügen / Löschen von Kanten nur in übereinstimmenden Paaren erfolgen kann).

Lehrbücher folgen jedoch normalerweise nicht dieser Behandlung und definieren ungerichtete Diagramme lieber als separates Konzept als als Unterkategorie gerichteter Diagramme. Gibt es dafür einen Grund?

graphs terminology max
quelle
2
Beachten Sie, dass es auch "gemischte Diagramme" gibt: ein Diagramm, in das Kanten gerichtet werden können oder nicht. In diesem Fall ist ein Paar gerichteter Kanten nicht dasselbe wie eine ungerichtete Kante zwischen zwei Knoten. Beispiel: Betrachten Sie Straßen: Sie können zwei Einbahnstraßen zwischen zwei entgegengesetzten Punkten oder eine einzelne Einbahnstraße haben. Dies ist in einigen Fällen wichtig: z. B. möchten Sie nicht, dass ein Navigationsgerät einen Benutzer auffordert, eine Kehrtwende zwischen zwei Einbahnstraßen durchzuführen, wenn sich in der Mitte eine Barriere befindet, während dies in einem Fall möglich sein kann einzelne Einbahnstraße.
Bakuriu

Antworten:

8

Sie sind absolut richtig; Dies ist eine absolut gültige Methode zum Anzeigen ungerichteter Diagramme.

In ungerichteten Diagrammen sind einige Dinge manchmal einfacher und klarer zu überlegen. Zum Beispiel müssen Sie sich keine Gedanken über den Unterschied zwischen schwach verbundenen und stark verbundenen Komponenten in ungerichteten Diagrammen machen. Algorithmen für ungerichtete Graphen können manchmal effizienter oder einfacher sein, als wenn wir den entsprechenden Algorithmus für gerichtete Graphen anwenden würden.

Also: Vielleicht entscheiden sich einige Lehrbücher für diese Behandlung, weil sie damit ein Problem zuerst im (einfacheren) Kontext ungerichteter Diagramme einführen und dann auf den (schwierigeren) Fall gerichteter Diagramme verallgemeinern können. Das ist nur Spekulation.

DW
quelle
3

Auf dieser Seite finden Sie Beispiele für Probleme, bei denen die Form des ungerichteten Diagramms tatsächlich schwieriger ist als die Form des gerichteten Diagramms. Dazu gehören beispielsweise das Finden eines Zyklus mit negativem Gewicht und das Zählen der Anzahl von Euler-Zyklen. Für mich scheinen diese Probleme in ungerichteten Diagrammen schwieriger zu sein, da ein Teil der Aufgabe so gestaltet werden kann, dass für jede Kante die richtige "Richtung" gewählt wird - was natürlich "bereits für uns erledigt" ist, wenn das Diagramm gerichtet ist.

j_random_hacker
quelle
1
Oh, richtig. Zum Beispiel müsste der Euler-Zyklus, wenn er als gerichtete Graphen definiert wird, erfordern, dass "nicht mehr als eine Kante von jedem Paar (v, w), (w, v) verwendet wird" - was die Idee der Darstellung eines ungerichteten Graphen ergibt als Digraph weniger attraktiv.
Max
0

Es ist schwer, aus heiterem Himmel etwas sehr Allgemeines zu motivieren . es könnte die Beweise und die Lehrbücher einfacher machen, aber nicht unbedingt einfacher zu verstehen und intuitiv zu befolgen.
Menschen finden es normalerweise intuitiver, ein einfaches Konzept zu lernen und es dann auf etwas Abstrakteres zu verallgemeinern, anstatt ein überverallgemeinertes und abstraktes Konzept zu definieren und dann seine besonderen Fälle zu instanziieren. Dies ist wahrscheinlich einer dieser Fälle.

user541686
quelle