Pytania otagowane jako graph-theory

Pytania o grafy, dyskretne struktury węzłów, które są połączone krawędziami. Popularne smaki to drzewa i sieci o dużej pojemności.

5
Maksymalny niezależny zestaw wykresu dwudzielnego
Próbuję znaleźć maksymalny niezależny zestaw wykresu biparytu. W niektórych notatkach „13 maja 1998 r. - University of Washington - CSE 521 - Zastosowania przepływu sieci” znalazłem : Problem: Biorąc pod uwagę dwudzielny wykres , znalezienie niezależnego zestawu , który jest tak duży, jak to tylko możliwe, w którym i . …
4
Dlaczego wykresy skierowane są ważne?
Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Czytaliśmy o algorytmach dla MST, silnej łączności, routingu itp. W grafach ukierunkowanych. Ostatnio ludzie przeprowadzają badania nad algorytmami dynamicznymi i …
1
Liczba cykli hamiltonowskich na wykresie Sierpińskiego
Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie. Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę …
4
Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w …
1
Przekształcanie arbitralnej osłony w osłonę wierzchołków
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 jako najkrótsza odległość w obrębie …
6
Dlaczego DFS nie może być używany do znajdowania najkrótszych ścieżek na nieważonych wykresach?
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 można tego zrobić. Nie jestem przekonany (sam tego nie …
4
Algorytm Dijkstry na wielkich wykresach
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ą biblioteki do obliczania najkrótszych ścieżek na takich …
4
Wykres ma dwa / trzy różne minimalne drzewa rozpinające?
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 znalezienie całkowitej masy minimalnego drzewa opinającego. Później, usuwając krawędź z wykresu …
1
Algorytm
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 istnieje algorytm z czasem wykonania ? …
5
Jakie jest znaczenie ujemnych krawędzi masy na wykresie?
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 wagi? Przydałoby się proste angielskie wyjaśnienie.
2
Skutecznie próbkuj najkrótsze ścieżki
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 nieważony. Nawet w ograniczonych wielu …
2
Jak praktycznie konstruować zwykłe wykresy ekspanderó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 Ramanujana, które są ekspanderami i konstrukcją wykorzystującą produkt …
1
Wydajny algorytm odzyskiwania przejściowego zamknięcia ukierunkowanego wykresu acyklicznego
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 znalezienie których wierzchołki są osiągalne z każdego …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.