Pytania otagowane jako graph-theory

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

1
Istnienie długo indukowanych ścieżek na wykresach ekspanderów
Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam się obecnie, czy …
3
NP-pełna właściwość graficzna, która jest dziedziczna, ale nie addytywna?
Właściwość wykresu jest nazywana dziedziczną, jeśli zostanie zamknięta w odniesieniu do usuwania wierzchołków (tj. Wszystkie indukowane podgrupy dziedziczą właściwość). Właściwość graf nazywa się addytywną, jeśli jest zamknięta w odniesieniu do przyjmowania rozłącznych związków. Nie jest trudno znaleźć właściwości dziedziczne, ale nie addytywne. Dwa proste przykłady: \;\;\;(1) Wykres jest kompletny. \;\;\;(2) …
2
Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?
Szukam małego wykresu GGG którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)&lt;χ(G)χv(G)&lt;χ(G)\chi_v(G)<\chi(G) . ( GGG zawiera wektor chromatycznej liczba qqq , jeśli istnieje zadanie x:V→Rdx:V→Rdx\colon V \rightarrow \mathbf R^d , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, ⟨x(v),x(w)⟩≤−1/(q−1)⟨x(v),x(w)⟩≤−1/(q−1)\langle x(v), x(w)\rangle \leq -1/(q-1) …
1
Czy ta klasa wykresów ma nazwę?
Jest sformułowany przez rozszerzenie wykresów progowych . Biorąc pod uwagę wykres progowy gdzie jest kliką, a jest niezależnym zbiorem, moje rozszerzenie jest następujące: Każdy wierzchołek można zastąpić nową kliką tak, że wierzchołki mają to samo sąsiedzi .( C, Ja)(do,ja)(C,I)dodoCjajaIv ∈ Iv∈jav\in IK.vK.vK_vK.vK.vK_vvvv Wydaje mi się, że należało to zbadać, ale …
1
Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez …
1
Kombinatoryczne osadzanie wykresu
Tutaj: http://www.planarity.org/Klein_elementary_graph_theory.pdf (w osadzeniach rozdziałów) podano definicję kombinatorycznego osadzania wykresu płaskiego. (z definicją ścian i tak dalej) Choć można go łatwo zastosować do dowolnego wykresu, definiują wykres płaski jako wykres, dla którego obowiązuje formuła Eulera (zakładając, że wykres jest połączony). Zrozumiałe jest, że dla każdego wykresu płaskiego definicja ścian w …
4
Przyrostowy maksymalny przepływ na wykresach dynamicznych
Szukam szybkiego algorytmu do obliczenia maksymalnego przepływu na wykresach dynamicznych. tzn. biorąc pod uwagę wykres i , mamy maksymalny przepływ w od do . Następnie nowy / stary węzeł dodane / usunięty z jego odpowiednich krawędziach, tworząc krzywą . Jaki jest maksymalny przepływ na nowo utworzonym wykresie? Czy istnieje sposób, …
1
Cytowanie pokazujące osoby niepełnoletnie są nieletnimi topologicznymi dla wykresów podrzędnych
Jeśli jest wykresem w stopniu maksymalnie 3 i jest minor H , a G jest topologiczna minor H .solGGH.HHsolGGH.HH Wikipedia cytuje ten wynik z „Teorii grafów” Diestela. Jest wymieniony jako Prop 1.7.4 w najnowszej wersji książki. W książce brakuje dowodu lub cytowania. Czy miejsce pobytu znane jest z (oryginalnego) dowodu …
4
Jakie jest najważniejsze pojęcie rzadkości w projektowaniu wydajnych algorytmów graficznych?
Istnieje kilka konkurencyjnych pojęć „rzadkiego wykresu”. Na przykład wykres, który można osadzić na powierzchni, można uznać za rzadki. Lub wykres z ograniczoną gęstością krawędzi. Lub wykres z wysokim obwodem. Wykres z dużym rozszerzeniem. Wykres z ograniczoną szerokością. (Nawet w obrębie podpól losowych wykresów jest nieco niejednoznaczne co do tego, co …
1
Czy wykresy „rodzaju zewnętrznego” mają stałą szerokość grzbietu?
Niech i przez zestaw wszystkich wykresów, które mogą być osadzone na powierzchni rodzaju tak, aby wszystkie wierzchołki znajdowały się na zewnętrznej powierzchni . Na przykład jest zbiorem zewnętrznych wykresów płaskich. Czy szerokość wykresów w być ograniczona przez jakąś funkcję ?G k k G 0 G k kk∈Nk∈Nk\in\mathbb{N}GkGkG_kkkkG0G0G_0GkGkG_kkkk Drugi kierunek oczywiście …
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.