Czy zero jest dozwolone jako waga krawędzi na wykresie ważonym?

Próbuję napisać skrypt, który generuje losowe wykresy i muszę wiedzieć, czy krawędź na wykresie ważonym może mieć wartość 0.

właściwie to ma sens, że 0 może być użyte jako waga krawędzi, ale pracowałem z wykresami w ciągu ostatnich kilku dni i nigdy nie widziałem takiego przykładu.

Pozwolony przez kogo ? Nie ma centralnej administracji grafów, która decydowałaby o tym, co możesz, a czego nie możesz zrobić. Możesz definiować obiekty w dowolny dogodny dla ciebie sposób, o ile masz jasność co do definicji. Jeśli krawędzie zerowane są dla Ciebie przydatne, użyj ich; tylko upewnij się, że czytelnicy wiedzą, że właśnie to robisz.

Powodem, dla którego zwykle nie widzisz krawędzi zerowej jest to, że w większości kontekstów krawędź z zerową wagą jest dokładnie równoważna braku krawędzi. Na przykład, jeśli wykres przedstawia kraje i ilość transakcji między nimi, zerowa waga oznaczałaby brak handlu, co jest tym samym, co brak krawędzi. Jeśli wykres przedstawia odległości, krawędź o zerowej wadze odpowiadałaby dwóm punktom w odległości zero od siebie, co oznaczałoby, że faktycznie byłyby to samo miejsce, więc oba powinny być reprezentowane przez ten sam wierzchołek. Jednak w innych kontekstach krawędzie zerowej wagi mogą mieć sens. Na przykład, jeśli wykres przedstawia sieć dróg, a masy krawędzi reprezentują natężenie ruchu, istnieje duża różnica między drogą, z której nikt nie korzysta (krawędź zerowa), a w ogóle bez drogi (bez krawędzi).

To zależy od kontekstu. Zasadniczo tak, dozwolone mogą być krawędzie zerowe, a nawet ujemne. W niektórych szczególnych przypadkach może być wymagane, aby wagi krawędzi były nieujemne lub ściśle dodatnie (na przykład algorytm Dijkstry wymaga, aby wagi były nieujemne).

Jak zauważają inne odpowiedzi, masz całkowitą swobodę rozważania (lub wykluczania z rozważań) wykresów ważonych z zerowymi krawędziami.

Z mojego doświadczenia wynika , że zwykle w większości zastosowań grafów ważonych nie wprowadza się rozróżnienia między krawędzią zerową a brakiem krawędzi. Jednym z powodów tego jest to, że zazwyczaj wykresy ważone pojawiają się jako uogólnienia multigrafów , które z kolei są uogólnieniami prostych wykresów.

W szczególności multigraf jest wykresem, który (w przeciwieństwie do prostego wykresu ) pozwala na wiele krawędzi między tą samą parą węzłów. Podczas gdy na prostym wykresie dowolna para węzłów jest zawsze połączona przez 0 lub 1 krawędzie, para węzłów w multigrafii może być połączona przez 0, 1, 2, 3 lub więcej (ale zawsze nieujemną liczbę całkowitą ) krawędzie.

Uogólnienie multigrafu, aby umożliwić ułamkową liczbę krawędzi między parą węzłów, naturalnie prowadzi następnie do rozważenia ważonych wykresów, a wiele algorytmów, które działają na dowolnych multigrafach, można również zmusić do pracy na takich ważonych wykresach. Ale w przypadku takich algorytmów „waga” krawędzi naprawdę oznacza jej różnorodność . Zatem, biorąc pod uwagę tę interpretację, nie może być znaczącego rozróżnienia między „bez krawędzi” i „0 krawędzi” między parą węzłów: oba oznaczają dokładnie to samo.

Oczywiście „wykres ważony” z definicji jest w rzeczywistości tylko wykresem z liczbą związaną z każdą krawędzią i jest całkowicie możliwe interpretowanie wagi jako czegoś innego niż wielokrotność, w którym to przypadku rozróżnienie między brakiem krawędzi a zerową wagą przewaga może rzeczywiście mieć znaczenie. Jednak próba zastosowania standardowych algorytmów multigraficznych do takich „dziwnie ważonych wykresów” raczej nie przyniesie rezultatów, które byłyby sensowne z punktu widzenia alternatywnej (niepoliczalności) interpretacji wag krawędzi.

Pomyśl o wykresie układu drogowego w Cambridge w Wielkiej Brytanii, notatki są wspólne dla rowerzystów i kierowców samochodów, podobnie jak większość krawędzi. Takie postępowanie znacznie zmniejsza koszty utrzymania danych.

Jeśli teraz zdefiniujemy ciężar krawędzi jako czas podróży w sekundach, czysto każda krawędź będzie miała dwa obciążniki, jeden dla samochodów innych dla rowerów. Niektóre ciężary będą nieskończone, ponieważ samochody nie są dozwolone na trasach rowerowych.

Teraz rozważ dwa skrzyżowania drogowe, które są bardzo blisko siebie, tak blisko, że są ząbkowane tylko przez kilka słupków, które zatrzymują kierowców samochodów. (Na przykład skrzyżowanie, na którym samochody mogą skręcać tylko w lewo, ale rowerzyści mogą jechać w dowolnym kierunku.) Dostajemy wtedy pewne krawędzie z nieskończoną wagą od kierowców samochodów i zerową wagą dla rowerzystów.

(Oczywiście wykres może być następnie wstępnie przetworzony w celu stworzenia prostszego wykresu dla tras rowerzystów, przed opracowaniem najlepszych tras).

Wygląda na to, że używasz ciężaru, aby spróbować przedstawić dwa wyraźnie różne aspekty wykresu. Pierwszy dotyczy tego, czy wykres rzeczywiście ma reprezentowalną (narysowaną) krawędź, a drugi to jego rzeczywista waga.

Jak zauważyłeś, wpadasz w mylącą sytuację, jeśli użyłeś „niezerowej” jako wskaźnika, że ​​krawędź jest obecna (i trzeba ją narysować lub umieścić na liście), a jednocześnie znalazła sytuację gdzie zerowa waga jest klasyfikowana jako ważna.

Zasadniczo będziesz potrzebować innego sposobu reprezentowania obecności krawędzi (zakładając, że tak naprawdę potrzebujesz, i nie możesz po prostu stworzyć tablicy wag N ^ 2, ale wtedy wpadniesz w pułapkę, że musisz zdecydować, co zrobić z pętlą tylne krawędzie ...)