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
3-розфарбування бідіакіс-куба, приклад вільного від трикутників планарного графа.

Історія

Теорему названо ім'ям німецького математика [en], який опублікував доведення 1959 року. Оригінальне доведення Ґрьоча було складним. Берж спробував спростити його, але його доведення містило помилки.

2003 року Карстен Томассен дав альтернативне доведення, виходячи з пов'язаної теореми — будь-який планарний граф з обхватом щонайменше п'ять має . Однак теорема Ґрьоча сама по собі не розширюється з розфарбування на спискове розфарбування — існують вільні від трикутників планарні графи, які не мають спискового розфарбування в 3 кольори. 1989 року Річард Штайнберг і Ден Юнгер надали перше правильне доведення англійською двоїстої версії цієї теореми. 2012 року Набіха Асгар надав нове істотно простіше доведення теореми, надихнувшись роботою Томассена.

Більші класи графів

Істинний дещо загальніший результат: якщо планарний граф має не більше трьох трикутників, то його можна розфарбувати в 3 кольори. Однак планарний повний граф K4 і нескінченно багато інших планарних графів, що містять K4, містять чотири трикутники і не розфарбовуються в 3 кольори. 2009 року Дворак, Краль і оголосили про доведення іншого узагальнення, гіпотезу про яке висловив 1969 року Л. Хавел: існує стала d така, що, якщо планарний граф має два трикутники на відстані не більше d, то граф можна розфарбувати в три кольори. Частково ця робота стала підставою для [en] Дворака 2015 року

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

Теорему також не можна узагальнити на всі планарні вільні від K4 графи — не будь-який планарний граф, який вимагає 4 кольорів, містить K4. Зокрема, існує планарний граф без 4-циклів, який не можна розфарбувати в 3 кольори.

Розкладання за допомогою гомоморфізмів

Розфарбування в 3 кольори графа G можна описати гомоморфізмом графів із G в трикутник K3. Мовою гомоморфізмів теорема Ґрьоча стверджує, що будь-який вільний від трикутників планарний граф має гомоморфізм графу K3. Насераср показав, що будь-який вільний від трикутників планарний граф також має гомоморфізм у граф Клебша, 4-хроматичний граф. Комбінуючи ці два результати можна показати, що будь-який вільний від трикутників планарний граф має гомоморфізм у вільний від трикутників розфарбовуваний у 3 кольори граф, тензорний добуток K3 з графом Клебша. Розфарбування графа можна тоді отримати суперпозицією цього гомоморфізму з гомоморфізмом із їх тензорного добутку в їхній K3 множник. Однак граф Клебша і його тензорний добуток з K3 не планарні. Не існує вільного від трикутників планарного графа, в який будь-який інший вільний від трикутників планарний граф можна відобразити гомоморфізмом.

Геометричне подання

Результат Кастро, Кобоса, Дана, Маркеса комбінує теорему Ґрьоча з гіпотезою Шейнермана на поданнях планарних графів як графів перетинів відрізків. Вони довели, що будь-який вільний від трикутників планарний граф можна подати набором відрізків з трьома можливими нахилами, так що дві вершини графа суміжні тоді й лише тоді, коли відповідні відрізки перетинаються. 3-розфарбування графа можна тоді отримати, призначивши двом вершинам однаковий колір, якщо їхні відрізки мають однаковий нахил.

Обчислювальна складність

Якщо дано планарний граф без трикутників, 3-розфарбування графа можна отримати за (лінійний час).

Примітки

  1. Berge, 1960.
  2. Grünbaum, 1963.
  3. Thomassen, 2003.
  4. Glebov, Kostochka, Tashkinov, 2005.
  5. Steinberg, Younger, 1989.
  6. Asghar, 2012.
  7. Zdeněk, Kráľ, Thomas, 2009.
  8. The European Prize in Combinatorics. — University of Bergen, 2015. — September. з джерела 20 серпня 2016. Процитовано 2015-09-16..
  9. Heckman, 2007.
  10. Naserasr, 2007, с. Theorem 11.
  11. Nešetřil, Ossona de Mendez, 2012.
  12. de Castro, Cobos, Dana, Márquez, 2002.
  13. Dvořák, Kawarabayashi, Thomas, (2009). Ранні роботи щодо алгоритмів для цієї задачі можна знайти в Kowalik, (2010).

