Pytania oznaczone «graphs»

13
Przejściowa redukcja DAG

Szukam algorytmu O (V + E) do znajdowania redukcji przechodnich przy danym DAG. To oznacza usunięcie jak największej liczby krawędzi, abyś mógł dosięgnąć v od ciebie, dla dowolnych v iu nadal możesz sięgnąć po usunięciu krawędzi. Jeśli jest to standardowy problem, proszę wskazać mi jakieś...

12
Znajdź najkrótsze ścieżki na zważonym wykresie unipatycznym

Mówi się, że ukierunkowany wykres jest unipatyczny, jeśli dla dowolnych dwóch wierzchołków i na wykresie istnieje co najwyżej jedna prosta ścieżka od do .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Załóżmy, że otrzymałem wykres jednoczynnościowy taki, że każda krawędź ma dodatnią lub ujemną wagę, ale nie...

12
Badania w teorii grafów a algorytmy grafowe

Mam bardzo ogólne pytanie. Jest to związane z badaniami. Interesuje mnie teoria grafów. Zrobiłem w tym kurs. Zrobiłem kilka tematów związanych z teorią grafów z punktu widzenia robienia tego jako student matematyki, a także studiowałem niektóre algorytmy grafów. Idę na staż badawczy z teorii...

12
Rekonstrukcja wykresów z rozkładu stopni

Biorąc pod uwagę rozkład stopni, jak szybko możemy zbudować wykres zgodny z danym rozkładem stopni? Szkic łącza lub algorytmu byłby dobry. Algorytm powinien zgłaszać „brak”, ponieważ nie można zbudować żadnego wykresu i dowolnego przykładu, jeśli można zbudować wiele...

11
Czy to trudne NP? Nie mogę tego udowodnić.

Mam problem i myślę, że jest to trudny NP, ale nie mogę tego udowodnić. Oto wykres warstw, w którym warstwa 0 jest najwyższą warstwą, a warstwa L najniższą. istnieje pewna ukierunkowana krawędź między warstwami, gdzie krawędź (A, B) wskazuje, że węzeł A może [pokrywać] węzeł B. A kiedy A może...

11
Wnioskowanie o rodzajach uściślenia

W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...

11
Ukierunkowane znalezienie związku

Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.GGG Przykład: las rozłączny Rozważ następujący zestaw zapytań: arrow(u, v) equiv(u, v) find(u) pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny...