Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Критичний граф граф у якому видалення будь якої вершини або ребра призводить до зменшення хроматичного числа графу Вгорі

Критичний граф

Критичний граф

Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

image
Вгорі зліва — вершинно-критичний граф з хроматичним числом 6. Решта N-1 подграфов мають хроматичне число 5.

Пов'язані визначення

  • image-критичний граф — це критичний граф із хроматичним числом k.
  • Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом.

Властивості

  • Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
    • G має тільки одну компоненту.
    • G — скінченний (теорема де Брёйна — Ердеша ).
    • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язний.
    • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом Kk, або непарним циклом (теорема Брукса).
    • 2m ≥ (k − 1)n + k − 3.
    • 2m ≥ (k − 1)n + [(k − 3)/(k2 − 3)]n.
    • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершин. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершини.
  • Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.
  • 1-критичних графів не існує.
  • Єдиний 2-критичний граф — це K2.
  • Всі 3-критичні графи вичерпуються простими циклами непарної довжини.
  • Як показав Хайош, будь-який k-критичний граф можна сформувати з повного графу Kk комбінацією [ru] з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.
image
4-критичний, але не реберно-критичний граф, оскільки image
  • Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним.

Варіації та узагальнення

  • Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є Kk єдиним двічі критичним k-хроматичним графом.