Література

  • Zdeněk Dvořák, Daniel Kráľ, . Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies. — 2009. — 29 червня. — arXiv:0911.0885. — Bibcode:2009arXiv0911.0885D.
  • [1] — University of Bergen, 2015. з джерела 20 серпня 2016
  • Claude Berge. Les problèmes de colaration en théorie des graphs // Publ. Inst. Statist. Univ. Paris. — 1960. — Т. 9 (29 червня). — С. 123–160.. Как процитировано в Grünbaum, (1963).}}
  • de Castro N., Cobos F. J., Dana J. C., Márquez A. Triangle-free planar graphs as segment intersection graphs // . — 2002. — Т. 6, вип. 1 (29 червня). — С. 7–26. — DOI:10.7155/jgaa.00043. з джерела 3 грудня 2008. Процитовано 25 березня 2022.
  • Zdeněk Dvořák, Ken-ichi Kawarabayashi, . Three-coloring triangle-free planar graphs in linear time // Proc. 20th ACM-SIAM Symposium on Discrete Algorithms. — 2009. — С. 1176–1182. — Bibcode:2013arXiv1302.5121D. з джерела 18 жовтня 2012 Архівна копія від 18 жовтня 2012 на Wayback Machine
  • Glebov A. N., Kostochka A. V., Tashkinov V. A. Smaller planar triangle-free graphs that are not 3-list-colorable // Discrete Mathematics. — 2005. — Т. 290, вип. 2–3 (29 червня). — С. 269–274. — DOI:10.1016/j.disc.2004.10.015.
  • Richard Steinberg, Younger D. H. Grötzsch's Theorem for the projective plane // Ars Combinatoria. — 1989. — Т. 28 (29 червня). — С. 15–31.
  • Herbert Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. — Т. 8 (29 червня). — С. 109–120.
  • Branko Grünbaum. Grötzsch's theorem on 3-colorings // Michigan Math. J.. — 1963. — Т. 10, вип. 3 (29 червня). — С. 303–310. — DOI:10.1307/mmj/1028998916.
  • Christopher Carl Heckman. Progress on Steinberg's Conjecture. — 2007. — 29 червня. з джерела 22 липня 2012. Процитовано 2012-07-27.
  • Łukasz Kowalik. Fast 3-coloring triangle-free planar graphs // Algorithmica. — 2010. — Т. 58, вип. 3 (29 червня). — С. 770–789. — DOI:10.1007/s00453-009-9295-2. з джерела 24 вересня 2020. Процитовано 25 березня 2022.
  • Reza Naserasr. Homomorphisms and edge-colourings of planar graphs // . — 2007. — Т. 97, вип. 3 (29 червня). — С. 394–400. — (Series B). — DOI:10.1016/j.jctb.2006.07.001.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. 2.5 Homomorphism Dualities // Sparsity. — Heidelberg : Springer, 2012. — Т. 28. — С. 15–16. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4.
  • Carsten Thomassen. A short list color proof of Grötzsch’s theorem // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вип. 1 (29 червня). — С. 189–192. — DOI:10.1016/S0095-8956(03)00029-7.
  • Nabiha Asghar. Grötzsch's Theorem // Master's Thesis, University of Waterloo. — 2012. — 29 червня. — DOI:10.13140/RG.2.1.1326.9367. з джерела 26 лютого 2019. Процитовано 25 березня 2022.

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

