Топологічна теорія графів розділ теорії графів що вивчає вкладення графів в поверхні просторове вкладення і графи як топ

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

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

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

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

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

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

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

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

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

Див. також

Примітки

Gross, Tucker та +1987.
Graph topology, from PlanetMath.
John Shareshian, Michelle L. Wachs (2004). Torsion in the matching complex and chessboard complex. arXiv:math.CO/0409054.
Hopcroft, Tarjan та +1974.
Chung, Leighton, Rosenberg, 1987.

[FOOTNOTEGross,_Tucker+1987-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.

[FOOTNOTEHopcroft,_Tarjan+1974-4] Hopcroft, Tarjan та +1974.

[FOOTNOTEChung,_Leighton,_Rosenberg1987-5] Chung, Leighton, Rosenberg, 1987.