www.wikidata.uk-ua.nina.az

Інваріант Колен де Вердьєра Інваріа нт Колен де Вердьєра характеристика графа μ G displaystyle mu G визначена для будь я

Інваріант Колен де Вердьєра

Інваріа́нт Колен де Вердьєра — характеристика графа , визначена для будь-якого графа , яку 1990 року ввів Ів Колен де Вердьє[fr] в процесі дослідження кратності другого власного значення деяких операторів Шредінгера.

Визначення ред.

Нехай  — простий (без петель і кратних ребер) ациклічний граф. Без втрати загальності поіменуємо множину вершин у такий спосіб: . Тоді  — найбільший коранг[en] будь-якої такої симетричної матриці , що:

  • (M1) для будь-яких , де : , якщо , і , якщо ;
  • (M2) має рівно одне від'ємне власне значення кратності ;
  • (M3) не існує такої ненульової матриці , що , і що щоразу, коли або .

Класифікація відомих груп графів ред.

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

Ці ж групи графів проявляють свої відмінні риси і під час аналізу зв'язку між інваріантом графа і доповненням цього графа:

  • Якщо доповнення графа з n вершинами є лінійним лісом, то μ ≥ n − 3;
  • Якщо доповнення графа з n вершинами є зовніпланарним графом, то μ ≥ n − 4;
  • Якщо доповнення графа з n вершинами є планарним графом, то μ ≥ n − 5.

Мінори графів ред.

Мінором графа 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 можна зобразити з одним перетином, і інваріант для них буде не більшим від чотирьох.

Примітки ред.

  1. ↑ (van der Holst, Lovász та Schrijver, 1999).
  2. ↑ (Colin de Verdière, 1990).
  3. У праці (Colin de Verdière, 1990) цей випадок явно не розглянуто, але він явно випливає з результатів аналізу графів, які не мають мінорів виду «трикутник» і «клешня».
  4. ↑ (Lovász та Schrijver, 1998).
  5. ↑ (Kotlov, Lovász та Vempala, 1997).

