Топологічна теорія графів

Топологічна теорія графів — розділ теорії графів, що вивчає вкладення графів в поверхні, просторове вкладення і графи як топологічні простори[1]. У цій галузі вивчаються також занурення графів.

Вкладення графу в поверхню означає, що ми хочемо намалювати граф на поверхні, наприклад, на сфері, без перетину ребер. Основне завдання вкладення, представлена ​​у вигляді математичної головоломки — завдання «Вода, газ та електрика». Найбільш значимі програми можна знайти в підготовці друкованих електронних схем, де метою є розвести (вкласти) електронні ланцюги (граф) на друкованій платі (поверхні) без перетинання ланцюгів щоб уникнути короткого замикання.

Графи як топологічні простори

Неорієнтований граф можна розглядати як абстрактний симпліціальний комплекс C, де підмножиною є одноелементні множини (відповідають вершинам) і двоелементні множини (відповідають ребрам)[2]. Геометрична реалізація комплексу |C| складається з копій одиничного інтервалу [0,1] для кожного ребра, при цьому кінці цих інтервалів склеюються в вершинах. З цієї точки зору вкладення графу в поверхню або підрозбиття іншого графу є окремими випадками топологічного вкладення. Гомеоморфізм графів — це просто спеціалізація топологічного гомеоморфізма, поняття зв'язний граф збігається з топологічною зв'язністю, і зв'язний граф є деревом тоді і тільки тоді, коли його фундаментальна група тривіальна.

Інші симпліціальні комплекси, які пов'язані з графами, включають комплекси Уїтні або клікові комплекси, де підмножинами є кліки графу, і комплекси парувань, де підмножинами служать парування графу (еквівалентно, клікові комплекси доповнення реберного графу). Комплекс парувань повного дводольного графу називається комплексом шахової дошки, так як його можна описати як комплекс множин тур на шаховій дошці, які не можуть побити одна одну.[3]

Напрями вивчення

Джон Гопкрофта і Роберт Тар'ян [4] при перевірці планарності графу досягли у середньому лінійного часу, в залежності від кількості ребер. Їх алгоритм робить це шляхом побудови вкладення графу, яке вони називають «пальмою». Ефективність перевірки на планарність має фундаментальне значення для візуалізації графів.

Фан Чанг і ін. [5] вивчали задачу книжкового вкладення графу з вершинами на прямій на корінці книги. Ребра графу малюються на різних сторінках книги так, що ребра які лежать на одній сторінці не перетинаються. Це завдання є абстракцією завдання розводки багатошарових друкованих плат.

Вкладення графів використовується також для доказу структурних результатів на графах за допомогою теорії мінорів графу і структурної теореми графів.

Див. також

Примітки
  1. Gross, Tucker, +1987.
  2. Graph topology, from PlanetMath.
  3. John Shareshian, Michelle L. Wachs (2004). «Torsion in the matching complex and chessboard complex». arXiv:math.CO/0409054.
  4. Hopcroft, Tarjan, +1974.
  5. Chung, Leighton, Rosenberg, 1987.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.