Pytania otagowane jako graph-theory

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

3
Udoskonalenia aproksymacji par do analizy sieci
Rozważając interakcje w sieci, zwykle bardzo trudno jest analitycznie obliczyć dynamikę i stosuje się przybliżenia. Przybliżenia pola średniego zwykle całkowicie ignorują strukturę sieci, a zatem rzadko są dobrym przybliżeniem. Popularnym aproksymacją jest aproksymacja pary, która uwzględnia korelacje nieodłączne między sąsiednimi węzłami (intuicyjnie możemy myśleć o tym jako o typie aproksymacji …
1
Funkcja Lovasz theta i wykresy regularne (w szczególności cykle nieparzyste) - związki z teorią spektralną
Wpis dotyczy: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Jak dalece Lovasz jest związany ze zdolnością do zerowego błędu regularnych grafów? Czy istnieją przykłady, w których wiadomo, że ograniczenie Lovasz nie jest równe pojemności zerowego błędu zwykłego wykresu? (Oleksandr Bondarenko odpowiedział poniżej). W szczególności czy znana jest jakakolwiek ścisła nierówność dla nieparzystych cykli boków większych lub …
1
Problem dotyczący minimalnego pokrycia ścieżki
Pracujemy na rozproszonych komputerach i znaleźliśmy problem złożoności, który sprowadza się do minimalnego problemu obejmującego ścieżkę. Obecnie nie wiemy, jak to rozwiązać. Problem jest następujący: Niech będzie liczbą całkowitą, a będzie wykresem zawierającym wierzchołki . Każdy wierzchołek oznaczamy parą taką, że . Odtąd nazywamy wierzchołki za pomocą ich etykiety. Zestaw …
4
Jakie są główne trudności w przechodzeniu od wykresów do hipergraphów?
W kombinatoryce i informatyce istnieje wiele przykładów, w których możemy analizować problem teoretyczny na wykresach, ale w przypadku analogu hipergrraficznego problemu brakuje naszych narzędzi. Jak myślisz, dlaczego problemy często stają się znacznie trudniejsze w przypadku 3-jednolitych hiperrafów niż w przypadku 2-jednolitych wykresów? Jakie są podstawowe trudności? Jedną kwestią jest to, …
1
sieci w odniesieniu do normy cięcia
Przeciętna norma ||A||C||ZA||do||A||_C rzeczywistej macierzy A=(ai,j)∈Rn×nZA=(zaja,jot)∈Rn×nA = (a_{i,j}) \in \mathcal{R}^{n\times n} jest maksimum we wszystkich I⊆ [ n ] ,J⊆ [ n ]ja⊆[n],jot⊆[n]I \subseteq [n], J \subseteq [n] ilości ∣∣∑i ∈I, j ∈ Jzaja , j∣∣|∑ja∈ja,jot∈jotzaja,jot|\left|\sum_{i \in I, j \in J}a_{i,j}\right|. Zdefiniuj odległość między dwiema macierzami ZAZAA i bbB aby …
1
Przycinanie silnie połączonego digrafa
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 algorytmu Floyda-Warshalla, można określić, które krawędzie nigdy nie są najlepszą opcją przejścia od …
1
Znalezienie krótkich i grubych ścieżek
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 krawędzi, musimy nałożyć ograniczenia na ścieżki, które znajdziemy. Na przykład algorytm Edmondsa-Karpa mówi nam, aby znaleźć …
2
Przybliżanie nietrywialnego automorfizmu grafów?
Wykres automorfizmem jest permutacją węzłów wykres indukuje bijection na zestawie krawędź EEE . Formalnie jest to permutacja fff węzłów takich jak (u,v)∈E(u,v)∈E(u,v)\in E iff (f(u),f(v))∈E(f(u),f(v))∈E(f(u),f(v))\in E Zdefiniuj naruszoną krawędź dla pewnej permutacji jako krawędź odwzorowana na inną niż krawędź lub krawędź, której preimage nie jest krawędzią. Dane wejściowe : niesztywny …
1
CSP z nieograniczoną ułamkową szerokością hipertree
za´za´\acute{\rm a}H ∈ P T I M EH.H.HH.H.H∈ P.T.jaM.mi∈P.T.jaM.mi\in PTIME Definicje itp. Świetny przegląd standardowych rozkładów drzew i ich szerokości znajduje się tutaj (Dziękujemy z góry, JeffE!). Niech H.H.H będzie hipergrafatem. Następnie dla hipergraph H.H.H i mapowania γ: E( H) → [ 0 , ∞ )γ:mi(H.)→[0,∞)\gamma : E(H) \rightarrow [0,\infty) …
4
Interesujące funkcje na wykresach, które można skutecznie zmaksymalizować.
Powiedz, że mam wykres ważony G=(V,E,w)G=(V,E,w)G = (V,E,w) taki, że w:E→[−1,1]w:E→[−1,1]w:E\rightarrow [-1,1] jest funkcją ważenia - zwróć uwagę, że dopuszczalne są wagi ujemne. Powiedzieć, że f:2V→Rf:2V→Rf:2^V\rightarrow \mathbb{R} definiuje właściwość każdego podzbioru wierzchołków S⊂VS⊂VS \subset V . fffargmaxS⊆Vf(S)arg⁡maxS⊆Vf(S)\arg\max_{S \subseteq V}f(S) Na przykład funkcja cięcia wykresu jest interesującą właściwością podzbiorów wierzchołków, ale …
1
Źródło modułowego wykresu rozkładu
Podczas wprowadzania modularnego rozkładu grafów większość autorów używa wykresu 11-wierzchołkowego, który kopiuję z wikipedii. Pytanie brzmi, kto jest (są) jego oryginalnymi projektantami. (Nie pytam, kto narysował ten wykres dla wikipedii, ale oryginalne źródło.) Strona wikipedia została utworzona w grudniu 2006 r. Najwcześniejsze źródło, jakie mogę znaleźć, to teza habilitacyjna Christophe …
2
Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?
Pozwolić G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) być losowym wykresem na ≈n3/2≈n3/2\approx n^{3/2}krawędzie Z bardzo dużym prawdopodobieństwemGGG ma wiele 444motocykle. Naszym celem jest wyprodukowanie dowolnego z nich444- motocykle tak szybko, jak to możliwe. Załóżmy, że mamy dostęp do GGG w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w O(n−−√)O(n)O(\sqrt{n}) czas …
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.