Інваріа́нт Колен де Вердьєра — характеристика графа , визначена для будь-якого графа , яку ввів [fr] в процесі дослідження кратності другого власного значення деяких операторів Шредінгера.
Визначення
Нехай — простий (без петель і кратних ребер) ациклічний граф. Без втрати загальності поіменуємо множину вершин у такий спосіб:
. Тоді
— найбільший [en] будь-якої такої симетричної матриці
, що:
- (M1) для будь-яких
, де
:
, якщо
, і
, якщо
;
- (M2)
має рівно одне від'ємне власне значення кратності
;
- (M3) не існує такої ненульової матриці
, що
, і що
щоразу, коли
або
.
Класифікація відомих груп графів
З точки зору інваріанта Колен де Вердьєра, деякі добре відомі сімейства графів мають характерні особливості:
,
,
при
;
- μ ≤ 1 тоді й лише тоді, коли G є лінійним лісом (лісом, у якому кожен компонент є шляхом, тобто інцидентність будь-якої вершини не більша від 2);
- μ ≤ 2 тоді й лише тоді, коли G є зовніпланарним графом (усі вершини лежать на одній грані);
- μ ≤ 3 тоді й лише тоді, коли G є планарним графом;
- μ ≤ 4 тоді й лише тоді, коли G є , тобто не існує двох циклів у G, для яких при відображенні на евклідів простір (коефіцієнт зачеплення) дорівнює нулю.
Ці ж групи графів проявляють свої відмінні риси і під час аналізу зв'язку між інваріантом графа і доповненням цього графа:
- Якщо доповнення графа з n вершинами є лінійним лісом, то μ ≥ n − 3;
- Якщо доповнення графа з n вершинами є зовніпланарним графом, то μ ≥ n − 4;
- Якщо доповнення графа з n вершинами є планарним графом, то μ ≥ n − 5.
Мінори графів
(Мінором) графа G називають граф H, отриманий з G послідовним видаленням вершин, видаленням ребер і стисненням ребер. Інваріант Колена де Вердьєра монотонний відносно операції взяття мінора в тому сенсі, що мінорування графа не може збільшити його інваріанта:
- Якщо H є мінором G, то
.
В (теоремі Робертсона — Сеймура), для будь-якого k існує H, скінченна множина графів така, що для будь-якого графа з інваріантом не більшим від k графи з H не можуть бути мінорами. В роботі (Colin de Verdière, 1990) перелічено множини таких недопустимих мінорів для k ≤ 3; для k = 4 множина недопустимих мінорів складається з семи графів (сімейства Петерсена) за визначенням незачеплено вкладеного графа як графа з μ ≤ 4 і без графів Петерсена як мінорів.
Зв'язок із хроматичним числом
Колен де Вердьєр (Colin de Verdière, 1990) припустив, що будь-який граф з інваріантом де Вердьера μ можна розфарбувати з використанням не больше ніж μ + 1 кольорів. Наприклад, у лінійних лісів (компоненти яких є двочастковими графами) інваріант дорівнює 1; у зовніпланарних графів інваріант дорівнює 2 і їх можна розфарбувати трьома кольорами; у планарних графів інваріант — 3 і їх можна розфарбувати чотирма кольорами.
Для графів з інваріантом де Вердьєра не більше чотирьох припущення істинне; вони всі є незачеплено вкладаними, і той факт, що вони розфарбовуються п'ятьма кольорами, є наслідком доведення (гіпотези Хадвігера) для графів без мінорів типу K6 у роботі Робертсона, Сеймура та Томаса (Robertson, Seymour та Thomas, 1993).
Інші властивості
Якщо число перетинів графа дорівнює k, то інваріант де Вердьєра для нього буде не більшим ніж k + 3. Наприклад, графи Куратовського K5 і K3,3 можна зобразити з одним перетином, і інваріант для них буде не більшим від чотирьох.
Примітки
- (van der Holst, Lovász та Schrijver, 1999).
- (Colin de Verdière, 1990).
- У праці (Colin de Verdière, 1990) цей випадок явно не розглянуто, але він явно випливає з результатів аналізу графів, які не мають мінорів виду «трикутник» і «клешня».
- (Lovász та Schrijver, 1998).
- (Kotlov, Lovász та Vempala, 1997).
Посилання
- (1990), Sur un nouvel invariant des graphes et un critère de planarité, , 50 (1): 11—21, doi:10.1016/0095-8956(90)90093-F
- van der Holst, Hein; (Lovász, László); (1999), The Colin de Verdière graph parameter, , Bolyai Soc. Math. Stud., т. 7, Budapest: János Bolyai Math. Soc., с. 29—85, архів оригіналу за 3 березня 2016, процитовано 20 січня 2022.
- Kotlov, Andrew; (Lovász, László); Vempala, Santosh (1997), , Combinatorica, 17 (4): 483—521, doi:10.1007/BF01195002, архів оригіналу за 3 березня 2016, процитовано 20 січня 2022
- (Lovász, László); (1998), A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, , 126 (5): 1275—1285, doi:10.1090/S0002-9939-98-04244-0.
- ; ; (1993), (PDF), , 13: 279—361, doi:10.1007/BF01202354, архів оригіналу (PDF) за 10 квітня 2009, процитовано 20 січня 2022.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет