Twoje wykresy są dokładnie wykresami szerokości ścieżki lub równoważnie lasów, z których każdy jest gąsienicą . Gąsienice mają dwie istotne cechy:1
są to drzewa, w których istnieje jedna ścieżka zawierająca każdy wierzchołek stopnia większy niż ;1
są to drzewa, w których każdy wierzchołek ma co najwyżej dwóch sąsiadów niebędących liśćmi.
Lemat 1. Każda gąsienica jest w twojej klasie.
Dowód. Niech będzie gąsienicą, a będzie najdłuższą ścieżką zawierającą każdy wierzchołek stopnia lub więcej. Zauważ, że maksymalnie . Możemy stworzyć rysunek , najpierw rysując jako zygzak, a następnie dodając wierzchołki stopnia- przylegające do między a . solP=x1…xℓ2d(x1)=d(xℓ)=1GP1xixi−1xi+1□
Lemat 2. Każdy wykres w twojej klasie jest acykliczny.G
Dowód. Załóżmy, że zawiera cykl i załóżmy, że ma rysunek wymaganej formy. Wlog, jest powyżej . Ale wtedy musimy mieć powyżej ponieważ w przeciwnym razie linie i przecinałyby się. Przez indukcję jest powyżej dla wszystkich i podobnie dla . Ale potem dowolna liniaGx1y1x2y2…xkykx1x2x1y2y1x1y1x2y2xi+1xii∈{1,…,k−1}yykx1musi albo opuścić obszar między dwiema kolumnami wierzchołków lub przekroczyć każdą drugą krawędź w cyklu. Jest to sprzeczne z naszym założeniem, że wykres ma prawidłowy rysunek. □
Lemat 3. Każda nie związana gąsienica nie jest w twojej klasie.
Dowód. Niech będzie połączonym wykresem, który nie jest gąsienicą. Jeśli zawiera cykl, nie ma go w klasie według Lemat , więc możemy założyć, że jest to drzewo. Jeśli nie jest to gąsienica, musi zawierać wierzchołek z wyraźnymi sąsiadami , i , z których każdy ma stopień co najmniej .G2xy1y2y32
Załóżmy, że mamy rysunek o wymaganych właściwościach. Wlog, jest powyżej a jest powyżej . Niech będzie sąsiadem . Krawędź musi przekroczyć lub , co jest sprzeczne z naszym założeniem, że wykres zawiera rysunek wymaganej formy. Gy2y1y3y2z≠xy2y2zxy1xy3□
Twierdzenie. Twoja klasa grafów jest dokładnie klasą lasów, z których każdy jest gąsienicą.
Dowód. Niech będzie wykresem. Oczywiście, jest w twojej klasie, jeśli i tylko wtedy, gdy każdy komponent jest: jeśli żaden komponent nie może być narysowany zgodnie z wymaganiami, cały wykres nie może; jeśli każdy element można narysować zgodnie z wymaganiami, wówczas można narysować cały wykres, ustawiając elementy jeden nad drugim. Wynik następuje teraz w Lematach i . GG13□
Następstwo. Twoja klasa grafów jest klasą grafów, które nie mają lub poddziału jako drobne.K3K1,3
Dowód. Są to przeszkody dla ścieżki o szerokości 1 . □
Są to w zasadzie przeszkody, które znalazłeś: potrzebujesz zamiast ponieważ ten ostatni dopuszczałby do klasy; podział jest dokładnie twoją drugą przeszkodą.K3K4K3K1,3
Tak więc wymyśliłem następującą odpowiedź:
Jak już wspomniano, istnieją tylko dwa możliwe przypadki, których nie można zmienić.
Edycja: Źle odczytałem wykres, przepraszam za to.
Pozostaje nam to tylko z , co jest warunkiem, którego chcesz uniknąć. Odwrotnie, wystarczającym warunkiem jest to, że twój dwudzielny wykres nie ma w sobie pełnego podgrafu.K2,2
Aby udowodnić, że jakikolwiek inny podgraf jest prawidłowy, możesz wyobrazić sobie następujące rzeczy:
Po pierwsze, zakładamy, że nie mamy krawędzi i zaczynamy od dowolnej krawędzi . Dodając kolejną krawędź, mamy trzy możliwe przypadki:e
Pierwszy przypadek polega na tym, że mamy węzeł, który nie zaczyna się ani nie kończy na tym samym węźle co pierwsza krawędź. To pozostawia nam bez problemu i możemy kontynuować wstawianie.
Drugi przypadek polega na tym, że mamy krawędź, która po drodze przecina inną, już istniejącą, krawędź. W takim przypadku musimy zamienić wierzchołek lub (ten z już istniejącą krawędzią) na jedną z nowych krawędzi lub , tak abyśmy nadal spełniali kryteria.V1 V2 V3 V4
Zakłada się, że nie mamy żadnych dalszych krawędzi rozpoczynających się i kończących w węzłach do zamiany, co prowadzi nas do następującego trzeciego przypadku: Po zamianie jednego z czterech wierzchołków musimy prześledzić wszystkie inne połączenia z zamienionego wierzchołka.V1−V4
Znów możemy znaleźć tylko trzy rozwiązania: albo prześledzimy końcowe połączenie, albo powtórzymy krok, który już zrobiliśmy wcześniej (śledząc wszystkie pozostałe kroki). Jeśli skończymy na końcowym węźle, możemy zamienić wszystkie śledzone węzły.
Ostatni możliwy przypadek doprowadzi do węzła, który już odwiedziliśmy, co dałoby nam pełny podgraph, który możemy następnie zredukować do wspomnianego warunku .K2,2
EDYCJA: Aby rozszerzyć ten dowód na drugi przypadek, musimy spojrzeć na następujące warunki:
Ogólnie rzecz biorąc, jeśli mamy podsgraf z co najmniej jednym hubem (3 lub więcej połączeń), jest to „dość łatwe”.
Nie możemy zmienić kolejności, jeśli mamy wyświetlaną wielkość liter z więcej niż dwoma sąsiadami wyższego stopnia niż jeden ( ). Jest to ważne, ponieważ zapewnia wiedzę o dalszych sąsiadach. Nie musimy nawet śledzić ich dalej, aby uniknąć kręgów (jak w pierwszym przypadku), ale wystarczy sprawdzić bezpośrednich sąsiadów.⟨k⟩>1
Ponieważ sam mam tylko niewielką wiedzę w tej dziedzinie, ale nadal chcę zapewnić możliwe rozwiązanie, podłączyłem do ciebie jeden (mam nadzieję) odpowiedni artykuł
Jeśli ktoś nazwałby ten problem, chciałbym się tego nauczyć, zwłaszcza, że wymyśliłem to rozwiązanie jedynie w oparciu o przemyślenia z twierdzenia Fáry'ego i kompletne dwustronne podrozdziały.
źródło