Le zéro est-il autorisé comme poids d'un bord dans un graphique pondéré?

60

J'essaie d'écrire un script qui génère des graphiques aléatoires et j'ai besoin de savoir si une arête d'un graphique pondéré peut avoir la valeur 0.

En fait, il est logique que 0 puisse être utilisé comme poids d’un bord, mais j’ai travaillé avec des graphiques ces derniers jours et je n’en ai jamais vu un exemple.

entrez la description de l'image ici

Taxellool
la source
28
Si les valeurs négatives sont "autorisées", alors pourquoi pas un zéro? :)
Derek 會 功夫
5
À titre d’exemple rapide, si les poids positifs représentent la consommation nette de carburant lorsqu’on passe d’un nœud à un autre, les poids négatifs peuvent représenter le plein de carburant. Un bord zéro pondéré est l'endroit où le carburant dépensé est exactement compensé par le ravitaillement en carburant.
JW
1
@DavidRicherby Je crois que la vraie question ici est, par exemple, "l'algorithme X est-il correct en présence d'arêtes de poids nul". Sinon, quel est le contexte? La réponse peut être oui ou non, en fonction des détails. Une question comme "un tableau peut-il contenir des zéros" est tout aussi significative.
Juho
1
@ Juho: Oh c'est clair tout va bien. C'est comme demander si un nombre peut être négatif. Pour vous, il semble évident que cela dépend du contexte, mais ce n'était pas évident pour les gens jusqu'à ce que des chiffres négatifs apparaissent. Même zéro n'était pas évident.
Mehrdad
1
Selon ce que vous voulez faire, vos poids pourraient même ne pas être de vrais nombres. Par exemple, si votre graphique représente un circuit alternatif, vos poids pourraient être des phaseurs, et ce sont des nombres complexes.
user2357112

Réponses:

165

Permis par qui ? Aucune administration graphique centralisée ne décide de ce que vous pouvez ou ne pouvez pas faire. Vous pouvez définir des objets de la manière qui vous convient, à condition de bien définir leur définition. Si les arêtes à pondération zéro vous sont utiles, utilisez-les; assurez-vous simplement que vos lecteurs savent que c'est ce que vous faites.

La raison pour laquelle vous ne voyez généralement pas les arêtes à pondération nulle est que, dans la plupart des contextes, une arête de poids zéro équivaut exactement à l'absence d'un bord. Par exemple, si votre graphique représente les pays et le volume des échanges effectués entre eux, un avantage égal à zéro signifie qu’il n’existe aucun échange, ce qui revient à ne pas avoir d’avantage du tout. Si votre graphique représente des distances, une arête de poids zéro correspondrait à deux emplacements distants de zéro, ce qui voudrait dire qu'ils seraient en fait au même endroit. Les deux doivent donc être représentés par le même sommet. Cependant, dans d'autres contextes, les arêtes de poids zéro pourraient avoir un sens. Par exemple, si votre graphique représente un réseau routier et que les poids de carre représentent la quantité de trafic, il y a une grande différence entre une route que personne n'utilise (bord sans poids) et aucune route (pas de bord).

David Richerby
la source
1
Il convient de noter que de nombreux algorithmes de graphes spécifient explicitement s'ils travaillent ou non sur des graphes avec des pondérations négatives. Je pense que cela clarifie que même les poids négatifs sont autorisés, en fonction des contextes.
Mooing Duck
6
@MooingDuck Je pense que le problème de la question est que, bien que les algorithmes disent souvent s'ils fonctionnent ou non avec des poids négatifs, les poids zéro sont rarement mentionnés. Les poids négatifs sont beaucoup moins inhabituels que zéro, aussi, dans ce contexte particulier, je ne suis pas sûr qu'ils doivent être mentionnés.
David Richerby
13

