Motywacja: W standardowych algorytmach maksymalnego przepływu ścieżki augmentacyjnej wewnętrzna pętla wymaga znalezienia ścieżek od źródła do zatonięcia na ukierunkowanym, ważonym wykresie. Teoretycznie dobrze wiadomo, że aby algorytm nawet zakończył działanie, gdy istnieją nieracjonalne pojemności...
Biorąc pod uwagę silnie połączony wykres G z ważonymi krawędziami, chciałbym zidentyfikować krawędzie, które prawdopodobnie nie są częścią żadnego minimalnie silnie połączonego podgrupy (MSCS) G. Jedną z metod znajdowania takich krawędzi jest zmodyfikowany algorytm Floyda-Warshalla. Korzystając z...
Biorąc pod uwagę skończoną płaszczyznę, mam sześciokątną teselację tej płaszczyzny z regularnym sześciokątem o stałej wielkości. Następnie obliczam wykres G Delaunaya dla teselacji. Biorąc pod uwagę taki wykres G, usuwam określone zestawy węzłów na tym wykresie, aby uzyskać wiele podgraphów G....
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym,...
Z uwagi na skierowany wykres , a dwa wierzchołki s , t ∈ V . Para prostych ścieżek p 1 , p 2 od s do t jest rozłącznymi krawędziami, jeśli nie dzielą krawędzi.G = ( V, E)G=(V,E)G = (V,E)s , t ∈ V.s,t∈Vs,t \in Vp1, p2)p1,p2p_1,p_2sssttt Za pomocą maksymalnego przepływu łatwo jest zdecydować, czy...
Motywacja Pewnego dnia podróżowałem po mieście środkami transportu publicznego i stworzyłem interesujący problem graficzny, modelujący problem znalezienia najkrótszego połączenia między dwoma miejscami. Wszyscy znamy klasyczny „problem najkrótszej ścieżki”: biorąc pod uwagę ukierunkowany wykres...
Niech będzie prostym nieukierowanym wykresem na wierzchołkach i krawędziach.n mG=(V,E)sol=(V.,mi)G=(V,E)nnnmmm Próbuję określić czas oczekiwany prowadzeniem algorytmu Wilsona do generowania losowych rozpinające drzewo . Tam pokazano, że to , gdzie to średni czas uderzenia : gdzie:O ( τ )...
Czy istnieje algorytm wielomianowy do znalezienia - jeśli taki istnieje - pająka rozpinającego danego wykresu ? Pająk to drzewo z co najmniej jednym węzłem o stopniu większym niż 2: Wiem, że różne warunki stopnia na (zasadniczo wystarczająco duże stopnie węzła) gwarantują istnienie pająka...
Biorąc pod uwagę zestaw punktów w trójwymiarowej przestrzeni kartezjańskiej, szukam algorytmu, który posortuje te punkty, tak aby zminimalizować minimalną odległość euklidesową między dwoma kolejnymi punktami. Byłoby również korzystne, gdyby algorytm miał tendencję do wyższej średniej odległości...
Chciałbym wiedzieć, czy wcześniej zbadano następujący prosty problem i czy znane jest jakieś rozwiązanie. Niech G będzie siatką skończoną (MxN), S podzbiorem komórek G („okruchy”). Mówi się, że dwie okruchy są (lokalnie) połączone, jeśli ich współrzędne różnią się co najwyżej o jeden (tj. Jeśli...
Biorąc pod uwagę płaski wykres nieważony i zbiór par wierzchołków ( k ≥ 2 jest stałą), znajdź k ścieżek rozłącznych wierzchołków (z wyjątkiem źródła) od s do t i tak, że długość najdłuższej ścieżki jest zminimalizowana.( s , t1) , … , ( S , tk)(s,t1),…,(s,tk)(s,t_1),\dots,(s,t_k)k ≥...
Biorąc pod uwagę wykres G1, G2 i G3, chcemy wykonać test izomorfizmu F między G1 i G2 oraz G1 i G3. Jeśli G2 i G3 są bardzo podobne, tak że G3 powstaje przez usunięcie jednego węzła i wstawienie jednego węzła z G2, a mamy wynik F (G1, G2), czy możemy obliczyć F (G1, G3) bez obliczania go od zera...
Jaka jest złożoność następującego problemu ( P? NP-trudny?):∈∈\in Dane wejściowe: ukierunkowany wykres acykliczny , zestaw tylnych krawędzi E ′ ⊂ V × V i dwa odrębne węzły sD=(V,E)D=(V,E)D=(V,E)E′⊂V×VE′⊂V×VE'\subset V\times Vsss i .ttt Pytanie: Niech oznacza wykres utworzony przez dodanie do D...
Dla nieukierunkowane wykres i dany zbiór S wierzchołków, co jest znane asymptotycznie najszybciej Algorytm znalezienia prostą drogę, zawierający wszystkie elementy S . Co jeśli wymagamy, aby ścieżka była jak
Napraw . Dla każdego wystarczająco dużego chcielibyśmy oznaczyć wszystkie podzbiory wielkości dokładnie dodatnimi liczbami całkowitymi z . Chcielibyśmy, aby to etykietowanie spełniało następującą właściwość: istnieje zestaw liczb całkowitych , uln { 1 .. n } n / k { 1 ... T } S.k ≥ 5k≥5k\ge5nnn{ 1...
Rozważ dołączony niekierowany wykres z nieujemnymi wagami krawędzi i dwoma wyróżnionymi wierzchołkami . Poniżej przedstawiono niektóre problemy ze ścieżką, które mają następującą postać: znajdź ścieżkę , tak aby jakaś funkcja ciężaru krawędzi na ścieżce była minimalna. W tym sensie wszyscy są...
Biorąc pod uwagę rodzinę najwyżej n podzbiorów { 1 , 2 , … , n } . Zamknięcie związek C jest inny zestaw rodziny C zawierający każdy zestaw, które mogą być skonstruowane poprzez związek 1 lub więcej grup w F . Przez | C | oznaczymy liczbę zestawów w C .faF\mathcal Fnnn{ 1 , 2 , … , n }{1,2,…,n}\{...
Drzewo opinające wykresu nazywane jest drzewem kompletności, jeśli zbiór jego liści indukuje całkowity podrozdział na grafie gospodarza. Biorąc pod uwagę wykres i liczbę całkowitą , jaka jest złożoność decyzji, czy zawiera drzewo kompletności z co najwyżej liści?GsolGkkkGGGkkk Powodem zadawania...
Po równoważnych pytaniach dotyczących kompletności NP (patrz pytanie wagi i pytanie kierowane ) zastanawiałem się, w jaki sposób atrybuty te wpływają na sparametryzowane problemy. Które problemy z twardym grafem są trudne dla na grafach ukierunkowanych, ale stały parametr można traktować na...
Czy następujący problem decyzyjny NP-zupełny: Niech będzie nieukierowanym wykresem i dwiema liczbami całkowitymi. Czy można wybrać dla każdego wierzchołka dokładnie różnych sąsiadów, tak że żaden węzeł nie zostanie wybrany więcej niż razy.GGGb≤cb≤cb \le cGGGbbbccc Przypadek można rozwiązać...