Посилання ред.

  • Colin de Verdière, Y. (1990). Sur un nouvel invariant des graphes et un critère de planarité. Journal of Combinatorial Theory, Series B 50 (1): 11–21. doi:10.1016/0095-8956(90)90093-F. 
  • van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999). . Graph Theory and Combinatorial Biology (Balatonlelle, 1996). 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ó; Schrijver, Alexander (1998). A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs. Proceedings of the American Mathematical Society 126 (5): 1275–1285. doi:10.1090/S0002-9939-98-04244-0. .
  • Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). . Combinatorica 13: 279–361. doi:10.1007/BF01202354. Архів оригіналу за 10 квітня 2009. Процитовано 20 січня 2022. .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Invaria nt Kolen de Verdyera harakteristika grafa m G displaystyle mu G viznachena dlya bud yakogo grafa G displaystyle G yaku 1990 roku vviv Iv Kolen de Verdye fr v procesi doslidzhennya kratnosti drugogo vlasnogo znachennya deyakih operatoriv Shredingera 1 Zmist 1 Viznachennya 2 Klasifikaciya vidomih grup grafiv 3 Minori grafiv 4 Zv yazok iz hromatichnim chislom 5 Inshi vlastivosti 6 Primitki 7 PosilannyaViznachennya red Nehaj G V E displaystyle G V E nbsp prostij bez petel i kratnih reber aciklichnij graf Bez vtrati zagalnosti poimenuyemo mnozhinu vershin u takij sposib V 1 n displaystyle V 1 dots n nbsp Todi m G displaystyle mu G nbsp najbilshij korang en bud yakoyi takoyi simetrichnoyi matrici M M i j R n displaystyle M M i j in mathbb R n nbsp sho M1 dlya bud yakih i j displaystyle i j nbsp de i j displaystyle i neq j nbsp M i j lt 0 displaystyle M i j lt 0 nbsp yaksho i j E displaystyle i j in E nbsp i M i j 0 displaystyle M i j 0 nbsp yaksho i j E displaystyle i j notin E nbsp M2 M displaystyle M nbsp maye rivno odne vid yemne vlasne znachennya kratnosti 1 displaystyle 1 nbsp M3 ne isnuye takoyi nenulovoyi matrici X X i j R n displaystyle X X i j in mathbb R n nbsp sho M X 0 displaystyle MX 0 nbsp i sho X i j 0 displaystyle X i j 0 nbsp shorazu koli i j displaystyle i j nbsp abo M i j 0 displaystyle M i j neq 0 nbsp 2 1 Klasifikaciya vidomih grup grafiv red Z tochki zoru invarianta Kolen de Verdyera deyaki dobre vidomi simejstva grafiv mayut harakterni osoblivosti m K 1 0 displaystyle mu K 1 0 nbsp m K n n 1 displaystyle mu K n n 1 nbsp m K n 1 displaystyle mu overline K n 1 nbsp pri n gt 1 displaystyle n gt 1 nbsp 1 2 m 1 todi j lishe todi koli G ye linijnim lisom lisom u yakomu kozhen komponent ye shlyahom tobto incidentnist bud yakoyi vershini ne bilsha vid 2 1 3 m 2 todi j lishe todi koli G ye zovniplanarnim grafom usi vershini lezhat na odnij grani 1 2 m 3 todi j lishe todi koli G ye planarnim grafom 1 2 m 4 todi j lishe todi koli G ye nezachepleno vklada nim tobto ne isnuye dvoh cikliv u G dlya yakih pri vidobrazhenni na evklidiv prostir koeficiyent zacheplennya dorivnyuye nulyu 1 4 Ci zh grupi grafiv proyavlyayut svoyi vidminni risi i pid chas analizu zv yazku mizh invariantom grafa i dopovnennyam cogo grafa Yaksho dopovnennya grafa z n vershinami ye linijnim lisom to m n 3 1 5 Yaksho dopovnennya grafa z n vershinami ye zovniplanarnim grafom to m n 4 1 5 Yaksho dopovnennya grafa z n vershinami ye planarnim grafom to m n 5 1 5 Minori grafiv red Minorom grafa G nazivayut graf H otrimanij z G poslidovnim vidalennyam vershin vidalennyam reber i stisnennyam reber Invariant Kolena de Verdyera monotonnij vidnosno operaciyi vzyattya minora v tomu sensi sho minoruvannya grafa ne mozhe zbilshiti jogo invarianta Yaksho H ye minorom G to m H m G displaystyle mu H leq mu G nbsp 2 V teoremi Robertsona Sejmura dlya bud yakogo k isnuye H skinchenna mnozhina grafiv taka sho dlya bud yakogo grafa z invariantom ne bilshim vid k grafi z H ne mozhut buti minorami V roboti Colin de Verdiere 1990 perelicheno mnozhini takih nedopustimih minoriv dlya k 3 dlya k 4 mnozhina nedopustimih minoriv skladayetsya z semi grafiv simejstva Petersena za viznachennyam nezachepleno vkladenogo grafa yak grafa z m 4 i bez grafiv Petersena yak minoriv 4 Zv yazok iz hromatichnim chislom red Kolen de Verdyer Colin de Verdiere 1990 pripustiv sho bud yakij graf z invariantom de Verdera m mozhna rozfarbuvati z vikoristannyam ne bolshe nizh m 1 koloriv Napriklad u linijnih lisiv komponenti yakih ye dvochastkovimi grafami invariant dorivnyuye 1 u zovniplanarnih grafiv invariant dorivnyuye 2 i yih mozhna rozfarbuvati troma kolorami u planarnih grafiv invariant 3 i yih mozhna rozfarbuvati chotirma kolorami Dlya grafiv z invariantom de Verdyera ne bilshe chotiroh pripushennya istinne voni vsi ye nezachepleno vkladanimi i toj fakt sho voni rozfarbovuyutsya p yatma kolorami ye naslidkom dovedennya gipotezi Hadvigera dlya grafiv bez minoriv tipu K6 u roboti Robertsona Sejmura ta Tomasa Robertson Seymour ta Thomas 1993 Inshi vlastivosti red Yaksho chislo peretiniv grafa dorivnyuye k to invariant de Verdyera dlya nogo bude ne bilshim nizh k 3 Napriklad grafi Kuratovskogo K5 i K3 3 mozhna zobraziti z odnim peretinom i invariant dlya nih bude ne bilshim vid chotiroh 2 Primitki red a b v g d e zh i k l van der Holst Lovasz ta Schrijver 1999 a b v g d e Colin de Verdiere 1990 U praci Colin de Verdiere 1990 cej vipadok yavno ne rozglyanuto ale vin yavno viplivaye z rezultativ analizu grafiv yaki ne mayut minoriv vidu trikutnik i kleshnya a b Lovasz ta Schrijver 1998 a b v Kotlov Lovasz ta Vempala 1997 Posilannya red Colin de Verdiere Y 1990 Sur un nouvel invariant des graphes et un critere de planarite Journal of Combinatorial Theory Series B 50 1 11 21 doi 10 1016 0095 8956 90 90093 F van der Holst Hein Lovasz Laszlo Schrijver Alexander 1999 The Colin de Verdiere graph parameter Graph Theory and Combinatorial Biology Balatonlelle 1996 Bolyai Soc Math Stud 7 Budapest Janos Bolyai Math Soc s 29 85 Arhiv originalu za 3 bereznya 2016 Procitovano 20 sichnya 2022 Kotlov Andrew Lovasz Laszlo Vempala Santosh 1997 The Colin de Verdiere number and sphere representations of a graph Combinatorica 17 4 483 521 doi 10 1007 BF01195002 Arhiv originalu za 3 bereznya 2016 Procitovano 20 sichnya 2022 Lovasz Laszlo Schrijver Alexander 1998 A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs Proceedings of the American Mathematical Society 126 5 1275 1285 doi 10 1090 S0002 9939 98 04244 0 Robertson Neil Seymour Paul Thomas Robin 1993 Hadwiger s conjecture for K6 free graphs Combinatorica 13 279 361 doi 10 1007 BF01202354 Arhiv originalu za 10 kvitnya 2009 Procitovano 20 sichnya 2022 Otrimano z https uk wikipedia org w index php title Invariant Kolen de Verdyera amp oldid 39083827