Ça dépend du contexte. En général oui, des arêtes de poids nul et même négatif peuvent être autorisées. Dans certains cas spécifiques, il peut être nécessaire que les pondérations des arêtes soient non négatives ou strictement positives (par exemple, l'algorithme de Dijkstra exige que les pondérations soient non négatives).

Tom van der Zanden
la source
Existe-t-il un type de graphique spécifique qui interdit le zéro? et permet des valeurs négatives ou positives?
Taxellool
9
"Graphe pondéré par les arêtes non nul".
Tom van der Zanden
10
@Taxellool Les objets mathématiques ne sont pas gravés dans la pierre. Il n’existe pas de liste fixe d’objets mathématiques avec des noms fixes que vous êtes autorisé à utiliser.
David Richerby le
Cela dépend de l'algorithme que vous utilisez. Bellman-Ford accepte les zéros, alors qu'ils sont éliminés à Dijkstra
Manuel Azar
5

Comme le notent les autres réponses, vous êtes parfaitement libre de prendre en compte (ou d’exclure de cela) les graphes pondérés avec des arêtes de poids nul.

Cela dit, selon mon expérience, la convention habituelle dans la plupart des applications de graphes pondérés est de ne faire aucune distinction entre un bord de poids nul et l'absence de bord. Cela s'explique notamment par le fait que les graphes pondérés sont généralement des généralisations de multigraphes , qui sont à leur tour des généralisations de graphes simples.

Spécifiquement, un multigraphe est un graphe qui (contrairement à un graphe simple ) permet plusieurs arêtes entre la même paire de nœuds. Alors que, dans un graphique simple, toute paire de nœuds est toujours connectée par 0 ou 1 arête, une paire de nœuds dans un multigraphe peut être connectée par 0, 1, 2, 3 ou plus (mais toujours par un nombre entier non négatif de ) bords.

Généraliser un multigraphe pour permettre un nombre fractionnaire d'arêtes entre une paire de nœuds amène naturellement à considérer les graphes pondérés, et de nombreux algorithmes travaillant sur des multigraphes arbitraires peuvent également être conçus pour fonctionner sur de tels graphes pondérés. Mais pour de tels algorithmes, le "poids" d'un bord dénote réellement sa multiplicité . Ainsi, étant donné cette interprétation, il ne peut y avoir de distinction significative entre "pas de bord" et "0 fronts" entre une paire de nœuds: les deux signifient exactement la même chose.

Bien sûr, un "graphe pondéré", par définition, n’est en réalité qu’un graphe avec un nombre associé à chaque arête, et il est parfaitement possible d’interpréter le poids comme autre chose que la multiplicité, auquel cas la distinction entre aucun arête et zéro bord peut en effet avoir un sens. Cependant, essayer d'appliquer des algorithmes multigraphes standard à de tels "graphes étrangement pondérés" ne donnera probablement pas de résultats significatifs du point de vue de l'interprétation alternative (non-multiplicité) de la pondération des arêtes.

Ilmari Karonen
la source
6
La façon dont les graphiques pondérés apparaissent "généralement" dépend beaucoup de votre domaine. Lorsque je modélise un réseau routier sous forme de graphique pour trouver les chemins les plus courts, les poids représentent les distances. Je ne commence pas par plusieurs routes entre intersections, puis par des routes fractionnées.
adrianN
3
@adrianN Bien que dans un graphique comme celui-là, l'absence d'une arête correspond à une valeur associée infinie et non à zéro.
CodesInChaos
0

Pensez à un graphique du système routier de Cambridge UK, les notes sont partagées entre les cyclistes et les automobilistes, de même que la plupart des bords. Cela réduirait considérablement le coût de la maintenance des données.

Maintenant, si nous définissons le poids du bord comme étant le temps de parcours en secondes, chaque bord aura proprement deux poids, un pour les voitures et les vélos pour les vélos. Certains poids seront infinis car les voitures ne sont pas autorisées sur les pistes cyclables.

Examinons maintenant deux carrefours très proches l'un de l'autre si proches l'un de l'autre et qui ne sont bloqués que par quelques poteaux qui arrêtent les automobilistes. (Par exemple, une route transversale où les voitures roulent ne peuvent tourner que vers la gauche, mais les cyclistes peuvent aller dans n'importe quelle direction.) Nous obtenons alors des arêtes avec un poids infini de la part des automobilistes et un poids nul pour les cyclistes.

(Il est clair que le graphique pourrait ensuite être prétraité afin de créer un graphique plus simple pour l’acheminement des cyclistes, avant de déterminer les meilleurs itinéraires.)

Ian Ringrose
la source
Je ne vois pas comment cela répond à la question. La question concerne les arêtes de poids zéro. Dans votre exemple (qui, d’ailleurs, n’a peut-être pas beaucoup de sens pour ceux qui ne connaissent pas Cambridge), chaque bord a déjà deux poids. Maintenant, dans la mesure où vous pouvez définir des graphiques pondérés comme vous le souhaitez, c'est correct, mais cela ne semble pas répondre à la question posée. En outre, les bords que vous décrivez semblent tous avoir au moins un poids très faible pour les cyclistes: même se déplacer sur une courte distance nécessite une quantité de temps non nulle.
David Richerby
@DavidRicherby, supposons simplement que les durées inférieures à 1 seconde ne sont pas enregistrées.
Ian Ringrose
0

On dirait que vous utilisez le poids pour essayer de représenter deux aspects distincts du graphique. La première est de savoir si le graphique a réellement un bord représentable (dessiné) et la seconde est son poids réel.

Comme vous l'avez remarqué, vous tombez dans une situation confuse si vous avez utilisé le mot «non nul» comme indicateur de la présence d'une arête (et que vous deviez la tracer ou la répertorier), alors que vous avez simultanément trouvé une situation. où zéro poids est classé comme valide.

Vous aurez essentiellement besoin d’une autre façon de représenter la présence du bord (en supposant que vous en avez réellement besoin et que vous ne pouvez pas simplement créer un tableau de pondérations N ^ 2, mais vous tombez dans le piège de devoir décider quoi faire à propos de la boucle. bords arrières ...)

Philip Oakley
la source
Je ne suis pas sûr que cela réponde vraiment à la question. La question est de savoir si les graphiques peuvent avoir des arêtes égales à zéro; votre réponse porte principalement sur la manière dont on pourrait implémenter une structure de données pour les graphiques avec des arêtes de poids zéro.
David Richerby le
@DavidRicherby, Close; Il (ma réponse) portait plus sur pourquoi et comment la question est apparue (ou est peut-être apparue) - un problème XYProplem. Il peut souvent être très utile de pouvoir expliquer pourquoi le problème était au départ problématique et de voir en quoi la solution est la bonne réponse et non pas seulement un «fudge»
Philip Oakley