Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

2
Decydujący homomorfizm grafowy
Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników złożoności interesują mnie również pomocne techniki algebraiczne i / lub …
1
Określ minimalną liczbę ważeń monet
W artykule Na temat dwóch problemów teorii informacji Erdõs i Rényi wyznaczają dolne granice minimalnej liczby ważeń, które należy zrobić, aby określić liczbę fałszywych monet w zestawie monet.nnn Bardziej formalnie: Fałszywe monety mają mniejszą wagę niż właściwe monety; znane są wagi i zarówno prawych, jak i fałszywych monet. Podana jest …
2
Amplituda losowych wykresów sześciennych
Rozważ dołączony losowy wykres sześcienny G=(V,E)G=(V,E)G=(V,E) z n=|V|n=|V|n =|V|wierzchołki narysowane z G(n,3G(n,3G(n, 3 reg ))) (jak tu zdefiniowano , tzn. 3n3n3n jest parzyste, a dowolne dwa wykresy mają takie samo prawdopodobieństwo). Oczywiście istnieje nnn możliwe Szerokość najpierw szuka, po jednej dla każdego węzła wyjściowych s∈Vs∈Vs \in V . Przeszukiwanie wszerz …
1
Zwykły wykres wysokiego obwodu z „lokalnie jednolitym” całkowitym porządkiem w węzłach
Definicje Niech i niech d , r i g będą dodatnimi liczbami całkowitymi (z g > 2 r + 1 ).ϵ>0ϵ>0\epsilon > 0dddrrrgggg>2r+1g>2r+1g > 2r+1 Niech są proste, d -regular, nieukierunkowane skończonej wykres z obwodu co najmniej g .G=(V,E)G=(V,E)G = (V,E)dddggg Niech być całkowity porządek na V .≤≤\leVVV Dla każdego …
1
Jaka jest największa różnica między rangą a przybliżoną rangą?
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy. A co z różnicą między rangą a przybliżoną rangą macierzy boolowskiej?
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
Skończona jednokierunkowa permutacja z nieskończoną domeną
Niech będzie permutacją. Zauważ, że chociaż działa w nieskończonej domenie, jego opis może być skończony. Przez opis rozumiem program, który opisuje funkcjonalność . (Jak w złożoności Kołmogorowa.) Zobacz wyjaśnienia poniżej. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon \{0,1\}^* \to \{0,1\}^*ππ\piππ\pi Na przykład funkcja NOT jest jedną z takich permutacji: funkcja NOT (x) Niech y …
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
Znajdowanie podgrafów o wysokiej szerokości i stałym stopniu
Dano mi wykres z szerokością i dowolnym stopniem, i chciałbym znaleźć podrozdział z (niekoniecznie indukowany podsgraf) taki, że ma stały stopień, a jego szerokość jest tak wysoka, jak to możliwe. Formalnie mój problem jest następujący: po wybraniu stopnia związanego , jaka jest najlepsza funkcja tak że na dowolnym wykresieGGG kkkHHHGGGHHHd∈Nd∈Nd …
2
Liczba automorfizmów wykresu dla izomorfizmu grafowego
Niech i będą dwoma połączonymi wykresami regularnymi o rozmiarze . Niech być zbiorem permutacji tak, że . Jeśli następnie jest zestaw automorfizmy o .GGGHHHrrrnnnAAAPPPPGP−1=HPGP−1=HPGP^{-1}=HG=HG=HG=HAAAGGG Jaka jest najbardziej znana górna granica rozmiaru ? Czy są jakieś wyniki dla poszczególnych klas grafów (niezawierających grafów kompletnych / cyklicznych)?AAA Uwaga: Skonstruowanie grupy automorfizmów jest …
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.