Разрешен ли ноль в качестве веса ребра в взвешенном графике?

60

Я пытаюсь написать скрипт, который генерирует случайные графы, и мне нужно знать, может ли ребро в взвешенном графе иметь значение 0.

на самом деле имеет смысл, что 0 можно использовать как вес ребра, но я работал с графиками в последние несколько дней, и я никогда не видел пример этого.

введите описание изображения здесь

Taxellool
источник
28
Если отрицательные значения «разрешены», то почему не ноль? :)
Дерек 朕 會 功夫
5
В качестве быстрого примера, если положительные веса представляют чистый расход топлива при перемещении от одного узла к другому, то отрицательные веса могут представлять чистую заправку. Нулевой вес - это то место, где израсходованное топливо точно компенсируется заправкой.
JW
1
@DavidRicherby Я полагаю, что реальный вопрос здесь, например, «правильный ли алгоритм X при наличии весовых нулевых ребер». Иначе, каков контекст? Ответ может быть либо да, либо нет, в зависимости от деталей. Вопрос типа «может ли массив содержать нули» так же важен.
Юхо
1
@Juho: О, это ясно, все в порядке. Это все равно что спросить, может ли число быть отрицательным. Тебе кажется очевидным, что это зависит от контекста, но это не было очевидно для людей, пока не появились отрицательные числа. Даже ноль не был очевиден.
Мердад
1
В зависимости от того, что вы хотите сделать, ваши веса могут даже не быть действительными числами. Например, если ваш график представляет цепь переменного тока, ваши веса могут быть вектором, а это комплексные числа.
user2357112

Ответы:

165

Разрешено кем ? Там нет Центрального Администрации Графа, который решает, что вы можете и не можете делать. Вы можете определять объекты любым удобным для вас способом, если вам ясно, что это за определение. Если ребра с нулевым весом полезны для вас, используйте их; просто убедитесь, что ваши читатели знают, что вы делаете.

Причина, по которой вы обычно не видите ребер с нулевым весом, состоит в том, что в большинстве случаев ребро с нулевым весом точно эквивалентно отсутствию ребра. Например, если ваш график представляет страны и объем торговли между ними, преимущество нулевого веса будет означать отсутствие торговли, что равносильно отсутствию какого-либо преимущества. Если ваш график представляет расстояния, ребро с нулевым весом будет соответствовать двум местам на нулевом расстоянии друг от друга, что будет означать, что они фактически будут одним и тем же местом, поэтому оба должны быть представлены одной и той же вершиной. Однако в других контекстах ребра с нулевым весом могут иметь смысл. Например, если ваш график представляет дорожную сеть, а веса ребер - количество трафика, существует большая разница между дорогой, которой никто не пользуется (край с нулевым весом), и дорогой вообще (без края).

Дэвид Ричерби
источник
1
Стоит отметить, что многие алгоритмы графов явно указывают, работают ли они на графах с отрицательными весами или нет. Я думаю, что это проясняет, что даже отрицательные веса разрешены, в зависимости от контекста.
Mooing Duck
6
@MooingDuck Я думаю, суть вопроса в том, что, хотя алгоритмы действительно часто говорят, работают ли они для отрицательных весов, нулевые веса редко упоминаются. Отрицательные веса гораздо менее необычны, чем ноль, поэтому в данном конкретном контексте я не уверен, что их нужно упоминать.
Дэвид Ричерби
13

Это зависит от контекста. В общем, да, ребра с нулевым и даже отрицательным весом могут быть разрешены. В некоторых конкретных случаях может потребоваться, чтобы веса ребер были неотрицательными или строго положительными (например, алгоритм Дейкстры требует, чтобы веса были неотрицательными).

Том ван дер Занден
источник
Есть ли определенный тип графа, который запрещает ноль? и допускает отрицательные или положительные значения?
Taxellool
9
Msgstr "Взвешенный граф с ненулевым ребром".
Том ван дер Занден
10
@Taxellool Математические объекты не установлены в камне. Не существует фиксированного списка математических объектов с фиксированными именами, которые являются единственными, которые вам разрешено использовать.
Дэвид Ричерби
Зависит от того, какой алгоритм вы используете. Беллман-Форд принимает нули, в то время как в Дейкстре они устранены
Мануэль Азар
5

Как отмечают другие ответы, вы совершенно свободно можете рассматривать (или исключать из рассмотрения) взвешенные графы с ребрами с нулевым весом.

Тем не менее, по моему опыту, обычное соглашение в большинстве применений взвешенных графов - не проводить различий между ребром с нулевым весом и отсутствием ребра. Одна из причин этого заключается в том, что, как правило, взвешенные графы отображаются как обобщения мультиграфов , которые, в свою очередь, являются обобщениями простых графов.

