Pytania otagowane jako graph-theory

Teoria grafów to nauka o grafach, strukturach matematycznych wykorzystywanych do modelowania parowania relacji między obiektami.

1
Odniesienie do algorytmu testowania acykliczności mieszanego grafu?
Wykres mieszany to wykres, który może mieć zarówno skierowane, jak i nieukierowane krawędzie. Podstawowy nieukierowany wykres jest uzyskiwany przez zapomnienie orientacji skierowanych krawędzi, a w drugim kierunku orientacja mieszanego wykresu jest uzyskiwana przez przypisanie kierunku każdej nieukierunkowanej krawędzi. Zestaw krawędzi tworzy cykl na wykresie mieszanym, jeśli można go zorientować w …
4
Problemy z grafem, które są NP-Complete na grafach ukierunkowanych, ale wielomianowe na grafach niekierowanych
Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych. Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej. Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych …
2
Informacje o uogólnionych grafach płaskich i uogólnionych grafach zewnętrznych płaszczyzn
Każdy płaski odpowiednio outerplanar wykres spełnia , odpowiednio | E ′ | ≤ 2 | V ′ | - 3 dla każdego podgrafu G ' = ( V ' , E ' ) z G . Również (zewnętrzne) wykresy płaskie można rozpoznać w czasie wielomianowym.G=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6|E′|≤2|V′|−3|E′|≤2|V′|−3|E'|\le 2|V'|-3G′=(V′,E′)G′=(V′,E′)G'=(V',E')GGG Co wiadomo na …
1
Jaki jest najszybszy algorytm deterministyczny dla dynamicznej osiągalności digrafu bez usuwania krawędzi?
Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi? Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są jednak lepsze algorytmy z tylko wstawianiem krawędzi?
1
Złożoność rozpoznawania grafów przechodnich werteksów
Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik. Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla wierzchołków?GGGnnnnnnGGG Przypomnij sobie, że wykres jest przechodni na wierzchołki, jeśli działa …
1
Liczba cykli hamiltonowskich na losowych wykresach
Zakładamy, że . Zatem dobrze znany jest następujący fakt:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=ln⁡n+ln⁡ln⁡n+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian cycle]={1(c(n)→∞)0(c(n)→−∞)e−e−c(c(n)→c)\begin{eqnarray} Pr [G\mbox{ has a Hamiltonian cycle}]= \begin{cases} 1 & (c(n)\rightarrow \infty) \\ 0 & (c(n)\rightarrow - \infty) \\ e^{-e^{-c}} & (c(n)\rightarrow c) \end{cases} \end{eqnarray} Chcę poznać …
2
Reprezentowanie wykresów niepłaskich z nakładającymi się okręgami
Wiemy, że możemy przedstawić dowolny wykres płaski za pomocą zestawu kół w płaszczyźnie, znanego jako wykres monety . Każde koło reprezentuje wierzchołek, a pomiędzy dwoma wierzchołkami znajduje się krawędź wtedy i tylko wtedy, gdy koła „pocałują się” na swojej granicy. Załóżmy, że zamiast tego zezwalamy na nakładanie się kół i …
1
Twardość NP problemu podziału grafu?
Jestem zainteresowany tym problemem: Biorąc pod uwagę undirected wykres , Czy istnieje podział na wykresach i takie, że i są izomorficzne?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Tutaj jest podzielony na dwa rozłączne zestawy i . Zestawy i niekoniecznie są rozłączne. i .EEEE1E1E_1E2E2E_2V1V1V_1V2V2V_2E1∪E2=EE1∪E2=EE1∪E2=EV1∪V2=VV1∪V2=VV1∪V2=V Ten problem jest co najmniej tak trudny jak problem z …
2
Znajdowanie k najkrótszych ścieżek za pomocą algorytmu Eppsteina
Próbuję dowiedzieć się, jak działa wykres ścieżki według algorytmu Eppsteina w tym artykule i jak mogę zrekonstruować najkrótszych ścieżek od do z odpowiednią konstrukcją stosu .k s t H ( G )P(G)P(G)P(G)kkkssstttH(G)H(G)H(G) Jak dotąd: out(v)out(v)out(v) zawiera wszystkie krawędzie opuszczające wierzchołek na wykresie , które nie są częścią najkrótszej ścieżce . …
1
Zmniejszanie rozkładu drzewa o minimalnej szerokości w czasie wielomianowym
Jak dobrze wiadomo, rozkład drzewa wykresu składa się z drzewa ze skojarzoną torbą dla każdego wierzchołka , który spełnia następujące warunki:T T v ⊆ V ( G ) v ∈GGGTTTTv⊆V(G)Tv⊆V(G)T_v \subseteq V(G)v∈V(T)v∈V(T)v \in V(T) Każdy wierzchołek występuje w jakimś workiem .TGGGTTT Dla każdej krawędzi znajduje się worek zawierający oba punkty …
2
Czy jest jakiś problem w
ΣP2Σ2P\mathsf{\Sigma^P_2}PP\mathsf{P} na ograniczonych wykresach szerokości drzewa. W rzeczywistości myślę, że te problemy są trudniejsze niż użycie normalnego programowania dynamicznego na wykresach ograniczonej szerokości do ich rozwiązania.
1
Odniesienia do wykresów wolnych od (nieparzystych, dziurawych)?
Wykresy wolne od X to te, które nie zawierają wykresu z X jako indukowanego podgrupy. Otwór jest cykl co najmniej 4 wierzchołków. Odd-dziura jest dziura z nieparzystej liczby wierzchołków. Antihole jest dopełnieniem otworem. Wykresy wolne od (nieparzystej dziury, nieparzystej antihole) są dokładnie idealnymi grafami; to jest twierdzenie Strong Perfect Graph …
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.