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.
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...
Istnieje standardowy algorytm znajdowania najdłuższej ścieżki w nieukierunkowanych drzewach przy użyciu dwóch wyszukiwań w pierwszej kolejności: Uruchom DFS od losowego wierzchołka i znajdź od niego najdalszy wierzchołek; powiedzmy, że to v ′ .vvvv′v′v' Teraz uruchom DFS od aby znaleźć...
Oto standardowy pseudokod pierwszego wyszukiwania szerokości: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!empty(q)) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Tutaj pushi popzakłada się, że są...
Ktoś może zaproponować mi liniowy algorytmu czasu, który wprowadzany jest skierowany acykliczny wykres a dwa wierzchołki i i powraca liczbę prostych odcinków z na w . Mam algorytm, w którym uruchomię DFS (Głębokie pierwsze wyszukiwanie), ale jeśli DFS znajdzie to nie zmieni koloru (z białego na...
W mojej klasie uczeń zapytał, czy wszystkie skończone automaty można narysować bez przekraczania krawędzi (wydaje się, że zrobiły to wszystkie moje przykłady). Oczywiście odpowiedź jest przecząca, oczywisty automat dla języka ma strukturę K_5 , kompletny wykres na pięciu węzłach . Yuval pokazał...
Chciałbym wyliczyć wszystkie niekierowane wykresy wielkości , ale potrzebuję tylko jednego wystąpienia każdej klasy izomorfizmu . Innymi słowy, chcę wyliczyć wszystkie nieizomorficzne (niekierowane) wykresy na wierzchołkach. W jaki sposób mogę to zrobić?nnnnnn Dokładniej, chcę algorytmu, który...
Wdrażam zestaw algorytmów wyszukiwania ścieżek, takich jak Dijkstra's, Depth First itp. Początkowo korzystałem z kilku samodzielnie wykonanych wykresów, ale teraz chciałbym podjąć wyzwanie nieco dalej, dlatego szukam jednego z nich wykresy stosowane w testach porównawczych; wykresy miast świata...
Rozważ skierowane wykresy. Nazywamy węzeł supergwiazdą wtedy i tylko wtedy, gdy nie można do niego dotrzeć z żadnego innego węzła, ale wszystkie inne węzły mają krawędź do . Formalnie:vvvv vvv \qquad \displaystyle v superstar :⟺outdeg(v)=0∧indeg(v)=n−1 superstar :⟺outdeg(v)=0∧indeg(v)=n−1 \text{...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
W moim lokalnym klubie squasha jest drabina, która działa w następujący sposób. Na początku sezonu budujemy tabelę z nazwiskiem każdego członka klubu w osobnej linii. Następnie zapisujemy liczbę wygranych gier i liczbę gier rozegranych przy każdej nazwie (w formie: wygrywa gracz / gry). Tak...
To łącze zapewnia algorytm znajdowania średnicy drzewa bezkierunkowego za pomocą BFS / DFS . Zreasumowanie: Uruchom BFS na dowolnym węźle na wykresie, pamiętając węzeł wykryty jako ostatni. Uruchom BFS, pamiętając ostatnio wykryty węzeł v. d (u, v) to średnica drzewa. Dlaczego to...
Wypróbowałem kilka przypadków i okazało się, że dowolne dwa drzewa rozpinające prostego wykresu mają pewne wspólne krawędzie. Mam na myśli, że do tej pory nie znalazłem żadnego kontrprzykładu. Ale nie mogłem tego udowodnić ani obalić. Jak udowodnić lub obalić tę...
Na nieważonym wykresie bezkierunkowym z wierzchołkami i krawędziami E, takimi jak 2 V > E , jaki jest najszybszy sposób znalezienia wszystkich najkrótszych ścieżek na wykresie? Czy można to zrobić szybciej niż Floyd-Warshall, który jest O ( V 3 ), ale bardzo szybki na iterację?V.VVmiEE2 V.>...
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki...
Szukam wskazówek w pytaniu zadanym przez mojego instruktora. Właśnie dlatego doszedłem do wniosku, że problemem decyzyjnym jest :NP-completeNP-complete\sf{NP\text{-}complete} Na wykresie znajduje się drzewo rozpinające w G, które zawiera dokładny zestaw S = { x 1 , x 2 , … , x n } jako liście. I...
Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G ′G = ( V, E)G=(V,E)G=(V,E)sol′= ( V, E′)G′=(V,E′)G'=(V, E')miEEmi′E′E'Θ ( | V|...
Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że
Biorąc pod uwagę ważony, niekierowany wykres G: Które warunki muszą być spełnione, aby istniało wiele drzew minimalnych obejmujących G? Wiem, że MST jest wyjątkowy, gdy wszystkie wagi są różne, ale nie można odwrócić tego stwierdzenia. Jeśli na wykresie jest wiele krawędzi o tej samej masie, może...
Jeśli wykres ważony ma dwa różne minimalne drzewa i , to prawda, że dla dowolnej krawędzi w liczba krawędzi w ma taką samą wagę jak (w tym sam ) jest taki sam jak liczba krawędzi w o tej samej wadze co ? Jeśli stwierdzenie jest prawdziwe, to jak możemy to udowodnić?T 1 = ( V 1 , E 1 ) E 1 e e E 2...
Muszę znaleźć cykl ujemny na ukierunkowanym wykresie ważonym. Wiem, jak działa algorytm Bellmana Forda i który mówi mi, czy istnieje możliwy do osiągnięcia cykl ujemny. Ale nie określa go wprost. Jak uzyskać rzeczywistą ścieżkę cyklu?v1,v2,…vk,v1v1,v2,…vk,v1v1, v2, \ldots vk, v1 Po zastosowaniu...