В частности, мультиграф - это граф, который (в отличие от простого графа ) допускает несколько ребер между одной и той же парой узлов. В то время как в простом графе любая пара узлов всегда соединена ребрами 0 или 1, пара узлов в мультиграфе может быть соединена 0, 1, 2, 3 или более (но всегда неотрицательным целым числом ) края.

Обобщение мультиграфа, чтобы учесть дробное число ребер между парой узлов, естественным образом приводит к рассмотрению взвешенных графов, и многие алгоритмы, работающие с произвольными мультиграфами, также могут работать на таких взвешенных графах. Но для таких алгоритмов «вес» ребра действительно означает его кратность . Таким образом, учитывая эту интерпретацию, не может быть значимого различия между «без ребра» и «0 ребрами» между парой узлов: оба означают одно и то же.

Конечно, «взвешенный граф» по определению на самом деле является просто графом с числом, связанным с каждым ребром, и вполне возможно интерпретировать вес как нечто иное, чем кратность, в этом случае различие между отсутствием ребра и нулевым весом край действительно может быть значимым. Но попытка применить стандартные мультиграфные алгоритмы к таким «странно взвешенным графам» вряд ли даст результаты, которые имели бы смысл с точки зрения альтернативной (не кратной) интерпретации весов ребер.

Илмари Каронен
источник
6
То, как «взвешенные» графики отображаются «как правило», очень сильно зависит от вашей области. Когда я моделирую дорожную сеть в виде графика, чтобы найти кратчайшие пути, веса представляют расстояния, я не начинаю с нескольких дорог между перекрестками, а затем представляю дробные дороги.
adrianN
3
@adrianN Хотя на таком графике отсутствие ребра соответствует бесконечному значению, а не нулю.
CodesInChaos
0

Подумайте о графике дорожной системы в Кембридже, Великобритания, заметки разделены между велосипедистами и водителями автомобилей, так что большинство из них. Это значительно снижает стоимость обслуживания данных.

Теперь, если мы определим вес края как время в пути в секундах, то чисто у каждого края будет два веса, один для автомобилей, пыльников для велосипедов. Некоторые веса будут бесконечными, так как машины не допускаются на велосипедных дорожках.

Теперь рассмотрим два дорожных развязки, которые расположены очень близко друг к другу и настолько близко, что их зазубривают лишь несколько постов, которые останавливают водителей. (Например, перекресток, где автомобильные приводы могут поворачивать только налево, но велосипедисты могут двигаться в любом направлении.) Затем мы получаем некоторые ребра с бесконечным весом от водителей автомобилей и 0 весов для велосипедистов.

(Очевидно, что граф можно предварительно обработать, чтобы создать более простой график для маршрутизации велосипедистов, прежде чем разрабатывать лучшие маршруты.)

Ян Рингроз
источник
Я не вижу, как это решает вопрос. Вопрос задается о ребрах с нулевым весом. В вашем примере (который, кстати, может не иметь большого смысла для людей, не знакомых с Кембриджем), каждое ребро уже имеет два веса. Теперь, если вы можете определять взвешенные графики как хотите, это нормально, но, похоже, это не относится к заданному вопросу. Кроме того, все ребра, которые вы описываете, по-видимому, имеют как минимум очень маленький вес для велосипедистов: даже перемещение на небольшое расстояние требует ненулевого количества времени.
Дэвид Ричерби
@DavidRicherby, просто предположите, что время менее 1 секунды не записывается.
Ян Рингроз
0

Похоже, вы используете вес, чтобы попытаться представить два совершенно разных аспекта графика. Во-первых, имеет ли граф фактически представимое (нарисованное) ребро, а во-вторых, его фактический вес.

Как вы заметили, вы попадаете в сбивающую с толку ситуацию, если вы использовали «ненулевой» в качестве индикатора того, что грань присутствует (и ее нужно будет нарисовать или перечислить), в то время как в то же время нашли ситуацию где нулевой вес классифицируется как действительный.

По сути, вам понадобится другой способ представления наличия ребра (при условии, что вам это действительно нужно, и вы не можете просто создать массив весов N ^ 2, но тогда вы попадаете в ловушку необходимости решать, что делать с циклом задние края ...)

Филип Окли
источник
Я не уверен, что это действительно отвечает на вопрос. Вопрос в том, могут ли графы иметь ребра с нулевым весом; Ваш ответ в основном о том, как можно реализовать структуру данных для графов с ребрами с нулевым весом.
Дэвид Ричерби
@DavidRicherby, Close; Это (мой ответ) было больше о том, почему и как возник вопрос (или, возможно, возник) вопрос - проблема XYProplem. Часто способность объяснить, почему это была проблема в первую очередь, может сильно помочь понять, как решение является правильным ответом, а не просто «выдумкой»
Филипп Оукли