¿Se permite cero como el peso de una arista, en un gráfico ponderado?

60

Estoy tratando de escribir un script que genere gráficos aleatorios y necesito saber si un borde en un gráfico ponderado puede tener el valor 0.

en realidad tiene sentido que 0 pueda usarse como el peso de una arista, pero he estado trabajando con gráficos en los últimos días y nunca he visto un ejemplo de ello.

ingrese la descripción de la imagen aquí

Taxellool
fuente
28
Si los valores negativos están "permitidos", ¿por qué no un cero? :)
Derek 朕 會 功夫
55
Solo como un ejemplo rápido, si los pesos positivos representan el consumo neto de combustible cuando se viaja de un nodo a otro, los pesos negativos pueden representar el reabastecimiento neto. Un borde ponderado cero es donde el combustible gastado se compensa exactamente mediante el reabastecimiento de combustible.
JW
1
@DavidRicherby Creo que la verdadera pregunta aquí es, por ejemplo, "¿es correcto el algoritmo X en presencia de bordes de peso cero"? De lo contrario, ¿cuál es el contexto? La respuesta puede ser sí o no, según los detalles. Una pregunta como "puede una matriz contener ceros" es igual de significativa.
Juho
1
@Juho: Oh, está claro, de acuerdo. Es como preguntar si un número puede ser negativo. Para usted parece obvio que depende del contexto, pero seguro que no fue obvio para las personas hasta que aparecieron los números negativos. Incluso cero no era obvio.
Mehrdad
1
Dependiendo de lo que quieras hacer, es posible que tus pesos ni siquiera sean números reales. Por ejemplo, si su gráfico representa un circuito de CA, sus pesos pueden ser fasores y esos son números complejos.
user2357112

Respuestas:

165

Permitido por quien ? No existe una Administración central de gráficos que decida lo que puede y no puede hacer. Puede definir objetos de la forma que le resulte conveniente, siempre que tenga claro cuál es la definición. Si los bordes con ponderación cero son útiles para usted, utilícelos; solo asegúrate de que tus lectores sepan que eso es lo que estás haciendo.

La razón por la que no suele ver bordes de peso cero es que, en la mayoría de los contextos, un borde con peso cero es exactamente equivalente a la ausencia de un borde. Por ejemplo, si su gráfico representa países y la cantidad de comercio realizado entre ellos, una ventaja de peso cero significaría que no hay comercio, que es lo mismo que no tener ninguna ventaja. Si su gráfico representa distancias, un borde de peso cero correspondería a dos lugares a una distancia cero uno del otro, lo que significaría que en realidad serían el mismo lugar, por lo que ambos deberían estar representados por el mismo vértice. Sin embargo, en otros contextos, los bordes de peso cero podrían tener sentido. Por ejemplo, si su gráfico representa una red de carreteras y los pesos de los bordes representan la cantidad de tráfico, hay una gran diferencia entre una carretera que nadie usa (borde de peso cero) y ninguna carretera (sin borde).

David Richerby
fuente
1
Vale la pena señalar que muchos algoritmos de gráficos especifican explícitamente si funcionan en gráficos con pesos negativos o no. Creo que esto aclara que incluso se permiten pesos negativos, dependiendo de los contextos.
Mooing Duck
66
@MooingDuck Creo que el punto de la pregunta es que, si bien los algoritmos a menudo dicen si funcionan o no con pesos negativos, rara vez se mencionan los pesos cero. Los pesos negativos son mucho menos inusuales que cero, por lo que, en este contexto particular, no estoy seguro de que necesiten mencionarse.
David Richerby
13

Depende del contexto. En general, sí, pueden permitirse bordes de cero e incluso peso negativo. En algunos casos específicos, es posible que se requiera que los pesos de los bordes sean no negativos o estrictamente positivos (por ejemplo, el algoritmo de Dijkstra requiere que los pesos no sean negativos).

Tom van der Zanden
fuente
¿Hay algún tipo específico de gráfico que prohíba cero? y permite valores negativos o positivos?
Taxellool
99
"Gráfico ponderado de borde distinto de cero".
Tom van der Zanden
10
@Taxellool Los objetos matemáticos no están escritos en piedra. No hay una lista fija de objetos matemáticos con nombres fijos que sean los únicos que puede usar.
David Richerby
Depende del algoritmo que uses. Bellman-Ford acepta ceros, mientras que en Dijkstra son obviados
Manuel Azar
5

Como señalan las otras respuestas, es perfectamente libre de considerar (o excluir de la consideración) gráficos ponderados con bordes de peso cero.

Dicho esto, en mi experiencia, la convención habitual en la mayoría de las aplicaciones de gráficos ponderados es no hacer distinción entre un borde de peso cero y la ausencia de un borde. Una razón para esto es que, típicamente, los gráficos ponderados se muestran como generalizaciones de multigrafos , que a su vez son generalizaciones de gráficos simples.

