Szukam pełnego tekstu wyniku kliknięcia Księżyca i Mosera z 1965 r. O klikach na wykresach (istnieją wykresy z liczbą maksymalnych wykładniczych klik w ). Zapora mojego uniwersytetu nie ma dostępu do konkretnego czasopisma. (W rzeczywistości podgląd zawiera kilka pierwszych zdań dowodu, ale potem pozostawia mnie bez reszty!)
Byłem zainteresowany tym wynikiem związanym z kierunkiem badań, którym podążałem, ale kierunek ten nieznacznie się zmienił, więc moje zainteresowanie jest teraz czysto akademicką ciekawością.
Moje pytanie brzmi:
Czy jest gdzieś link do pełnego tekstu artykułu LUB inny papier, który szkicuje dowód LUB LUB, jeśli szkic jest wystarczająco krótki, aby go odtworzyć tutaj, czy ktoś to wie? Interesuje mnie również klasa grafów z wykładniczą liczbą klików.
Dodałem BibTeX w celach informacyjnych:
@article {springerlink:10.1007/BF02760024,
author = {Moon, J. and Moser, L.},
affiliation = {University of Alberta Edmonton Canada},
title = {On cliques in graphs},
journal = {Israel Journal of Mathematics},
publisher = {Hebrew University Magnes Press},
issn = {0021-2172},
keyword = {Computer Science},
pages = {23-28},
volume = {3},
issue = {1},
url = {http://dx.doi.org/10.1007/BF02760024},
note = {10.1007/BF02760024},
year = {1965}
}
źródło
Odpowiedzi:
Nie mam pod ręką kopii Moon & Moser, ale: maksymalna liczba wyraźnych maksymalnych klików na wykresie węzłowym (przy ) wynosi , lub , zgodnie z wartością mod 3. Myślę, że trochę łatwiej jest zobaczyć to w uzupełniającej się formie liczenia maksimum niezależne zestawy.n > 1 3 n / 3 4 ⋅ 3 ( n - 4 ) / 3 2 ⋅ 3 ( n - 2 ) / 3 nn n > 1 3)n / 3 4 ⋅ 3( n - 4 ) / 3 2 ⋅ 3( n - 2 ) / 3 n
Dolna granica wynosi co tak naprawdę prośbą o, i jest najczęściej podane już w komentarzach powyżej: tworzą wykres z Unii rozłącznych kopii i , używając tyle kopii jak to możliwe. Każdy maksymalny niezależny zestaw ma dokładnie jeden węzeł z każdego z tych pełnych wykresów podrzędnych, z których wynika formuła.K 3 K 3K.2) K.3) K.3)
Wydaje mi się, że górna granica dowodu Księżyca i Mosera polegała na przekształceniu wykresu w formę dolnej granicy (lub formę komplementarną dla maksymalnych klików), na każdym kroku nie zmniejszając liczby niezależnych zbiorów lub klik. Ale istnieje inny sposób udowodnienia tego, który prowadzi do algorytmów cofania optymalnych w najgorszym przypadku, umożliwiających wyświetlanie wszystkich klików lub niezależnych zestawów (patrz np. Mój artykuł arXiv: cs / 0011009 ), który tutaj naszkicuję tylko dlatego, że szczegóły są trochę nudne. Jeśli na danym wykresie znajduje się wierzchołek stopnia trzeciego lub więcej , wówczas każdy maksymalny niezależny zbiór jest albo maksymalnym niezależnym zbiorem w albo zawieraG G G ∖ v v G vv sol sol G ∖ v v i jest maksymalnym niezależnym zestawem wykresu utworzonego z przez usunięcie i wszystkich jego sąsiadów. Przez indukcję (wprowadzenie wzoru na liczbę niezależnych zestawów na tych dwóch mniejszych wykresach, z niektórymi modami analizy przypadków 3) następuje granica. Z drugiej strony, jeśli nie istnieje wierzchołek wysokiego stopnia, wówczas wykres jest rozłącznym połączeniem ścieżek i cykli, w którym można bezpośrednio obliczyć liczbę niezależnych zbiorów.sol v
źródło
Możesz także poszukać twierdzenia Moon-Moser w książce Fomin-Kratsch Exact Al Algorytmy
źródło
Odpowiedzi, które zostały podane do tej pory, są świetne. Myślałem, że dodam kilka referencji.
Miller, RE i Muller, DE 1960. Problem maksymalnych spójnych podzbiorów. Raport badawczy IBM RC-240, JT Watson Research Center, Yorktown Heights, NY.
Vatter, V. 2011. Maksymalne niezależne zestawy i pokrywy rozdzielające . American Mathematical Monthly 118, 418-423.
Wood, DR 2011. O liczbie maksymalnych niezależnych zestawów na wykresie . CoRR abs / 1104.1243.
źródło
Oto kopia artykułu z 1965 r. Autorstwa Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf
Zauważ, że wynik został po raz pierwszy udowodniony w 1960 roku przez Millera i Mullera: http://users.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf
źródło