Pytanie o ważenie krawędzi

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
lumen

Pytanie o ważenie krawędzi

Post autor: lumen »

Cześć,

Aktualnie walczę z następującym problemem:

Mam DAG, w którym chcę obciążyć krawędzie. Mam wiele możliwości obciążania krawędzi. Dla uproszczenia załóżmy, że można je ważyć 1 lub 2.

Mam ograniczenie dla wag: Maksymalnie dwa równoległe węzły (poniżej 2,3,4 biegną równolegle) mogą mieć wagę krawędzi 1. Pozostałe muszą mieć wagę 2. Na koniec sumowane są wagi wszystkich ścieżek i przyjmuje się maksimum (powinno być jak najniższe).

Na przykład: 1 / |2 3 4 | | | | 5 | \ | / 6

Węzeł 1 ma trzech następców: 2, 3 i 4 działających równolegle. Potrzebuję czegoś, co waży wykres tak, aby ograniczenie było prawdziwe. W tym przypadku możliwym rozwiązaniem jest: krawędzie 1-4 powinny mieć wagę 2. Wszystkie pozostałe krawędzie powinny mieć wagę 1.

Byłoby wspaniale, gdyby ktoś mógł pomóc. Dzięki.