Ожина (теорія графів)

В теорії графів ожиною для неорієнтованого графу G називається сімейство зв'язних підграфів графу G, які дотикаються один з одним: для будь-якої пари підграфів, які не мають спільних вершин, має існувати ребро, кінцеві вершини якого лежать в цих двох підграфах. Порядок ожини - це найменший розмір множини вершин G, яка має непорожній перетин з кожним підграфом ожини. Ожини використовують для опису деревної ширини графу G[1].

Ожина порядку чотири в 3×3 ґратці, що складається з шести попарно дотичних зв'язних підграфів

Деревна ширина й укриття

Укриттям порядку k в графі G називається функція β, яка переводить кожну множину X з числом вершин менше k в зв'язний компонент GX таким чином, що будь-які дві підмножини β(X) і β(Y) дотикаються між собою. Тобто, образи β утворюють ожину з порядком k в G. І навпаки, будь-яку ожину можна використати для створення укриття — для кожної множини X з розміром, меншим від порядку ожини, є єдиний зв'язний компонент β(X), що містить всі підграфи в ожині, не зв'язані з X.

Як показали Сеймур і Томас, порядок ожини (або, що еквівалентно, укриття) описує деревну ширину — граф має ожину порядку k в тому і тільки в тому випадку, коли деревна ширина не менша від k − 1[1].

Розмір ожин

Як помітили Грох і Маркс (Marx), експандери з обмеженим степенем мають деревну ширину, пропорційну числу вершин, і щоб включити всі підграфи, які не мають спільних вершин з кожною підмножиною такого розміру, ожина для таких графів повинна містити експоненціально багато різних підграфів. Точніше, для цих графів навіть ті ожини, порядок яких трохи більший від квадратного кореня з деревної ширини, повинні мати експоненціальний розмір. Однак Грох і Маркс також показали, що будь-який граф з деревною шириною k має ожину поліноміального розміру і порядок [2].

Обчислювальна складність

Оскільки ожини можуть мати експоненціальний розмір, не завжди можливо побудувати їх за поліноміальний час для графів з необмеженою деревною шириною. Однак якщо деревна ширина обмежена, поліноміальний час побудови можливий — є можливість знайти ожину порядку k, якщо така існує, за час , де n — число вершин у графі. Можливі навіть швидші алгоритми для графів з малим числом мінімальних сепараторів[3].

Бодлендер, Григор'єв і Костер[4] вивчали евристичні алгоритми пошуку ожин високого порядку. Їхні методи не завжди давали ожини з порядком, близьким до деревної ширини, але для планарних графів вони дають постійний апроксимаційний коефіцієнт. Крейцер і Тазарі[5] пропонують імовірнісні алгоритми пошуку з поліноміальним часом роботи на графах з деревною шириною k ожин поліноміального розміру і порядку , що відповідає логарифмічному множнику порядку, виведеного Грохом і Марксом (Grohe, Marx, 2009) для існування ожин поліноміального розміру.

Примітки

  1. Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // Journal of Combinatorial Theory.  1993. Т. 58, вип. 1 (17 лютого). С. 22–33. — (Series B). DOI:10.1006/jctb.1993.1027. В цій статті ожини названо «сітками» (screens), а їх порядки - «товщиною».
  2. Martin Grohe, Dániel Marx. On tree width, bramble size, and expansion // Journal of Combinatorial Theory.  2009. Т. 99, вип. 1 (17 лютого). С. 218–228. — (Series B). DOI:10.1016/j.jctb.2008.06.004..
  3. Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca. Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings. — Berlin : Springer, 2009. — Т. 5734. — С. 223–234. — (Lecture Notes in Computer Science) DOI:10.1007/978-3-642-03816-7_20..
  4. Bodlaender. Treewidth lower bounds with brambles. Algorithmica. — 2008. — Т. 51. — С. 81–98. DOI:10.1007/s00453-007-9056-z..
  5. Stephan Kreutzer, Siamak Tazari. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). — 2010. — С. 354–364..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.