Específicamente, un multigrafo es un gráfico que (a diferencia de un gráfico simple ) permite múltiples bordes entre el mismo par de nodos. Mientras que, en un gráfico simple, cualquier par de nodos siempre está conectado por 0 o 1 aristas, un par de nodos en un multigrafo puede estar conectado por 0, 1, 2, 3 o más (pero siempre un número entero no negativo de ) bordes.

Generalizar un multigrafo para permitir un número fraccionario de aristas entre un par de nodos, naturalmente, lleva a uno a considerar gráficos ponderados, y muchos algoritmos que funcionan en multigrafos arbitrarios también se pueden hacer funcionar en tales gráficos ponderados. Pero para tales algoritmos, el "peso" de un borde realmente denota su multiplicidad . Por lo tanto, dada esta interpretación, no puede haber una distinción significativa entre "sin borde" y "bordes 0" entre un par de nodos: ambos significan exactamente lo mismo.

Por supuesto, un "gráfico ponderado", por definición, es realmente solo un gráfico con un número asociado a cada borde, y es perfectamente posible interpretar el peso como algo diferente a la multiplicidad, en cuyo caso una distinción entre sin borde y un peso cero borde de hecho puede ser significativo. Pero es poco probable que intentar aplicar algoritmos multigráficos estándar a tales "gráficos ponderados de manera extraña" produzca resultados que tengan sentido en términos de la interpretación alternativa (no multiplicidad) de los pesos de borde.

Ilmari Karonen
fuente
66
La forma en que los gráficos ponderados se muestran "típicamente" depende en gran medida de su campo. Cuando modelo una red de carreteras como un gráfico para encontrar caminos más cortos, los pesos representan distancias, no empiezo con caminos múltiples entre intersecciones y luego introduzco caminos fraccionados.
adrianN
3
@adrianN Aunque en un gráfico como ese, la ausencia de una arista corresponde a un valor asociado infinito y no a cero.
CodesInChaos
0

Piense en un gráfico del sistema de carreteras en Cambridge, Reino Unido, las notas se comparten entre los ciclistas y los conductores de automóviles, al igual que la mayoría de los bordes. Hacerlo disminuye enormemente el costo de mantener los datos.

Ahora, si definimos el peso del borde como el tiempo de viaje en segundos, cada borde tendrá dos pesos, uno para los autos y otros para las bicicletas. Algunos pesos serán infinitos ya que los automóviles no están permitidos en ciclovías.

Ahora considere dos cruces de carreteras que están tan cerca uno del otro tan cerca que solo son aserrados por unas pocas publicaciones que detienen a los conductores de automóviles. (Por ejemplo, una encrucijada, donde las unidades de automóviles solo pueden girar a la izquierda, pero los ciclistas pueden ir en cualquier dirección). Luego obtenemos algunas aristas con un peso infinito de los conductores de automóviles y 0 de peso para los ciclistas.

(Claramente, el gráfico podría procesarse previamente para crear un gráfico más simple para el enrutamiento de los ciclistas, antes de encontrar las mejores rutas).

Ian Ringrose
fuente
No veo cómo esto aborda la pregunta. La pregunta se refiere a aristas con peso cero. En su ejemplo (que, por cierto, podría no tener mucho sentido para las personas que no están familiarizadas con Cambridge), cada borde ya tiene dos pesos. Ahora, en la medida en que pueda definir gráficos ponderados como desee, está bien, pero no parece estar respondiendo a la pregunta formulada. Además, los bordes que describe todos parecen tener al menos un peso muy pequeño para los ciclistas: incluso moverse una distancia corta requiere una cantidad de tiempo distinta de cero.
David Richerby
@DavidRicherby, solo asuma que no se registran tiempos de menos de 1 segundo.
Ian Ringrose
0

Parece que está usando el peso para tratar de representar dos aspectos claramente diferentes del gráfico. El primero es si el gráfico realmente tiene un borde representable (dibujado), y el segundo es su peso real.

Como ha notado, cae en una situación confusa si ha utilizado 'no cero' como indicador de que hay un borde presente (y necesitaría dibujarlo o enumerarlo), mientras que al mismo tiempo ahora ha encontrado una situación donde el peso cero se clasifica como válido.

Esencialmente, necesitará otra forma de representar la presencia del borde (suponiendo que realmente lo necesite, y no pueda simplemente crear un conjunto de pesas N ^ 2, pero luego cae en la trampa de necesitar decidir qué hacer con el bucle bordes traseros ...)

Philip Oakley
fuente
No estoy seguro de que esto realmente responda la pregunta. La pregunta es sobre si los gráficos pueden tener bordes de peso cero; su respuesta es principalmente sobre cómo se podría implementar una estructura de datos para gráficos con bordes de peso cero.
David Richerby
@DavidRicherby, Cerrar; (Mi respuesta) fue más sobre por qué y cómo surgió (o pudo haber surgido) la pregunta: un problema de XYProplem. A menudo, ser capaz de racionalizar por qué fue un problema en primer lugar puede ser de gran ayuda para ver cómo la solución es la respuesta correcta y no solo un "dulce"
Philip Oakley