Ist Null als Kantengewicht in einem gewichteten Diagramm zulässig?

Ich versuche, ein Skript zu schreiben, das zufällige Diagramme generiert, und ich muss wissen, ob eine Kante in einem gewichteten Diagramm den Wert 0 haben kann.

Eigentlich macht es Sinn, dass 0 als Kantengewicht verwendet werden kann, aber ich habe in den letzten Tagen mit Diagrammen gearbeitet und noch nie ein Beispiel dafür gesehen.

Von wem erlaubt ? Es gibt keine zentrale Grafikverwaltung, die entscheidet, was Sie tun und was nicht. Sie können Objekte auf eine für Sie bequeme Weise definieren, solange Sie sich über die Definition im Klaren sind. Wenn Ihnen Kanten mit einer Gewichtung von Null nützlich sind, verwenden Sie sie. Stellen Sie einfach sicher, dass Ihre Leser wissen, was Sie tun.

Der Grund, warum Sie normalerweise keine Kanten mit der Gewichtung Null sehen, ist, dass in den meisten Kontexten eine Kante mit der Gewichtung Null genau dem Fehlen einer Kante entspricht. Wenn Ihre Grafik beispielsweise Länder und den zwischen ihnen getätigten Handel darstellt, würde eine Null-Gewichtungs-Kante keinen Handel bedeuten, was dasselbe ist, als hätte sie überhaupt keine Kante. Wenn Ihr Diagramm Entfernungen darstellt, würde eine Kante mit Nullgewicht zwei Stellen im Abstand Null voneinander entsprechen, was bedeuten würde, dass sie tatsächlich dieselbe Stelle sind. Daher sollten beide Stellen durch denselben Scheitelpunkt dargestellt werden. In anderen Zusammenhängen können Kanten mit Nullgewicht jedoch sinnvoll sein. Wenn Ihr Diagramm beispielsweise ein Straßennetz darstellt und die Kantengewichte die Verkehrsmenge darstellen, gibt es einen großen Unterschied zwischen einer Straße, die von niemandem verwendet wird (gewichtsfreie Kante) und keiner Straße (keine Kante).

Es kommt auf den Kontext an. Im Allgemeinen sind ja Kanten von Null und sogar eine negative Gewichtung zulässig. In bestimmten Fällen müssen die Kantengewichte möglicherweise nicht negativ oder streng positiv sein (zum Beispiel erfordert der Dijkstra-Algorithmus, dass die Gewichte nicht negativ sind).

Wie die anderen Antworten vermerken, können Sie gewichtete Diagramme mit Kanten ohne Gewichtung durchaus berücksichtigen (oder von der Berücksichtigung ausschließen).

Nach meiner Erfahrung besteht die übliche Konvention bei den meisten Anwendungen von gewichteten Graphen darin, keine Unterscheidung zwischen einer Kante mit null Gewicht und dem Fehlen einer Kante zu treffen. Ein Grund dafür ist, dass gewichtete Graphen in der Regel als Verallgemeinerungen von Multigraphen angezeigt werden , die wiederum Verallgemeinerungen einfacher Graphen sind.

Insbesondere ist ein Multigraph ein Graph, der (anders als ein einfacher Graph ) mehrere Kanten zwischen demselben Knotenpaar zulässt. Während in einem einfachen Graphen jedes Knotenpaar immer durch 0 oder 1 Kanten verbunden ist, kann ein Knotenpaar in einem Multigraph durch 0, 1, 2, 3 oder mehr verbunden sein (aber immer eine nicht negative ganze Zahl von ) Kanten.

Die Verallgemeinerung eines Multigraphen, um eine gebrochene Anzahl von Kanten zwischen einem Knotenpaar zuzulassen, führt natürlich dazu, dass man gewichtete Graphen berücksichtigt, und viele Algorithmen, die mit beliebigen Multigraphen arbeiten, können auch dazu gebracht werden, mit solchen gewichteten Graphen zu arbeiten. Aber für solche Algorithmen bezeichnet das "Gewicht" einer Kante wirklich ihre Vielheit . Bei dieser Interpretation kann es also keine sinnvolle Unterscheidung zwischen "keine Kante" und "0 Kanten" zwischen einem Knotenpaar geben: Beide bedeuten genau dasselbe.

Natürlich ist ein "gewichteter Graph" per Definition nur ein Graph mit einer Nummer, die jeder Kante zugeordnet ist, und es ist durchaus möglich, das Gewicht als etwas anderes als eine Multiplizität zu interpretieren , in diesem Fall eine Unterscheidung zwischen keiner Kante und einer Null-Gewichtung Rand kann in der Tat sinnvoll sein. Es ist jedoch unwahrscheinlich, dass der Versuch, Standard-Multigraph-Algorithmen auf solche "seltsam gewichteten Graphen" anzuwenden, zu Ergebnissen führt, die im Hinblick auf die alternative (Nicht-Multiplizitäts-) Interpretation von Kantengewichten sinnvoll wären.

Stellen Sie sich ein Diagramm des Straßensystems in Cambridge vor. Die Notizen werden zwischen Radfahrern und Autofahrern geteilt, ebenso die meisten Kanten. Auf diese Weise werden die Kosten für die Pflege der Daten erheblich gesenkt.

Wenn wir nun das Kantengewicht als Fahrzeit in Sekunden definieren, hat jede Kante zwei Gewichte, eines für Autos und eines für Fahrräder. Einige Gewichte sind unendlich, da Autos auf Radwegen nicht erlaubt sind.

Betrachten Sie nun zwei Straßenkreuzungen, die so nahe beieinander liegen, dass sie nur von wenigen Pfosten gezackt werden, die Autofahrer anhalten. (Zum Beispiel eine Querstraße, auf der Autofahrer nur nach links abbiegen können, Radfahrer jedoch in jede Richtung.) Dann erhalten wir einige Kanten mit unendlich viel Gewicht von Autofahrern und 0 Gewicht für Radfahrer.

(Das Diagramm könnte dann natürlich vorverarbeitet werden, um ein einfacheres Diagramm für das Routen von Radfahrern zu erstellen, bevor die besten Routen ermittelt werden.)

Es klingt so, als würden Sie die Gewichtung verwenden, um zwei deutlich unterschiedliche Aspekte des Diagramms darzustellen. Das erste ist, ob der Graph tatsächlich eine darstellbare (gezogene) Kante hat, und das zweite ist das tatsächliche Gewicht.

Wie Sie bemerkt haben, geraten Sie in eine verwirrende Situation, wenn Sie "Nicht-Null" als Indikator dafür verwendet haben, dass eine Kante vorhanden ist (und gezeichnet oder aufgelistet werden müsste), während Sie gleichzeitig eine Situation gefunden haben Wobei Nullgewicht als gültig eingestuft wird.

Im Wesentlichen benötigen Sie eine andere Art der Darstellung des Vorhandenseins der Kante (vorausgesetzt, Sie benötigen diese tatsächlich und können nicht einfach ein N ^ 2-Array von Gewichten erstellen. Dann müssen Sie jedoch entscheiden, was mit der Schleife geschehen soll Hinterkanten ...)