Warunki, aby wykres dwudzielny był płaski, bez krawędzi biegnących wokół wierzchołków

9

Dwustronny wykres jest płaski, jeśli nie ma nieletnich lub .K3,3K5

Szukam koniecznych i / lub wystarczających warunków, aby umożliwić rysunki planarne bez krawędzi „przechodzących” przez zestawy wierzchołków. Są to rysunki spełniające:

  1. Wszystkie wierzchołki jednej części są rysowane na jednej linii pionowej. Wierzchołki drugiej części są rysowane na równoległej linii pionowej.
  2. Krawędzie nie przecinają się z wyjątkiem wierzchołków.
  3. Krawędzie znajdują się na nieskończonym pasku między dwiema pionowymi liniami w punkcie 1.

Na przykład wszystkie rysunki tutaj oprócz prawego dolnego rogu nie są przykładami. Lewy dolny wykres można ponownie narysować, aby spełnić warunki, zamieniając pozycje Q i R. Górnych dwóch wykresów nie można przerysować, aby spełnić warunki.

wprowadź opis zdjęcia tutaj

Dwa górne wykresy to jedyne przeszkody, jakie mogłem znaleźć. Moje pytania to:

  1. Czy ten problem ma nazwę?
  2. Jakieś inne przeszkody, za którymi tęskniłem?
  3. Wszelkie wskazówki, w jaki sposób mogę udowodnić, że te dwie przeszkody (wraz ze wszystkim, czego mi brakowało), oczywiście jako nieletni, są konieczne i wystarczające.

Zauważ, że to nie jest to samo, co bycie zewnętrznym, jest obrysem zewnętrznym (może być narysowany jako kwadrat), ale nie można go narysować, aby spełnić warunki, o których wspomniałem powyżej.K2,2

aelguindy
źródło

Odpowiedzi:

13

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  . GP=x1x2d(x1)=d(x)=1GP1xixi1xi+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 liniaGx1y1x2y2xkykx1x2x1y2y1x1y1x2y2xi+1xii{1,,k1}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. Gy2y1y3y2zxy2y2zxy1xy3

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

David Richerby
źródło
Bardzo dobra odpowiedź!
Pål GD
0

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ć.

Drugi przypadek ma prawidłowa reprezentacja jeśli przyjmiemy graf dwudzielny, ponieważ Wikipedia definiuje Graf dwudzielny jak: każda krawędź łączy wierzchołek w jednego w .UV

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.V1V2V3V4

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.V1V4

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.

dennlinger
źródło
Dlaczego drugi przypadek nie jest grafem dwustronnym? Krawędź (H, J) łączy tylko H i J i nie dotyka I (tylko rysunek jest trochę zły).
aelguindy,
Cholera, myślałem, że to dwie odrębne krawędzie. Pozwól mi się domyślić, ale powinien on łatwo zostać uwzględniony w bieżącym dowodzie
dennlinger
Rozszerzam kryterium, aby uwzględnić również drugi przypadek. Sprawdzenie jest znacznie łatwiejsze (zarówno pod względem zrozumienia, jak i złożoności), ponieważ ten przypadek należy wziąć pod uwagę tylko wtedy, gdy rozszerzysz wykres za pomocą koncentratora (w mojej definicji dowolny wierzchołek zk>2
dennlinger
Co rozumiesz przez „Pierwszy przypadek polega na tym, że mamy węzeł, który zaczyna się lub kończy na tym samym węźle”? Nie rozumiem, jak twoje rozumowanie potwierdza te stwierdzenia. Udowadniasz, że jeśli robisz rzeczy w określony sposób, nie rysujesz wykresu. Nawet nie rozumiem, jak to poradziłoby sobie z tym, że nie mielibyśmy tych dwóch przeszkód bezpośrednio, ale raczej ich nieletnich ..
aelguindy,
Pierwszym przypadkiem powinno być „ani… ani”. Przepraszam za to. Próbowałem skonstruować dowód, który eliminuje potencjalne podzbiory, które naruszają twój stan, sprawdzając każdą możliwą krawędź.
dennlinger,