Czy jest coś znanego o klasie grafów z właściwością, że wszystkie maksymalne niezależne zbiory mają tę samą liczność, a zatem są maksymalnymi IS?
Na przykład weź zestaw punktów na płaszczyźnie i rozważ wykres przecięcia między wszystkimi segmentami między parami punktów w zestawie. (segmenty-> wierzchołki, przecięcia-> krawędzie). Ten wykres będzie miał powyższą właściwość, ponieważ wszystkie maksymalne IS odpowiadają triangulacjom oryginalnego zestawu punktów. Czy istnieją inne kategorie wykresów, które mają tę właściwość? Czy tę właściwość można łatwo przetestować?
graph-theory
co.combinatorics
László Kozma
źródło
źródło
Odpowiedzi:
Takie wykresy nazywane są dobrze pokrytymi wykresami. Oto najnowszy artykuł na ten temat, w którym wymieniono kilka przydatnych odniesień. Jak wspomniał Suresh, problem rozpoznawania jest wspólny z NP.
Zauważ, że niezależne zestawy wykresu tworzą abstrakcyjny, prosty kompleks. Powstające w ten sposób kompleksy uproszczone nazywane są „kompleksami niezależności” lub „kompleksami flagowymi”. Mówi się, że prosty kompleks jest czysty, jeśli każdy maksymalny simpleks ma tę samą liczność. Możesz więc znaleźć kilka odpowiednich artykułów, wyszukując „kompleks czystego niepodległości” lub „kompleks czystej flagi”.
źródło
Ważna jest właściwość MAKSYMALNA = MAKSYMALNA dla niezależnych zestawów na wykresach i bardziej ogólnych strukturach kombinatorycznych. Interesujące będzie zrozumienie wykresów, na których ta właściwość obowiązuje dla wszystkich indukowanych podsgrafów. Jeden ogólny abstrakcyjny przypadek, w którym mamy MAKSIMUM = MAKSYMALNY, ma miejsce, gdy istnieje podstawowa struktura matroidu, ale istnieje wiele innych przypadków, takich jak przypadek maksymalnych płaskich wykresów wspomnianych w pytaniu. Oto pokrewny przykład: Rozważ n punktów na płaszczyźnie w pozycji wypukłej i niech k będzie liczbą całkowitą. Rozważ wykresy, których wierzchołki są segmentami linii między tymi punktami, w których dwa wierzchołki sąsiadują, jeśli segmenty linii się nie przecinają. Sukienka udowodniła, że dla tego wykresu MAKSIMUM = MAKSIMUM dla niezależnych zestawów.
źródło