Див. також

    Примітки

    1. Слід зазначити, що не завжди під критичним графом розуміють критичний k-хроматичний граф. У статті Візінга під критичним графом розмірності k розуміють граф, у якого розмірність будь-якої власної частини менша від k. Під розмірністю графа при цьому розуміють мінімальну розмірність метричного простору, в який можна вкласти граф так, що всі суміжні вершини опиняться на відстані 1. (Визинг, 1968)
    2. de Bruijn, Erdős, 1951.
    3. Lovász, 1992.
    4. Brooks, Tutte, 1941.
    5. Dirac, 1957.
    6. Gallai, 1963a.
    7. Gallai, 1963b.
    8. Stehlík, 2003.
    9. Харари, 2003, с. 167.
    10. Hajós, 1961.
    11. Харари, 2003, с. 168-169.
    12. Erdős, 1966.

    Література

    • R. L. Brooks, W. T. Tutte. On colouring the nodes of a network // Proceedings of the Cambridge Philosophical Society. — 1941. — Т. 37, вип. 02 (17 червня). — С. 194–197. — DOI:10.1017/S030500410002168X.
    • N. G. de Bruijn, P. Erdős. A colour problem for infinite graphs and a problem in the theory of relations // Nederl. Akad. Wetensch. Proc. Ser. A. — 1951. — Т. 54 (17 червня). — С. 371–373.. ( 13.)
    • G. A. Dirac. A theorem of R. L. Brooks and a conjecture of H. Hadwiger // Proceedings of the London Mathematical Society. — 1957. — Т. 7, вип. 1 (17 червня). — С. 161–195. — DOI:10.1112/plms/s3-7.1.161.
    • T. Gallai. Kritische Graphen I // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (17 червня). — С. 165–192.
    • T. Gallai. Kritische Graphen II // Publ. Math. Inst. Hungar. Acad. Sci.. — 1963. — Т. 8 (17 червня). — С. 373–395..
    • . Über eine Konstruktion nicht n-färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. — 1961. — Т. 10 (17 червня). — С. 116–117.
    • T. R. Jensen, B. Toft. Graph coloring problems. — New York : Wiley-Interscience, 1995. — .
    • Matěj Stehlík. Critical graphs with connected complements // . — 2003. — Т. 89, вип. 2 (17 червня). — С. 189–194. — (Series B). — DOI:10.1016/S0095-8956(03)00069-8.
    • László Lovász. Combinatorial Problems and Exercises (Second Edition). — North-Holland, 1992.
    • Paul Erdős. In Theory of Graphs. — Proc. Colloq., Tihany, 1966. — С. 361.
    • В. Г. Визинг. Некоторые нерешенные задачи в теории графов // Успехи Математических Наук. — 1968. — Т. XXIII, вип. 6 (144) (17 червня). — С. 117–134.
    • Ф. Харари. Теория графов. — 2-е. — М. : Едиториал УРСС, 2003. — , ББК 22.144, 22.18, 22.19.

    Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

    Kritichnij graf graf u yakomu vidalennya bud yakoyi vershini abo rebra prizvodit do zmenshennya hromatichnogo chisla grafu Vgori zliva vershinno kritichnij graf z hromatichnim chislom 6 Reshta N 1 podgrafov mayut hromatichne chislo 5 Pov yazani viznachennyak displaystyle k kritichnij graf ce kritichnij graf iz hromatichnim chislom k Graf G z hromatichnim chislom k ye vershinno k kritichnim yaksho kozhna z jogo vershin ye kritichnim elementom VlastivostiNehaj G ye k kritichnim grafom iz n vershinami i m rebrami Todi G maye tilki odnu komponentu G skinchennij teorema de Bryojna Erdesha d G k 1 tobto bud yaka vershina sumizhna shonajmenshe k 1 inshim vershinam Strogishe G reberno k 1 zv yaznij Yaksho graf G k 1 regulyarnij kozhna vershina sumizhna rivno k 1 inshim to graf G abo ye povnim grafom Kk abo neparnim ciklom teorema Bruksa 2m k 1 n k 3 2m k 1 n k 3 k2 3 n Abo G mozhna rozbiti na dva menshih kritichnih grafi z rebrom mizh kozhnoyu paroyu vershin de dvi vershini berutsya z riznih chastin abo graf G maye shonajmenshe 2k 1 vershin Strogishe abo G maye rozklad takogo tipu abo dlya kozhnoyi vershini v grafu G isnuye k rozfarbuvannya v yakomu v ye yedinoyu vershinoyu zi svoyim kolorom a vsi inshi klasi koloriv mayut shonajmenshe dvi vershini Graf G ye vershinno kritichnim todi i tilki todi koli dlya bud yakoyi vershini v isnuye optimalne pidhozhe rozfarbuvannya v yakomu vershina v odna predstavlyaye klas koloru 1 kritichnih grafiv ne isnuye Yedinij 2 kritichnij graf ce K2 Vsi 3 kritichni grafi vicherpuyutsya prostimi ciklami neparnoyi dovzhini Yak pokazav Hajosh bud yakij k kritichnij graf mozhna sformuvati z povnogo grafu Kk kombinaciyeyu ru z operaciyeyu ototozhnennya dvoh nesumizhnih vershin Graf utvorenij takim sposobom zavzhdi vimagaye k koloriv u bud yakomu pravilnomu rozfarbuvanni 4 kritichnij ale ne reberno kritichnij graf oskilki x G x 4 displaystyle chi G x 4 Hocha kozhen reberno kritichnij graf obov yazkovo ye kritichnim zvorotne hibne Napriklad graf navedenij pravoruch ye 4 kritichnim ale ne reberno kritichnim Variaciyi ta uzagalnennyaDvichi kritichnij graf ce zv yaznij graf u yakomu vidalennya bud yakoyi pari sumizhnih vershin zmenshuye hromatichne chislo na 2 Odna z nerozv yazanih zadach chi ye Kk yedinim dvichi kritichnim k hromatichnim grafom Div takozhPrimitkiSlid zaznachiti sho ne zavzhdi pid kritichnim grafom rozumiyut kritichnij k hromatichnij graf U statti Vizinga pid kritichnim grafom rozmirnosti k rozumiyut graf u yakogo rozmirnist bud yakoyi vlasnoyi chastini mensha vid k Pid rozmirnistyu grafa pri comu rozumiyut minimalnu rozmirnist metrichnogo prostoru v yakij mozhna vklasti graf tak sho vsi sumizhni vershini opinyatsya na vidstani 1 Vizing 1968 de Bruijn Erdos 1951 Lovasz 1992 Brooks Tutte 1941 Dirac 1957 Gallai 1963a Gallai 1963b Stehlik 2003 Harari 2003 s 167 Hajos 1961 Harari 2003 s 168 169 Erdos 1966 LiteraturaR L Brooks W T Tutte On colouring the nodes of a network Proceedings of the Cambridge Philosophical Society 1941 T 37 vip 02 17 chervnya S 194 197 DOI 10 1017 S030500410002168X N G de Bruijn P Erdos A colour problem for infinite graphs and a problem in the theory of relations Nederl Akad Wetensch Proc Ser A 1951 T 54 17 chervnya S 371 373 13 G A Dirac A theorem of R L Brooks and a conjecture of H Hadwiger Proceedings of the London Mathematical Society 1957 T 7 vip 1 17 chervnya S 161 195 DOI 10 1112 plms s3 7 1 161 T Gallai Kritische Graphen I Publ Math Inst Hungar Acad Sci 1963 T 8 17 chervnya S 165 192 T Gallai Kritische Graphen II Publ Math Inst Hungar Acad Sci 1963 T 8 17 chervnya S 373 395 Uber eine Konstruktion nicht n farbbarer Graphen Wiss Z Martin Luther Univ Halle Wittenberg Math Natur Reihe 1961 T 10 17 chervnya S 116 117 T R Jensen B Toft Graph coloring problems New York Wiley Interscience 1995 ISBN 0 471 02865 7 Matej Stehlik Critical graphs with connected complements 2003 T 89 vip 2 17 chervnya S 189 194 Series B DOI 10 1016 S0095 8956 03 00069 8 Laszlo Lovasz Combinatorial Problems and Exercises Second Edition North Holland 1992 Paul Erdos In Theory of Graphs Proc Colloq Tihany 1966 S 361 V G Vizing Nekotorye nereshennye zadachi v teorii grafov Uspehi Matematicheskih Nauk 1968 T XXIII vip 6 144 17 chervnya S 117 134 F Harari Teoriya grafov 2 e M Editorial URSS 2003 ISBN 5 354 00301 6 BBK 22 144 22 18 22 19

    Дата публікації:
    Топ