Pytania otagowane jako graphs

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.

3
Najdłuższa ścieżka w niekierowanym drzewie z tylko jednym przejściem
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źć wierzchołek najdalej od niego. Ta ścieżka jest najdłuższą ścieżką na wykresie.v′v′v' …
3
Algorytm znajdujący liczbę prostych ścieżek od do w
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 szary) żadnego z węzłów, …
4
Zlicz wszystkie nieizomorficzne wykresy o określonym rozmiarze
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 wygeneruje sekwencję niekierowanych wykresów , z następującą właściwością: dla każdego niekierowanego wykresu na wierzchołkach …
2
Skąd wziąć wykresy do przetestowania moich algorytmów wyszukiwania?
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 rzeczywistego (lub sposób pobrania tego rodzaju informacji z map Google lub innego …
2
Jak skutecznie ustalić, czy dana drabina jest ważna?
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 więc na początku sezonu stół wygląda …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
4
Jak znaleźć supergwiazdę w czasie liniowym?
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{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1 z liczba …
7
Algorytm znajdowania średnicy drzewa za pomocą BFS / DFS. Dlaczego to działa?
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 działa? Strona 2 tego zawiera uzasadnienie, ale jest …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
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 podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
2
Dowód kompletności NP problemu z drzewem opinającym
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 zdobione można wykazać, …
3
Kiedy minimalne drzewo rozpinające dla wykresu nie jest unikalne
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 istnieć wiele MST, ale …
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.