Топологічний граф

Граф із числом непарних схрещень 13 і попарним числом схрещень 15Шаблон:Sfn.

Топологі́чний граф — подання графа на площині, в якому вершини графа подано різними точками, а ребра — дугами Жордана (пов'язані шматки кривих Жордана), що з'єднують відповідні пари точок. Точки, що представляють вершини графа, і дуги, що представляють ребра, називають вершинами та ребрами топологічного графа. Зазвичай передбачається, що будь-які два ребра топологічного графа схрещуються скінченне число разів, причому жодне ребро не проходить через вершину (крім випадку, коли вершина є скінченною точкою ребра) і жодні два ребра не дотикаються між собою (без схрещень). Топологічний граф називають також малюнком графа.

Важливим класом топологічних графів є клас геометричних графів, у яких ребра подано відрізками. (Термін Шаблон:Не перекладено використовують і в ширшому та не цілком чіткому значенні.)

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

Екстремальні задачі топологічних графів

Фундаментальною проблемою екстремальної теорії графів є така: «Яке найбільше число ребер може мати граф з n вершинами, якщо він не містить підграфів із заданого класу заборонених підграфів?». Одним із початкових результатів розв'язання цієї задачі є теорема Турана, в якій є один заборонений підграф — повний граф з k вершинами (k фіксоване). Аналогічні задачі стосуються топологічних та геометричних графів з іншими забороненими геометричними підконфігураціями.

Історично, першою з теорем, що стосуються зазначеної проблематики, була теорема Пала Ердеша, який розширив результат Гайнца Гопфа та Еріки ПаннвіцШаблон:Sfn. Він довів, що найбільша кількість ребер, яка може мати геометричний граф з $n > 2$ вершинами, що не містить двох несхрещених ребер (які навіть не мають спільних кінцевих вершин) дорівнює n. Джон Конвей висловив гіпотезу, що це твердження можна узагальнити до найпростіших топологічних графів. Топологічний граф називають «простим», якщо будь-яка пара його ребер має принаймні одну спільну точку, яка або є кінцевою (вершиною дуги), або спільною внутрішньою точкою двох схрещених дуг. Гіпотезу Конвея про трекли можна тепер переформулювати так: «Простий топологічний граф з $n > 2$ вершинами, в якому жодні два ребра не схрещуються, має не більше n ребер». Першу верхню межу числа ребер такого графа встановили Ловас, Пах і ШегедіШаблон:Sfn. Найменшу відому верхню межу (1,428 n) знайшли Фулек і ПахШаблон:Sfn. Крім геометричних графів відомо, що гіпотеза Конвея про трекли істинна для x-монотонних топологічних графівШаблон:Sfn. Кажуть, що топологічний граф x-монотонний, якщо будь-яка вертикальна пряма перетинає ребро максимум в одній точці.

Алон і Ердеш Шаблон:Sfn ініціювали дослідження з узагальнення поставлених вище питань для випадків, коли заборонена конфігурація складається з k-несхрещених ребер ( $k > 2$ ). Вони довели, що число ребер геометричного графа з n вершинами, що не містить 3-несхрещених ребер, дорівнює O(n). Оптимальну межу близько 2,5n знайшов ЧерніШаблон:Sfn. Для більших значень k першу лінійну верхню межу $O (k^{4} n)$ встановили Пах і ТеречикШаблон:Sfn. Її покращив Тос до $O (k^{2} n)$ Шаблон:Sfn. Про кількість ребер простих топологічних графів, що не мають k-несхрещених ребер, відома тільки верхня межа $O (n \log^{4 k - 8} n)$ Шаблон:Sfn. З цього випливає, що будь-який повний простий топологічний граф з n вершинами має принаймні $c \frac{\log n}{\log \log n}$ ребер. Це значення покращив до $c n^{\frac{1}{2} - ϵ}$ Руїз-ВаргасШаблон:Sfn.

Квазіпланарні графи

Спільну внутрішню точка двох ребер, у якій перше ребро проходить з одного боку другого ребра на його інший бік, називають перетином. Два ребра топологічного графа перетинаються, якщо мають перетин. Для будь-якого цілого $k > 1$ топологічний або геометричний граф називають k-квазіпланарним, якщо він не має k попарно перетинних ребер. За використання такої термінології, якщо топологічний граф 2-квазіпланарний, він є планарним графом. Зі формули Ейлера випливає, що будь-який планарний граф із $n > 2$ вершинами має не більше $3 n - 6$ ребер. Тому будь-який 2-квазіпланарний граф з $n > 2$ вершинами має не більше $3 n - 6$ ребер.

Пах, Шарохі та Марі припустилиШаблон:Sfn, що будь-який k -квазіпланарний топологічний граф з n вершинами має не більше $c (k) n$ ребер, де $c (k)$ — константа, яка залежить тільки від k. Відомо, що ця гіпотеза істинна для $k = 3$ Шаблон:Sfn Шаблон:Sfn та $k = 4$ Шаблон:Sfn. Відомо також, що вона істинна для опуклих геометричних графів (тобто геометричних графів, вершини яких утворюють опуклий n-кутник)Шаблон:Sfn, а також для k-квазіпланарних топологічних графів, ребра яких подано як x-монотонні криві, що перетинають вертикальну прямуШаблон:Sfn Шаблон:Sfn. З останнього результату випливає, що будь-який k-квазіпланарний топологічний граф з n вершинами, ребра якого малюються як x-монотонні криві, має не більше $c (k) n \log n$ ребер за відповідної константи $c (k)$ . Для геометричних графів це твердження довів раніше ВальтрШаблон:Sfn. Найменша відома загальна верхня межа числа ребер k-квазіпланарного топологічного графа дорівнює $n \log^{O (\log k)} n$ Шаблон:Sfn. Попередню версію цього результату опубліковано в статті Якоба Фокса та Яноша ПахаШаблон:Sfn.

Числа перетинів

Відтоді, як Пал Туран під час Другої світової війни сформулював свою задачу про цегельний заводШаблон:Sfn, визначення або оцінення числа перетинів графів було популярною темою в теорії графів та теорії алгоритмівШаблон:Sfn. Однак публікації щодо задачі (явно або неявно) використовували деякі неузгоджені визначення числа перетинів. На це вказали Пах та ТосШаблон:Sfn і запропонували таку термінологію.

Число хрещень (графа $G$ ): найменша кількість точок перетину серед усіх малюнків графа $G$ на площині (тобто всіх подань графа у вигляді топологічного графа) зі властивістю, що ніякі три ребра не проходять через одну й ту саму точку. Це число позначають як $c r (G)$ .

Число попарних перетинів: найменша кількість пар ребер, що перетинаються, серед усіх малюнків графа $G$ . Це число позначають як $p a i r - c r (G)$ .

Число непарних перетинів: найменша кількість пар ребер, які перетинаються непарне число разів серед усіх малюнків графа $G$ . Це число позначають як $o d d - c r (G)$ .

Ці параметри не є незалежними. Маємо $o d d - c r (G) ⩽ p a i r - c r (G) ⩽ c r (G)$ для будь-якого графа $G$ . Відомо що $c r (G) ⩽ 2 (o d d - c r (G))^{2}$ Шаблон:Sfn та $O (pcr (G)^{\frac{3}{2}} \log^{2} pcr (G))$ Шаблон:Sfn, а також, що існує нескінченно багато графів, для яких $p a i r - c r (G) \neq o d d - c r (G)$ Шаблон:Sfn. Попередн. версі. цих результатів оголошено в статті Пелсмаєра, Стефанковича та ШефераШаблон:Sfn. Невідомо жодного прикладу, у якому число перетинів не дорівнює попарному числу перетинів. З Шаблон:Не перекладено Шаблон:Sfn Шаблон:Sfn випливає, що з $o d d - c r (G) = 0$ витікає $c r (G) = 0$ . Відомо також, що з $o d d - c r (G) = k$ випливає $c r (G) = k$ для $k = 1, 2, 3$ Шаблон:Sfn.

Інший добре вивчений параметр графа — число прямолінійних перетинів. Це найменша кількість точок перетинів серед усіх малюнків графа $G$ на площині з ребрами у вигляді відрізків (тобто серед усіх подань у вигляді геометричного графа) з властивістю, що ніякі три ребра не проходять через ту саму точку. Число позначають як $l i n - c r (G)$ .

За визначенням маємо $c r (G) ⩽ l i n - c r (G)$ для будь-якого графа $G$ . Біншток і Дін показали, що є графи з числом перетинів 4 і довільно великим числом прямолінійних перетинівШаблон:Sfn.

Задчі рамсеївського типу для геометричних графів

У традиційній теорії графів типові результати рамсеївського типу стверджують, що при розфарбовуванні ребер досить великого повного графа фіксованою кількістю кольорів, обов'язково буде знайдено монохроматичний підграф певного типуШаблон:Sfn. Можна поставити подібні питання для геометричних (або топологічних) графів, за винятком того, що в цьому випадку шукають монохроматичні (одного кольору) підструктури, що задовольняють певним геометричним умовамШаблон:Sfn. Один із перших результатів такого роду стверджує, що будь-який повний геометричний граф, ребра якого розфарбовані в два кольори, містить монохроматичне кістякове дерево, що не перетинаєтьсяШаблон:Sfn. Правильно також, що будь-який такий геометричний граф містить $⌈ \frac{n + 1}{3} ⌉$ неперетинних ребер одного кольоруШаблон:Sfn. Існування монохроматичних неперетинних шляхів розміру, принаймні, cn, де $c > 0$ є сталою, залишається давньою невирішеною проблемою. Відомо лише, що будь-який повний геометричний граф з n вершинами містить монохроматичний неперетинний шлях довжиною, принаймні, $n^{\frac{2}{3}}$ Шаблон:Sfn.

Топологічні гіперграфи

При аналізі топологічного графа, як топологічної реалізації одновимірного симпліційного комплексу, виникає питання: як описані вище екстремальні задачі рамсеївського типу узагальнити на топологічну реалізацію d-вимірних симпліційних комплексів. Є кілька початкових результатів у цьому напрямі, але вони вимагають подальших досліджень для визначення ключових понять та проблемШаблон:Sfn Шаблон:Sfn Шаблон:Sfn.

Кажуть, що два симплекси, які не мають спільних вершин, перетинаються, якщо їхні відносні внутрішності мають спільну точку. Набори з $k > 3$ симплексів строго перетинаються, якщо жодні з них не мають спільних вершин, але всі вони мають спільну внутрішню точку.

Відомо, що множина d-вимірних симплексів, натягнутих на n точок в $ℝ^{d}$ без пари симплексів, що перетинаються, може мати не більше $O (n^{d})$ симплексів, причому ця межа асимптотично точнаШаблон:Sfn. Цей результат узагальнено на множини двовимірних симплексів $ℝ^{2}$ без того, щоб три з них сильно перетиналисяШаблон:Sfn. Якщо ввести заборону на k симплексів, що сильно перетинаються, то відповідна добре відома верхня межа дорівнює $O (n^{d + 1 - δ})$ Шаблон:Sfn, для деякого $δ = δ (k, d) < 1$ . Цей результат випливає з теореми Тверберга Шаблон:Sfn. Отриманий результат далекий від передбачуваної в гіпотезі межі $O (n^{d})$ Шаблон:Sfn.

Для будь-якого фіксованого $k > 1$ можна вибрати (не більше) $O (n^{⌈ \frac{d}{2} ⌉})$ d-вимірних симплексів, натягнутих на множину з n точок в $ℝ^{d}$ зі властивістю, що жодні k з них не мають спільної внутрішньої точкиШаблон:Sfn Шаблон:Sfn. Ця величина асимптотично точна.

Кажуть, що два трикутники в $ℝ^{3}$ майже не перетинаються, якщо вони не перетинаються, або мають лише одну спільну вершину. Є стара задача Гіля Калая (зі співавторами): визначити, чи дорівнює $o (n^{2})$ найбільшому числу трикутників, що майже не перетинаються, які можна вибрати на деякому наборі вершин з n точок в $ℝ^{3}$ . Відомо, що існують множини з n точок, для яких це число не менше $c n^{\frac{2}{3}}$ для відповідної константи $c > 0$ Шаблон:Sfn.

Примітки

Література

Шаблон:Refbegin

Шаблон:Refend

Топологічний граф

Зміст

Екстремальні задачі топологічних графів

Квазіпланарні графи

Числа перетинів

Задчі рамсеївського типу для геометричних графів

Топологічні гіперграфи

Примітки

Література

Навігаційне меню

Топологічний граф

Екстремальні задачі топологічних графів

Квазіпланарні графи

Числа перетинів

Задчі рамсеївського типу для геометричних графів

Топологічні гіперграфи

Примітки

Література

Навігаційне меню

Пошук