Płytka nieletnia - Shallow minor

W teorii grafów , płytkie drobne lub o ograniczonej głębokości drobne drobne to ograniczona forma drobnego grafu , w którym podgrafy, które są skrócone w celu utworzenia drobnego, mają małą średnicę . Płytkich nieletnich przedstawili Plotkin, Rao & Smith (1994) , którzy przypisali swój wynalazek Charlesowi E. Leisersonowi i Sivanowi Toledo.

Definicja

Wykres, który ma cały wykres K 4 jako 1-płytki molowy. Każdy z czterech podzbiorów wierzchołków wskazanych przerywanymi prostokątami indukuje połączony podgraf o promieniu jeden, a pomiędzy każdą parą podzbiorów istnieje krawędź.

Jednym sposobem zdefiniowania drobne danego nieukierunkowane wykres G jest określenie podgrafu H o G , oraz zbiór podzbiorów rozłącznych S I wierzchołków G , z których każdy tworzy się połączony wywołanego podgrafu H I o H . Drugorzędny ma wierzchołek V i dla każdego podzbioru S ma I i krawędź v i v j , gdy istnieje krawędź z S I do S j należącym do H .

W tym sformułowaniu d -moll płytka (alternatywnie nazywana małą o głębokości d ) jest molem, który można zdefiniować w taki sposób, że każdy z podgrafów H i ma promień co najwyżej d , co oznacza, że ​​zawiera centralny wierzchołek c i, który znajduje się w odległości d od wszystkich innych wierzchołków H i . Zauważ, że odległość ta jest mierzona liczbą przeskoków w H i , dlatego może być większa niż odległość w G .

Przypadki specjalne

Płytkie minory o głębokości zerowej są tym samym, co podgrafy danego grafu. Dla wystarczająco dużych wartości d (obejmujących wszystkie wartości co najmniej tak duże, jak liczba wierzchołków), drobne drobne d danego grafu pokrywają się ze wszystkimi jego małymi.

Klasyfikacja rodzin grafów

Nešetřil i Ossona de Mendez (2012) używają płytkich nieletnich do podziału rodzin grafów skończonych na dwa typy. Mówią, że rodzina grafów F jest gdzieś gęsta, jeśli istnieje skończona wartość d, dla której d -płytkie mniejsze grafów w F składają się z każdego skończonego grafu. W przeciwnym razie mówią, że rodzina grafów nigdzie nie jest gęsta . Tę terminologię uzasadnia fakt, że jeśli F jest nigdzie gęstą klasą grafów, to (dla każdego ε > 0) n- wierzchołkowe grafy w F mają krawędzie O ( n 1 + ε ); tak więc grafy nigdzie gęste są grafami rzadkimi .

Bardziej restrykcyjnym typem rodziny grafów, opisanym podobnie, są rodziny grafów o rozwinięciu ograniczonym . Są to rodziny grafów, dla których istnieje funkcja f taka, że ​​stosunek krawędzi do wierzchołków w każdym d -płytkim molowym wynosi co najwyżej f ( d ). Jeśli ta funkcja istnieje i jest ograniczona wielomianem , mówi się, że rodzina grafów ma rozwinięcie wielomianowe.

Twierdzenia o separatorach

Jak pokazali Plotkin, Rao i Smith (1994) , grafy z wykluczonymi płytkimi podrzędnymi można podzielić analogicznie do twierdzenia o separatorze planarnym dla grafów planarnych . W szczególności, jeśli pełna wykres K H nie jest D -shallow drobne o n wykresie -Vertex G , to istnieje podzbiór S o G o wielkości O ( dh 2 log n + n / d ), tak że każdy z połączony składnik G \ S ma co najwyżej 2 n /3 wierzchołków. Wynik jest konstruktywny: istnieje wielomianowy algorytm czasu, który albo znajduje taki separator, albo d -płytki K h -moll. W konsekwencji wykazali, że każda rodzina mniejszych grafów domkniętych podlega twierdzeniu o separatorze prawie tak silnemu, jak to dla grafów planarnych.

Plotkin i in. również zastosował ten wynik do podziału siatek metody elementów skończonych na większe wymiary; dla tego uogólnienia konieczne są płytkie nieistotne, ponieważ (bez ograniczenia głębokości) rodzina siatek w trzech lub więcej wymiarach ma wszystkie grafy jako podrzędne. Teng (1998) rozszerza te wyniki na szerszą klasę wykresów wielowymiarowych.

Bardziej ogólnie, rodzina grafów dziedzicznych ma twierdzenie o separatorze, w którym rozmiar separatora jest potęgą podliniową n wtedy i tylko wtedy, gdy ma rozwinięcie wielomianowe.

Uwagi

Bibliografia

  • Dworzak, Zdenek ; Norin, Sergey (2015), Separatory silnie podliniowe i rozwinięcie wielomianowe , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D.
  • Plotkin, Serge; Rao, Satisz; Smith, Warren D. (1994), „Płytko wykluczone nieletnich i ulepszone rozkłady wykresów”, Proc. V Symp. ACM-SIAM o algorytmach dyskretnych (SODA) , s. 462-470.
  • Teng, Shang-Hua (1998), „Aspekty kombinatoryczne wykresów geometrycznych”, Comput. Geom. , 9 (4): 277–287, doi : 10.1016/S0925-7721(96)00008-9 , MR  1609578.
  • Wulff-Nilsen, Christian (2011), „Twierdzenia o separatorach dla wykresów wolnych od drugorzędnych i płytkich, wolnych od drugorzędnych z aplikacjami”, Proc. 52. Symp. IEEE Podstawy Informatyki (FOCS) , s. 37–46, arXiv : 1107.1292 , doi : 10.1109/FOCS.2011.15.
  • Nešetřil, Jarosław ; Ossona de Mendez, Patrice (2012), rzadkość: wykresy, struktury i algorytmy , algorytmy i kombinatoryka, 28 , Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.