Loading AI tools
З Вікіпедії, вільної енциклопедії
Кубі́чний граф в теорії графів — це граф, всі вершини якого мають степінь три. Інакше кажучи, кубічний граф це 3-регулярний граф. Кубічні графи також називають тривале́нтними гра́фами.
Бікубі́чний граф — кубічний двочастковий граф.
1932 року Рональд Фостер почав збирати приклади кубічних симетричних графів, що поклало початок списку Фостера.[1] Багато відомих графів є кубічними та симетричними, включаючи такі графи, як «Вода, газ та електрика», граф Петерсена, граф Хівуда, граф Мебіуса — Кантора, граф Паппа, граф Дезарга, граф Науру, граф Коксетера, граф Татта — Коксетера, граф Діка, граф Фостера і граф Бігса — Смітта. Вільям Татт класифікував симетричні кубічні графи по їх меншому цілого номера s, при якому будь-які два орієнтованих шляху довжини s можуть бути переведені один в інший єдиною симетрією графа. Він показав, що s не перевищує 5, і навів приклади графів для всіх значень s від 1 до 5.[2]
Напівсиметричні кубічні графи включають граф Грея (найменший напівсиметричний кубічний граф), граф Любляни і 12-клітка Татта.
Граф Фрухта є одним з двох найменших кубічних графів без симетрій — він має єдиний автоморфізм — тотожний автоморфізм.
Згідно з теоремою Брукса будь-який кубічний граф, відмінний від повного графа K4, можна розфарбувати в три кольори. Таким чином, будь-який кубічний граф, відмінний від K4, має незалежну множину, що має не менш n/3 вершин, де n — число вершин графа.
Згідно з теоремою Візінга для будь-якого кубічного графа потрібно три або чотири кольори для розмальовки ребер. Хроматичний індекс в 3 кольори відомий як розфарбування Тета, і воно утворює розбиття ребер графа на три досконалих паросполучення. За теоремою Кеніга будь-який бікубічний граф має розмальовку Тета.
Кубічні графи без мостів, які не мають розмальовки Тета, відомі як снарки. Вони включають граф Петерсена, граф Тітце, снарк Блануші, снарк «Квітка», снарк подвійна зірка, снарк Секереша і снарк Уоткінса. Існує нескінченне число різних снарків.[3]
Кубічні графи природним чином виникають у багатьох розділах топології, зокрема, при вивченні CW-комплексів. Також кубічними є графи простих багатогранників в тривимірному просторі, таких, як додекаедр.
Довільне вкладення графа в двовимірну поверхню можна подати у вигляді структури кубічного графа, відомої як карта кодування графа. У цій структурі кожна вершина кубічного графа представляється як прапор вкладення, і являє собою трійку — вершина, ребро та грань. Три сусіди кожного прапора — це три прапори, які можна отримати, змінивши один з елементів прапора та залишивши два інших[4].
Багато робіт присвячено гамільтоновим циклам кубічних графів. 1880 року Пітер Тет висловив гіпотезу, що будь-який кубічний багатогранний граф є гамільтоновим. Але 1946 року Вільям Татт навів контрприклад гіпотезі Тета — граф Татта з 46 вершинами. 1971 року Татт припустив, що всі бікубічні графи — гамільтонові. Однак Джозеф Хортон знайшов контрприклад з 96 вершинами, граф Хортона[5]. Пізніше Марк Еллінгхам побудував два інших приклади — графи Елінгхама — Гортона[en][6][7]. Гіпотеза Барнета — не спростована і не доведена комбінація гіпотез Тета і Татта, — стверджує, що будь бікубічний граф багатогранника є гамільтоновим. Якщо кубічний граф гамільтонів, LCF-нотація дозволяє представити його стисло.
Якщо вибрати кубічний граф випадково з усіх кубічних графів з n вершинами, з великою ймовірністю він буде гамільтоновим — відношення графів з n вершинами, які є гамільтонові, до всіх кубічним графів наближається до одиниці при n наближеним до нескінченності.[8]
Девід Епштейн висловив гіпотезу, що кубічний граф з n вершинами має максимум 2n/3 (що приблизно 1,260n) різних гамільтонових циклів та представив приклади графів з таким числом циклів[9]. Найкраща верхня доведена межа числа різних гамільтонових циклів дорівнює 1,276n[10].
Шляхова ширина будь-якого кубічного графа з n вершинами не перевищує n/6. Однак, найкраща відома нижня межа шляхової ширини графа менша, вона дорівнює 0.082n.[11]
З леми про рукостискання, доведеною Ейлером в 1736, як частини його першої роботи з теорії графів, випливає, що будь який кубічний граф має парне число вершин.
Теорема Петерсона стверджує, що будь кубічний граф без мостів має досконале парування.[12] Ловас і Пламер висловили гіпотезу, що будь кубічний граф без мостів має експоненціальне число досконалих парувань. Гіпотеза була недавно доведена. А саме, було доведено, що будь-який кубічний граф з n вершинами має як мінімум 2n/3656 досконалих парування.[13]
Деякі дослідники вивчали складність експоненційних за часом алгоритмів при застосуванні їх на кубічні графи. Наприклад, при застосуванні динамічного програмування до розкладання графа на шляхи, Фомін і Хойі (Høie) показали як знайти незалежні множини за час O(2n/6 + o(n) ).[11] Задачу комівояжера можна вирішити на кубічних графах за час O(1.251n).[14]
Деякі оптимізаційні задачі на графах є APX-складними, що означає, що хоча для них і існують апроксимаційні алгоритми, гарантована ефективність яких наближається до 1, лише якщо P=NP. До них належать завдання пошуку мінімального вершинного покриття, максимально незалежної множини, мінімальної домінівної множини і максимального розрізу[en].[15] Завдання пошуку числа схрещень (мінімальне число ребер, які перетинаються в будь-якому малюнка графа) кубічного графа є також NP-важкою, але завдання піддається апроксимації.[16] Доведено, що задача комівояжера на кубічних графах NP-важко апроксимувати для будь-якого коефіцієнта, меншого 1153/1152.[17]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
