Кубічний граф

1932 року Рональд Фостер почав збирати приклади кубічних симетричних графів, що поклало початок списку Фостера.[1] Багато відомих графів є кубічними та симетричними, включаючи такі графи, як «Вода, газ та електрика», граф Петерсена, граф Хівуда, граф Мебіуса — Кантора, граф Паппа, граф Дезарга, граф Науру, граф Коксетера, граф Татта — Коксетера, граф Діка, граф Фостера і граф Бігса — Смітта. Вільям Татт класифікував симетричні кубічні графи по їх меншому цілого номера s, при якому будь-які два орієнтованих шляху довжини s можуть бути переведені один в інший єдиною симетрією графу. Він показав, що s не перевищує 5, і навів приклади графів для всіх значень s від 1 до 5.[2]

Напівсиметричні кубічні графи включають граф Грея (найменший напівсиметричний кубічний граф), граф Любляни і 12-клітка Татта.

Граф Фрухта є одним з двох найменших кубічних графів без симетрій — він має єдиний автоморфізм — тотожний автоморфізм.

Згідно з теоремою Брукса будь-який кубічний граф, відмінний від повного графу K₄, можна розфарбувати в три кольори. Таким чином, будь-який кубічний граф, відмінний від K₄, має незалежну множину, що має не менш n/3 вершин, де n — число вершин графу.

Згідно з теоремою Візінга для будь-якого кубічного графу потрібно три або чотири кольори для розмальовки ребер. Хроматичний індекс в 3 кольори відомий як розфарбування Тета, і воно утворює розбиття ребер графу на три досконалих паросполучення. За теоремою Кеніга будь-який бікубічний граф має розмальовку Тета.

Кубічні графи без мостів, які не мають розмальовки Тета, відомі як снарки. Вони включають граф Петерсена, граф Тітце, снарк Блануші, снарк «Квітка», снарк подвійна зірка, снарк Секереша і снарк Уоткінса. Існує нескінченне число різних снарків.[3]

Кубічні графи природним чином виникають у багатьох розділах топології, зокрема, при вивченні CW-комплексів. Також кубічними є графи простих багатогранників в тривимірному просторі, таких, як додекаедр.

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

Багато робіт присвячено гамільтоновим циклам кубічних графів. 1880 року Пітер Тет висловив гіпотезу, що будь-який кубічний багатогранний граф є гамільтоновим. Але 1946 року Вільям Татт навів контрприклад гіпотезі Тета — граф Татта з 46 вершинами. 1971 року Татт припустив, що всі бікубічні графи — гамільтонові. Однак Джозеф Хортон знайшов контрприклад з 96 вершинами, граф Хортона[5]. Пізніше Марк Еллінгхам побудував два інших приклади — графи Елінгхама — Гортона[6][7]. Гіпотеза Барнета — не спростована і не доведена комбінація гіпотез Тета і Татта, — стверджує, що будь бікубічний граф багатогранника є гамільтоновим. Якщо кубічний граф гамільтонів, LCF-нотація дозволяє представити його стисло.

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

Девід Епштейн висловив гіпотезу, що кубічний граф з n вершинами має максимум 2^n/3 (що приблизно 1,260ⁿ) різних гамільтонових циклів та представив приклади графів з таким числом циклів[9]. Найкраща верхня доведена межа числа різних гамільтонових циклів дорівнює 1,276ⁿ[10].

Шляхова ширина будь-якого кубічного графу з n вершинами не перевищує n/6. Однак, найкраща відома нижня межа шляховий ширини графу менше, вона дорівнює 0.082n.[11]

З леми про рукостискання, доведеною Ейлером в 1736, як частини його першої роботи з теорії графів, випливає, що будь який кубічний граф має парне число вершин.

Теорема Петерсона стверджує, що будь кубічний граф без мостів має досконале парування.[12] Ловас і Пламер висловили гіпотезу, що будь кубічний граф без мостів має експоненціальне число досконалих парувань. Гіпотеза була недавно доведена. А саме, було доведено, що будь-який кубічний граф з n вершинами має як мінімум 2^n/3656 досконалих парування.[13]

Деякі дослідники вивчали складність експоненційних за часом алгоритмів при застосуванні їх на кубічні графи. Наприклад, при застосуванні динамічного програмування до розкладання графу на шляхи, Фомін і Хойі (Høie) показали як знайти незалежні множини за час O(2^{n/6 + o(n)} ).[11] Задачу комівояжера можна вирішити на кубічних графах за час O(1.251ⁿ).[14]

Деякі оптимізаційні задачі на графах є APX-складними, що означає, що хоча для них і існують апроксимаційні алгоритми, гарантована ефективність яких обмежена константою, для них немає наближеної схеми поліноміального часу, гарантована ефективність яких наближається до 1, лише якщо P=NP. До них належать завдання пошуку мінімального вершинного покриття, максимально незалежної множини, мінімальної домінівної множини і максимального розрізу.[15] Завдання пошуку числа схрещувань (мінімальне число ребер, які перетинаються в будь-якому малюнку графу) кубічного графу є також NP-важкою, але завдання піддається апроксимації.[16] Доведено, що задача комівояжера на кубічних графах NP-важко апроксимувати для будь-якого коефіцієнта, меншого 1153/1152.[17]

• Royle, Gordon. Cubic symmetric graphs (The Foster Census). Архів оригіналу за 23 жовтня 2011. Процитовано 28 листопада 2014.
• Weisstein, Eric W. Bicubic Graph(англ.) на сайті Wolfram MathWorld.
• Weisstein, Eric W. Cubic Graph(англ.) на сайті Wolfram MathWorld.