Pytania otagowane jako co.combinatorics

Pytania dotyczące kombinatoryki i dyskretnych struktur matematycznych

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
Złożoność decydowania, czy rodzina jest rodziną Sperner
Otrzymujemy rodzinę składającą się z m podzbiorów {1, ..., n}. Czy można znaleźć nietrywialną dolną granicę złożoności decydowania, czy F jest rodziną Spernerów? Trywialna dolna granica to O ( n m ) i mocno podejrzewam, że nie jest ciasna.FF\mathcal{F}mmmFF\mathcal{F}O(nm)O(nm)O(n m) Przypomnij sobie, że zestaw jest rodziną Spernerów, jeśli dla X …
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 …
1
Podziel wykres na cykle rozłączne węzłów
Powiązany problem: Twierdzenie Veblena stwierdza, że ​​„Wykres dopuszcza rozkład cyklu wtedy i tylko wtedy, gdy jest on parzysty”. Cykle są rozłączne na krawędziach, ale niekoniecznie są rozłączne w węzłach. Innymi słowy: „Zestaw krawędzi wykresu można podzielić na cykle, jeśli i tylko wtedy, gdy każdy wierzchołek ma równy stopień”. Mój problem: …
1
Co możemy udowodnić za pomocą nieskończonych wykresów, że bez nich nie możemy udowodnić?
Jest to kontynuacja pytanie na ten temat nieskończonych wykresach. Odpowiedzi i komentarze do tego pytania zawierają listę obiektów i sytuacji, które są naturalnie modelowane przez nieskończone wykresy. Ale istnieją również liczne twierdzenia o grafach nieskończonych (patrz rozdział 8 w książce Diestela), z których na przykład bardzo popularny jest nieskończony lemat …
1
Rozkład grafów połączonych na k na elementy połączone (k + 1)
Połączony wykres można rozłożyć na jego połączone elementy. To drzewo punktów odcięcia bloku jest unikalne. Podobnie, dwupołączone wykresy można rozłożyć na trójkołowe komponenty. Odpowiednie drzewo SPQR opisuje wszystkie cięcia 2-wierzchołkowe na wykresie i jest jednoznacznie określone na podstawie jego wykresu. Ten proces nie uogólnia się na większą łączność. Na przykład, …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
2
Minimalna liczba transpozycji do sortowania listy
Próbując opracować własny algorytm sortowania, szukam optymalnego testu porównawczego, z którym mogę go porównać. W przypadku nieposortowanego uporządkowania elementów A i posortowanego uporządkowania B , jaki jest skuteczny sposób obliczenia optymalnej liczby transpozycji, które można uzyskać od A do B ? Transpozycja jest definiowana jako zmiana pozycji 2 elementów na …
1
Wymiar VC wielomianów nad tropikalnymi półksiężycami?
BPP\mathbf{BPP}P\mathbf{P}poly\mathrm{poly} (max,+)(max,+)(\max,+)(min,+)(min,+)(\min,+) Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , f i ( x ) = Y IFF ı ∈ S . Oznacza to, że wykresy dokładnie tych wielomianów f i z i ∈ …
1
Beigel-Tarui transformacja układów ACC
Czytam dodatek na temat dolnych granic ACC dla NEXP w książce Arora i Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accupt.pdf Jednym z kluczowych lematów jest transformacja z obwodów w wielomianowe wielomianowe nad liczbami całkowitymi o stopniu polilogarytmicznym i quasipolynomialnym współczynnikami lub równoważnie , klasa obwodów S Y M + , która 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.