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

60

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.

Bildbeschreibung hier eingeben

Taxellool
quelle
28
Wenn negative Werte "erlaubt" sind, warum dann nicht eine Null? :)
Derek 朕 會 功夫
5
Nur als ein kurzes Beispiel: Wenn positive Gewichte den Nettokraftstoffverbrauch beim Transport von einem Knoten zum anderen darstellen, können negative Gewichte das Nettotanken darstellen. Bei einer Nullkante wird der verbrauchte Kraftstoff durch Auftanken exakt ausgeglichen.
JW
1
@DavidRicherby Ich glaube, die eigentliche Frage hier ist z. B. "Ist der Algorithmus X in Gegenwart von Kanten mit Gewicht Null korrekt?". Ansonsten, was ist der Kontext? Die Antwort kann je nach Detail entweder Ja oder Nein sein. Eine Frage wie "Kann ein Array Nullen enthalten" ist genauso aussagekräftig.
Juho
1
@Juho: Oh, es ist klar, alles in Ordnung. Es ist so, als würde man fragen, ob eine Zahl negativ sein kann. Für Sie scheint es offensichtlich, dass es vom Kontext abhängt, aber für die Menschen war es sicher nicht offensichtlich, bis negative Zahlen eintrafen. Sogar Null war nicht offensichtlich.
Mehrdad
1
Je nachdem, was Sie tun möchten, sind Ihre Gewichte möglicherweise nicht einmal reelle Zahlen. Wenn Ihr Diagramm beispielsweise einen Wechselstromkreis darstellt, können Ihre Gewichtungen Zeiger sein, und dies sind komplexe Zahlen.
user2357112

Antworten:

165

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).

David Richerby
quelle
1
Es ist erwähnenswert, dass viele Diagrammalgorithmen explizit angeben, ob sie mit Diagrammen mit negativer Gewichtung arbeiten oder nicht. Ich denke, dies verdeutlicht, dass je nach Kontext auch negative Gewichte zulässig sind.
Mooing Duck
6
@MooingDuck Ich denke, der Punkt der Frage ist, dass, während Algorithmen in der Tat oft sagen, ob sie für negative Gewichte funktionieren oder nicht, Nullgewichte selten erwähnt werden. Negative Gewichte sind weitaus weniger ungewöhnlich als Null, daher bin ich mir nicht sicher, ob sie erwähnt werden müssen.
David Richerby
13

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).

Tom van der Zanden
quelle
Gibt es eine bestimmte Art von Grafik, die Null verbietet? und erlaubt negative oder positive werte?
Taxellool
9
Msgstr "Nicht - Null - kantengewichteter Graph".
Tom van der Zanden
10
@Taxellool Mathematische Objekte sind nicht in Stein gemeißelt. Es gibt keine feste Liste mathematischer Objekte mit festen Namen, die Sie nur verwenden dürfen.
David Richerby
Hängt davon ab, welchen Algorithmus Sie verwenden. Bellman-Ford akzeptiert Nullen, während sie in der Dijkstra umgangen werden
Manuel Azar
5

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.

Ilmari Karonen
quelle
6
Wie stark gewichtete Diagramme "typisch" angezeigt werden, hängt von Ihrem Fachgebiet ab. Wenn ich ein Straßennetz als Diagramm modelliere, um kürzeste Wege zu finden, stellen die Gewichte Entfernungen dar. Ich beginne nicht mit mehreren Straßen zwischen Kreuzungen und führe dann gebrochene Straßen ein.
AdrianN
3
@adrianN Obwohl in einem solchen Diagramm das Fehlen einer Kante einem unendlichen zugeordneten Wert und nicht Null entspricht.
CodesInChaos
0

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.)

Ian Ringrose
quelle
Ich verstehe nicht, wie dies die Frage anspricht. Die Frage fragt nach Kanten mit dem Gewicht Null. In Ihrem Beispiel (das übrigens für Leute, die mit Cambridge nicht vertraut sind, keinen Sinn ergibt) hat jede Kante bereits zwei Gewichte. Nun, soweit Sie gewichtete Graphen definieren können, wie Sie möchten, ist das in Ordnung, aber es scheint die gestellte Frage nicht zu beantworten. Außerdem scheinen die Kanten, die Sie beschreiben, zumindest ein sehr geringes Gewicht für Radfahrer zu haben: Selbst das Bewegen einer kurzen Strecke erfordert eine Zeit, die nicht null ist.
David Richerby
@DavidRicherby, nimm einfach an, dass Zeiten von weniger als 1 Sekunde nicht aufgezeichnet werden.
Ian Ringrose
0

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 ...)

Philip Oakley
quelle
Ich bin mir nicht sicher, ob dies die Frage wirklich beantwortet. Die Frage ist, ob Graphen Kanten mit einer Gewichtung von Null haben könnten. In Ihrer Antwort geht es hauptsächlich darum, wie man eine Datenstruktur für Diagramme mit Kanten ohne Gewichtung implementieren kann.
David Richerby
@DavidRicherby, Close; Es (meine Antwort) ging mehr darum, warum und wie die Frage entstand (oder entstanden sein könnte) - Eine XYProplem-Frage. Oft kann es sehr
Philip Oakley