Azərbaycanca AzərbaycancaDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisItaliana ItalianaҚазақ ҚазақLietuvos LietuvosРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人
Підтримка
www.wikidata.uk-ua.nina.az

Розфарбуванням простого графу G називають таке приписування кольорів або натуральних чисел його вершинам що ніякі дві су

Розфарбовування графів

Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору. Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом.

image
Розфарбовування графу Петерсена трьома кольорами.

Теорема

Якщо найбільший зі степенів вершини графу дорівнює p, то цей граф можна розфарбувати в p+1 колір.

Доведення

Застосуємо індукцію за кількістю вершин графу. Нехай граф G має n вершин; вилучимо з нього довільну вершину u разом з усіма інцидентними їй ребрами. Отримаємо граф з n-1 вершиною, степінь кожної вершини не більший ніж p. За припущенням індукції цей граф можна розфарбувати в p+1 колір. Отже, у p+1 колір можна розфарбувати й граф G, якщо розфарбувати вершину u кольором, що відрізняється від тих, якими розфарбовано суміжні з нею вершини (а їх разом не більше ніж p).

Теорема Р. Хейвуда

Будь-який планарний граф можна розфарбувати в п'ять кольорів, тобто χ(G)≤5 для будь-якого планарного графу G.

Доведення

Доведення цієї теореми ґрунтується на тому, що в будь-якому простому планарному графі є вершина, степінь якої не більший ніж п'ять. Застосуємо математичну індукцію за кількістю вершин графу. Теорема справджується для графів із не більше ніж n вершинами, де n≥5. Розглянемо довільний плоский граф G з (n+1) вершиною. Він містить вершину u_0, степінь якої не більший ніж п'ять. Нехай W =Г(u_0)- множина вершин, суміжних із вершиною u_0 в графі G. Розглянемо наступний випадок. | W |≤4. Позначимо як G — u_0 граф, отриманий із графу G вилученням вершини u_0 та всіх інцидентних їй ребер. За індуктивним припущенням граф G — u_0 можна розфарбувати в п'ять кольорів. Зафіксуємо одне з таких розфарбувань і зафарбуємо вершину u_0 в той із п'яти кольорів, який не використано для фарбування вершин із множини W.

Теорема

Нехай G — простий граф, а u та w — його несуміжні вершини. Якщо граф G_1 отримано з G за допомогою з'єднання вершин u та wребром, а граф G_2 — ототожненням вершини u та w (і кратних ребер, якщо їх буде одержано), то P_G(k)=P_G1(k)+P_G2(k).

Доведення

За будь-якого допустимого розфарбовування вершин графу G існує альтернатива: u та w мають різні кольори, або той самий. Кількість розфарбовувань, за яких u та w мають різні кольори, не зміниться, якщо долучити ребро {u, w}. Отже, ця кількість дорівнює P_G1(k). Аналогічно, кількість розфарбовувань, за яких u та w мають один колір, не зміниться, якщо ототожнити u та w. Залишилось застосувати комбінаторне правило суми. Теорему доведено.

Наслідок

Хроматична функція простого графу — поліном. P_G(k) — хроматичний поліном .Якщо граф G має n вершин, то степінь полінома P_G(k) дорівнює n. Коефіцієнт kn дорівнює 1, а при kn-1 дорівнює m, де m — кількість ребер графу G; знаки коефіцієнтів чергуються; вільний член хроматичного полінома дорівнює 0. Хроматичний поліном будують на основі теореми 3.19 у вигляді суми хроматичних поліномів повних графів.

Див. також

Література

  • Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина «Дискретна математика», 2007.