Teorema Grocha tverdzhennya sho bud yakij planarnij graf bez trikutnikiv mozhna rozfarbuvati troma kolorami Zgidno z teoremoyu pro chotiri farbi vershini bud yakogo grafa yakij mozhna namalyuvati na ploshini bez peretiniv reber mozhna rozfarbuvati ne bilshe nizh u chotiri riznih kolori tak sho bud yaki dva kinci bud yakogo rebra matimut rizni kolori Za teoremoyu zh Grocha dostatno lishe tri kolori dlya planarnih grafiv yaki ne mistyat troh pov yazanih odna z odnoyu vershin 3 rozfarbuvannya bidiakis kuba priklad vilnogo vid trikutnikiv planarnogo grafa IstoriyaTeoremu nazvano im yam nimeckogo matematika en yakij opublikuvav dovedennya 1959 roku Originalne dovedennya Grocha bulo skladnim Berzh sprobuvav sprostiti jogo ale jogo dovedennya mistilo pomilki 2003 roku Karsten Tomassen dav alternativne dovedennya vihodyachi z pov yazanoyi teoremi bud yakij planarnij graf z obhvatom shonajmenshe p yat maye Odnak teorema Grocha sama po sobi ne rozshiryuyetsya z rozfarbuvannya na spiskove rozfarbuvannya isnuyut vilni vid trikutnikiv planarni grafi yaki ne mayut spiskovogo rozfarbuvannya v 3 kolori 1989 roku Richard Shtajnberg i Den Yunger nadali pershe pravilne dovedennya anglijskoyu dvoyistoyi versiyi ciyeyi teoremi 2012 roku Nabiha Asgar nadav nove istotno prostishe dovedennya teoremi nadihnuvshis robotoyu Tomassena Bilshi klasi grafivIstinnij desho zagalnishij rezultat yaksho planarnij graf maye ne bilshe troh trikutnikiv to jogo mozhna rozfarbuvati v 3 kolori Odnak planarnij povnij graf K4 i neskinchenno bagato inshih planarnih grafiv sho mistyat K4 mistyat chotiri trikutniki i ne rozfarbovuyutsya v 3 kolori 2009 roku Dvorak Kral i ogolosili pro dovedennya inshogo uzagalnennya gipotezu pro yake visloviv 1969 roku L Havel isnuye stala d taka sho yaksho planarnij graf maye dva trikutniki na vidstani ne bilshe d to graf mozhna rozfarbuvati v tri kolori Chastkovo cya robota stala pidstavoyu dlya en Dvoraka 2015 roku Teoremu ne mozhna uzagalniti na vsi neplanarni grafi bez trikutnikiv ne bud yakij neplanarnij graf bez trikutnikiv mozhna rozfarbuvati v 3 kolori Zokrema graf Grocha i graf Hvatala ye grafami bez trikutnikiv ale vimagayut chotiroh koloriv a michelskian ce peretvorennya grafiv yake mozhna vikoristati dlya pobudovi grafiv bez trikutnikiv dlya yakih potribno dovilno velike chislo koloriv Teoremu takozh ne mozhna uzagalniti na vsi planarni vilni vid K4 grafi ne bud yakij planarnij graf yakij vimagaye 4 koloriv mistit K4 Zokrema isnuye planarnij graf bez 4 cikliv yakij ne mozhna rozfarbuvati v 3 kolori Rozkladannya za dopomogoyu gomomorfizmivRozfarbuvannya v 3 kolori grafa G mozhna opisati gomomorfizmom grafiv iz G v trikutnik K3 Movoyu gomomorfizmiv teorema Grocha stverdzhuye sho bud yakij vilnij vid trikutnikiv planarnij graf maye gomomorfizm grafu K3 Naserasr pokazav sho bud yakij vilnij vid trikutnikiv planarnij graf takozh maye gomomorfizm u graf Klebsha 4 hromatichnij graf Kombinuyuchi ci dva rezultati mozhna pokazati sho bud yakij vilnij vid trikutnikiv planarnij graf maye gomomorfizm u vilnij vid trikutnikiv rozfarbovuvanij u 3 kolori graf tenzornij dobutok K3 z grafom Klebsha Rozfarbuvannya grafa mozhna todi otrimati superpoziciyeyu cogo gomomorfizmu z gomomorfizmom iz yih tenzornogo dobutku v yihnij K3 mnozhnik Odnak graf Klebsha i jogo tenzornij dobutok z K3 ne planarni Ne isnuye vilnogo vid trikutnikiv planarnogo grafa v yakij bud yakij inshij vilnij vid trikutnikiv planarnij graf mozhna vidobraziti gomomorfizmom Geometrichne podannyaRezultat Kastro Kobosa Dana Markesa kombinuye teoremu Grocha z gipotezoyu Shejnermana na podannyah planarnih grafiv yak grafiv peretiniv vidrizkiv Voni doveli sho bud yakij vilnij vid trikutnikiv planarnij graf mozhna podati naborom vidrizkiv z troma mozhlivimi nahilami tak sho dvi vershini grafa sumizhni todi j lishe todi koli vidpovidni vidrizki peretinayutsya 3 rozfarbuvannya grafa mozhna todi otrimati priznachivshi dvom vershinam odnakovij kolir yaksho yihni vidrizki mayut odnakovij nahil Obchislyuvalna skladnistYaksho dano planarnij graf bez trikutnikiv 3 rozfarbuvannya grafa mozhna otrimati za linijnij chas PrimitkiBerge 1960 Grunbaum 1963 Thomassen 2003 Glebov Kostochka Tashkinov 2005 Steinberg Younger 1989 Asghar 2012 Zdenek Kraľ Thomas 2009 The European Prize in Combinatorics University of Bergen 2015 September z dzherela 20 serpnya 2016 Procitovano 2015 09 16 Heckman 2007 Naserasr 2007 s Theorem 11 Nesetril Ossona de Mendez 2012 de Castro Cobos Dana Marquez 2002 Dvorak Kawarabayashi Thomas 2009 Ranni roboti shodo algoritmiv dlya ciyeyi zadachi mozhna znajti v Kowalik 2010 LiteraturaZdenek Dvorak Daniel Kraľ Three coloring triangle free graphs on surfaces V Coloring planar graphs with distant anomalies 2009 29 chervnya arXiv 0911 0885 Bibcode 2009arXiv0911 0885D 1 University of Bergen 2015 z dzherela 20 serpnya 2016 Claude Berge Les problemes de colaration en theorie des graphs Publ Inst Statist Univ Paris 1960 T 9 29 chervnya S 123 160 Kak procitirovano v Grunbaum 1963 de Castro N Cobos F J Dana J C Marquez A Triangle free planar graphs as segment intersection graphs 2002 T 6 vip 1 29 chervnya S 7 26 DOI 10 7155 jgaa 00043 z dzherela 3 grudnya 2008 Procitovano 25 bereznya 2022 Zdenek Dvorak Ken ichi Kawarabayashi Three coloring triangle free planar graphs in linear time Proc 20th ACM SIAM Symposium on Discrete Algorithms 2009 S 1176 1182 Bibcode 2013arXiv1302 5121D z dzherela 18 zhovtnya 2012 Arhivna kopiya vid 18 zhovtnya 2012 na Wayback Machine Glebov A N Kostochka A V Tashkinov V A Smaller planar triangle free graphs that are not 3 list colorable Discrete Mathematics 2005 T 290 vip 2 3 29 chervnya S 269 274 DOI 10 1016 j disc 2004 10 015 Richard Steinberg Younger D H Grotzsch s Theorem for the projective plane Ars Combinatoria 1989 T 28 29 chervnya S 15 31 Herbert Grotzsch Zur Theorie der diskreten Gebilde VII Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel Wiss Z Martin Luther U Halle Wittenberg Math Nat Reihe 1959 T 8 29 chervnya S 109 120 Branko Grunbaum Grotzsch s theorem on 3 colorings Michigan Math J 1963 T 10 vip 3 29 chervnya S 303 310 DOI 10 1307 mmj 1028998916 Christopher Carl Heckman Progress on Steinberg s Conjecture 2007 29 chervnya z dzherela 22 lipnya 2012 Procitovano 2012 07 27 Lukasz Kowalik Fast 3 coloring triangle free planar graphs Algorithmica 2010 T 58 vip 3 29 chervnya S 770 789 DOI 10 1007 s00453 009 9295 2 z dzherela 24 veresnya 2020 Procitovano 25 bereznya 2022 Reza Naserasr Homomorphisms and edge colourings of planar graphs 2007 T 97 vip 3 29 chervnya S 394 400 Series B DOI 10 1016 j jctb 2006 07 001 Jaroslav Nesetril Patrice Ossona de Mendez 2 5 Homomorphism Dualities Sparsity Heidelberg Springer 2012 T 28 S 15 16 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 Carsten Thomassen A short list color proof of Grotzsch s theorem Journal of Combinatorial Theory Series B 2003 T 88 vip 1 29 chervnya S 189 192 DOI 10 1016 S0095 8956 03 00029 7 Nabiha Asghar Grotzsch s Theorem Master s Thesis University of Waterloo 2012 29 chervnya DOI 10 13140 RG 2 1 1326 9367 z dzherela 26 lyutogo 2019 Procitovano 25 bereznya 2022

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