Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie...
Podano wykres płaski G=(V,E)G=(V,E)G=(V,E) i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona...
Klika problem jest znany -Complete problemem przy czym wielkość wymaganej klika jest częścią wejścia. Jednak problem kliki k ma trywialny wielomianowy algorytm czasu ( O ( n k ), gdy k jest stałe). Interesują mnie najlepiej znane górne granice, gdy k jest stałe.NPNPNPO(nk)O(nk)O(n^k)kkk Czy...
Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i...
Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych. Dostępne są...
Robiłem ćwiczenia programowania dynamicznego i znalazłem algorytm Floyda-Warshalla. Najwyraźniej znajduje wszystkie pary najkrótszych ścieżek dla wykresu, który może mieć ujemne krawędzie wagi, ale nie ma ujemnych cykli. Zastanawiam się więc, jakie jest rzeczywiste znaczenie ujemnych krawędzi...
Niektóre prace Conora McBride'a, Diff , Dissect , wiążą pochodną typów danych z ich „typem jednootworowych kontekstów”. Oznacza to, że jeśli weźmiesz pochodną typu, pozostanie ci typ danych, który pokazuje, jak typ danych wygląda od wewnątrz w danym punkcie. Na przykład, jeśli masz listę (w...
Muszę skonstruować wykres ekspandera regularnego d dla niektórych małych stałych d (jak 3 lub 4) n wierzchołków. Jaka jest najłatwiejsza metoda na zrobienie tego w praktyce? Konstruujesz losowy wykres d-regularny, który okazał się być ekspanderem? Czytałem także o konstrukcjach Margulis i grafach...
Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie? Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego? Jak zmienia się algorytm w niekierowanych...
Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej ⌈ nnnnliści. Jak miałbym to robić z indukcją?⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione
Jeśli wykres jest połączony i nie ma ścieżki o długości większej niż k , udowodnij, że co dwie ścieżki w G o długości k mają co najmniej jeden wspólny wierzchołek. GGGkkkGGGkkk Myślę, że ten wspólny wierzchołek powinien znajdować się na środku obu ścieżek. Ponieważ jeśli tak nie jest, możemy mieć...
Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest...
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i...
Jakie są kluczowe różnice między tymi trzema terminami: izomorfizm, automorfizm i homomorfizm w prostym języku laika i dlaczego robimy izomorfizm, automorfizm i
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...
Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne. algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych...
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...
Rozważmy wykres . Każda krawędź ma dwa obciążniki i . Znajdź drzewo które minimalizuje produkt . Algorytm powinien działać w czasie wielomianowym w odniesieniu do.G(V,E)G(V,E)G(V,E)A e B e ( ∑ e ∈ T A e ) ( ∑ e ∈ T B e ) | V | , | E |eeeAeAeA_eBeBeB_e(∑e∈TAe)(∑e∈TBe)(∑e∈TAe)(∑e∈TBe)\left(\sum_{e...
Istnieje rodzina losowych wykresów G ( n , p )G(n,p)G(n, p) z węzłami nnn ( ze względu na Gilberta ). Każda możliwa krawędź jest niezależnie wstawiana do G ( n , p )G(n,p)G(n, p) z prawdopodobieństwem ppp . Niech XkXkX_k będzie liczbą klik o rozmiarze kkk w G ( n , p )G(n,p)G(n, p) . Wiem, że ,...
Rozważ kwadrat, ABCD. Intuicyjnie wydawało mi się, że jego wielomian chromatyczny to λ ( λ - 1 ) ( λ - 1 ) ( λ - 2 )λ(λ-1)(λ-1)(λ-2))\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2) tam, gdzie dostępne są kolory λλ\lambda .. Oznacza to, że istnieje λλ\lambda sposobów na wybranie koloru dla A,...