image Це незавершена стаття з математики.
Ви можете проєкту, виправивши або дописавши її.
В іншому мовному розділі є повніша стаття Graph coloring(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою з англійської.
  • Дивитись автоперекладену версію статті з мови «англійська».
  • Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
  • Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
  • Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
  • Докладні рекомендації: див. .

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

Дата публікації:
Rozfarbuvannyam prostogo grafu G nazivayut take pripisuvannya koloriv abo naturalnih chisel jogo vershinam sho niyaki dvi sumizhni vershini ne nabuvayut odnakovogo koloru Najmenshu mozhlivu kilkist koloriv u rozfarbuvanni nazivayut hromatichnim chislom Rozfarbovuvannya grafu Petersena troma kolorami TeoremaYaksho najbilshij zi stepeniv vershini grafu dorivnyuye p to cej graf mozhna rozfarbuvati v p 1 kolir Dovedennya Zastosuyemo indukciyu za kilkistyu vershin grafu Nehaj graf G maye n vershin viluchimo z nogo dovilnu vershinu u razom z usima incidentnimi yij rebrami Otrimayemo graf z n 1 vershinoyu stepin kozhnoyi vershini ne bilshij nizh p Za pripushennyam indukciyi cej graf mozhna rozfarbuvati v p 1 kolir Otzhe u p 1 kolir mozhna rozfarbuvati j graf G yaksho rozfarbuvati vershinu u kolorom sho vidriznyayetsya vid tih yakimi rozfarbovano sumizhni z neyu vershini a yih razom ne bilshe nizh p Teorema R HejvudaBud yakij planarnij graf mozhna rozfarbuvati v p yat koloriv tobto x G 5 dlya bud yakogo planarnogo grafu G Dovedennya Dovedennya ciyeyi teoremi gruntuyetsya na tomu sho v bud yakomu prostomu planarnomu grafi ye vershina stepin yakoyi ne bilshij nizh p yat Zastosuyemo matematichnu indukciyu za kilkistyu vershin grafu Teorema spravdzhuyetsya dlya grafiv iz ne bilshe nizh n vershinami de n 5 Rozglyanemo dovilnij ploskij graf G z n 1 vershinoyu Vin mistit vershinu u 0 stepin yakoyi ne bilshij nizh p yat Nehaj W G u 0 mnozhina vershin sumizhnih iz vershinoyu u 0 v grafi G Rozglyanemo nastupnij vipadok W 4 Poznachimo yak G u 0 graf otrimanij iz grafu G viluchennyam vershini u 0 ta vsih incidentnih yij reber Za induktivnim pripushennyam graf G u 0 mozhna rozfarbuvati v p yat koloriv Zafiksuyemo odne z takih rozfarbuvan i zafarbuyemo vershinu u 0 v toj iz p yati koloriv yakij ne vikoristano dlya farbuvannya vershin iz mnozhini W TeoremaNehaj G prostij graf a u ta w jogo nesumizhni vershini Yaksho graf G 1 otrimano z G za dopomogoyu z yednannya vershin u ta wrebrom a graf G 2 ototozhnennyam vershini u ta w i kratnih reber yaksho yih bude oderzhano to P G k P G1 k P G2 k Dovedennya Za bud yakogo dopustimogo rozfarbovuvannya vershin grafu G isnuye alternativa u ta w mayut rizni kolori abo toj samij Kilkist rozfarbovuvan za yakih u ta w mayut rizni kolori ne zminitsya yaksho doluchiti rebro u w Otzhe cya kilkist dorivnyuye P G1 k Analogichno kilkist rozfarbovuvan za yakih u ta w mayut odin kolir ne zminitsya yaksho ototozhniti u ta w Zalishilos zastosuvati kombinatorne pravilo sumi Teoremu dovedeno Naslidok Hromatichna funkciya prostogo grafu polinom P G k hromatichnij polinom Yaksho graf G maye n vershin to stepin polinoma P G k dorivnyuye n Koeficiyent kn dorivnyuye 1 a pri kn 1 dorivnyuye m de m kilkist reber grafu G znaki koeficiyentiv cherguyutsya vilnij chlen hromatichnogo polinoma dorivnyuye 0 Hromatichnij polinom buduyut na osnovi teoremi 3 19 u viglyadi sumi hromatichnih polinomiv povnih grafiv Div takozhZhadibne rozfarbovuvannya Kolove rozfarbovuvannya Michelskian Nide ne nulovij potik Odnoznachno rozfarbovuvanij graf Problema chotiroh farb Teorema de Brejna Erdesha teoriya grafiv Hromatichne chislo Cilkom uporyadkovuvanij grafLiteraturaYu V Nikolskij V V Pasichnik Yu M Sherbina Diskretna matematika 2007 Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi V inshomu movnomu rozdili ye povnisha stattya Graph coloring angl Vi mozhete dopomogti rozshirivshi potochnu stattyu za dopomogoyu perekladu z anglijskoyi Divitis avtoperekladenu versiyu statti z movi anglijska Perekladach povinen rozumiti sho vidpovidalnist za kincevij vmist statti u Vikipediyi nese same avtor redaguvan Onlajn pereklad nadayetsya lishe yak korisnij instrument pereglyadu vmistu zrozumiloyu movoyu Ne vikoristovujte nevichitanij i nevidkorigovanij mashinnij pereklad u stattyah ukrayinskoyi Vikipediyi Mashinnij pereklad Google ye korisnoyu vidpravnoyu tochkoyu dlya perekladu ale perekladacham neobhidno vipravlyati pomilki ta pidtverdzhuvati tochnist perekladu a ne prosto skopiyuvati mashinnij pereklad do ukrayinskoyi Vikipediyi Ne perekladajte tekst yakij vidayetsya nedostovirnim abo neyakisnim Yaksho mozhlivo perevirte tekst za posilannyami podanimi v inshomovnij statti Dokladni rekomendaciyi div Vikipediya Pereklad
Топ