Курсова работа по Избрани глави от комбинаториката и теорията на графите на тема Теорема за четирите цвята



Дата30.11.2018
Размер157.51 Kb.
Курсова работа
по
Избрани глави от комбинаториката и

теорията на графите


на тема
Теорема за четирите цвята

на

гр. София 2011г



Съществуват много различни въпроси в нашия живот, чиито отговори се предоставят от Теорията на графите и Комбинаториката.

Колко различни цветове са достатъчни за да се оцветят държавите върху карта, така че никои две съседни държави да не са от един и същи цвят? Фигурата по-долу показва подходящ начин за подредба на оцветени държави.


След изучаване на голям брой различни графове е открит един очевиден факт, че всеки граф, независимо от неговите размери и сложност, може да бъде оцветен с точно четири определени цвята. Това първо било забелязано от Август Фердинанд Мобиус през 1840г. Малко след това през 1852г. млад мъж на име Франсис Гътрие написал за това в писмо до брат си Фредерик, който тогава бил студент University College London. Никой от братята не могъл да докаже това, затова Фредерик се обърнал към един от професорите си, Августин ДеМорган. ДеМорган също не бил способен да докаже това предположение и след приемането на сложността на проблема, той писал на Сър Уилям Роуан Хамилтън ( 1805 – 1865 ) за да го помоли за помощ. Хамилтън допринесъл много за теорията на графите. А това е предмет, който бил развит широко с усилия, за да докаже четирицветното предположение. Въпреки това, Хамилтън веднага отговорил на писмото и казал, че не вярва да може толкова бързо да разреши задачата.


Оцветяването на географска карта е естествено топологичен проблем, в смисъл на това, че зависи само от свързаността на държавите, а не от техните специфични форми, размери или положение. Можем също да представим всяка държава чрез отделна точка ( връх ), а съседството между две съседни страни може да бъде предтавено чрез линия ( ребро ), свързващо тези две точки. Разбираемо е, че свързващите линии не могат да се пресичат. Чертеж от този вид се нарича граф. Една проста карта ( от само пет държави например) и съответният граф са показани по-долу.



Един граф е n-цветен, ако е възможно да има един от тези n цвята на всеки връх, по такъв начин, че никои два свързани върха да не са от един и същи цвят. Очевидно е, че графът горе не е 3-цветен, а е 4-цветен. Четирицветната теорема твърди, че всеки граф – и следователно всяка карта – без значение колко голям или сложен, е 4-цветен. Изглеждащо просто, това било доказано само през 1976г., а след това само чрез компютри.
Забележете, че този граф е “пълен” в такъв смисъл, че не могат да бъдат добавени повече връзки. Ребрата на пълния граф делят графовата равнина на полета с по 3 страни, тоест, всяко поле е заградено от 3 ребра на графа. Всеки граф може да бъде конструиран, като първо се конструира пълен граф и после се премахнат някои връзки ( ребра ). Очевидно, премахването на връзките не може да изиска допълнителни цветиве за n-цветен граф, така че за да докажем тази теорема ще бъде достатъчно да имаме предвид само пълни графове.
Въпреки че, ДеМорган не могъл да докаже четирицветното предположение, той забелязал, че не повече от четири области от равнината могат да бъдат всички във взаимен контакт един с друг. Графът от множество от три взаимно съседни области, е топологичен триъгълник и ако добавим четвърта област, тя ще е представена от четвъртия връх в графа, който трябва да е разположен, както отвътре, така и отвън от триъгълника, оформен от графа с първоначалните три върха. При всеки случай трябва да свържем този четвърти връх с всеки от първоначалните три, така че всяка от четирите области са взаимно съседни:

Това е уникалният граф с четири взаимно съседни области ( V = 4, E = 6 ). Това ясно разделя графа на четири отделни области, една област вън от големия триъгълник и трите вътрешни области. Петият добавен връх към този граф ще има

ребра, които ще достигат само три от съществуващите четири върха, защото всяка от четирите области е напълно заградена от три върха, които блокират достъпа до

един от върховете. Следователно не съществува граф с пет взаимно свързани върха, така че и не съществува множество от пет взаимно съседни области от една равнина.
Разбира се, несъществуването на граф с пет взаимно свързани върха не означава автоматично, че не съществува граф, които изисква пет различни цвята. Например, съществуват гарфи, в които най-голямото подмножество от взаимно свързани върха е две и все пак за всеки се изкискват три цвята. Подобно, има графи, които не съдържат подмножество от четири взаимно свързани върха, но въпреки това изискват четири цвята.


В лявата фигура имаме алтернативно сменящи се червено, зелено, червено, зелено. И ако това бяха единствените два възможни цвята, щеше да е ясно, че веригата ще продъулжи така без значение колко дълга или колко къса. По този начин ние можем да заменим всяка верига от типа rgrg…rg (red-green) с простия чифт ‘rg’, в който случай лявата фигура се състои от три взаимно свързани върха. По подобен начин, ако заменим веригата rgrg около централния жълт връх във фигурата в дясно с чифта rg, получаваме множество от четири взаимно свързани върха.


С оглед на това, възможно е да повярваме, че наблюденията на ДеМорган по някакъв начин, вероятно индиректно, свидетелстват за истинността на Теоремата за Четирите Цвята. Преди извеждането на едно възможно доказателство на теоремата, трябва да се спомене, че нейната достоверност все още е обект на внимание, породи факта , че е докъзателдтвото е осъществено единствено чрез компютър.

Наистина, ако конструираме граф чрез добавяне на върхове един по един и направим максимално много връзки при всяко добавяне, винаги ще откриваме, че графовата равнина е разделена на “триъгълни” области, всяка от които има достъп само до три върха. Следователно, четири цвята са достатъчни за всеки граф, които може да бъде конструиран по този начин. Например, вземете предвид двата графа показани на рисунка на следващата страница.



Тези два графа, всеки има V = 6 (a, b, c, d, e, f) върха и E = 12 края, и фактически двата графа са топологически идентични. Равнината представена от връх “a” и “b” всяка има пет взаимносвързани съседа, докато връх “е” и “f”, всеки има четири, а за върховете “c” и “d” по три. Има пълни графове и както посочихме по- горе, пълният граф разделя цялата равнина на графа на “ триъгълници “, например, частта образувана (оградена), ограничена от три края свързващи три върха. Въпреки това, опирайки се на това как добавяме точки, възможно е когато един връх е добавен към граф да има три съседни върха, така че ние не можем автоматично да кажем, че четири цвята ще са достатъчни.


Друг топологично еднакъв начин да нарисуваме горната графика е представен долу:


Това показва, че ние първо можем да отнесем три различни цвята към върховете e, b, f и след това да поставим връх “a” в този триъгълник, да го свържим със заобикалящите го върхове и да поставим четвърти цвят. След това можем да поставим връх d вътре в триъгълника „abe” и да му дадем същия цвят като на връх f. След това поставяме връх c в триъгълник „abf” и му даваме цвята на e. Така получаваме четирицветен граф. Освен това , всеки граф (или част от граф) ограден от триъгълник като abf, и имащ йерархическия модел на серия от триъгълници, влизащи един в друг , е четирицветен. Това е случеят, когато графът се състой от няколко върха само с три края , и когато тези върхове и краища са преместени. Графът, който остава също има няколко върха с три края , който също може да бъде преместен, и така , докато най- накрая остане един триъгълник.

За съжаление не всеки граф има такава йерархична форма. Например, нека разгледаме пълният граф показан долу.




Този граф има V= 16 върха и E= 24 края. Той не е йерархичен, защото след като преместим двата върха, всеки от които има три края, графът които се получава има четири или повече края прикрепени към всеки връх. ( Можем също да заключим, че този граф няма йерархична форма, защото никои три взаимносвързани върха са точно свързани към четвърти връх). Въпреки това, този граф е четирицветен, както може да се види от фигурата.

Горният граф се състои от еднакви шестоъгълни мрежи. Една безкрайна шестоъгълна мрежа е очевидно четирицветна служейки си с модела със сменящите/ редуващите се пласта, илюстриран долу:



Трява да отбележим, че ние не се нуждаем от разглеждането на гарф, съдържащ конфигурации от четири взаимносвързани върха, защото, както бе обсъдено по- рано , краят на такава конфирурация неизбежно разделя равнината на графа на четири отделени части , всяка от които има достъп само до три или четири върха. Въпреки това, ако можем да оцветим в четири цвята, то тогава можем и да оцветим в четири цвята четириъгълната рамка. Ако успеем да намалим всички причинни връзки до тяхния минимум, би могло да намалим всеки n- цветен граф до граф само с n взаимносвързани върха, и също така и n никога не трябва да надминава 4. Въпреки това, намалянето на графовете с повече от два цвята не е често срещана задача.


Ако означим броят на върховете, крайщата, лица на един граф съответно с V, E, и F, формулата на Ойлер за равнина ще има следния вид VE + F = 2. Освен това, всяко лице на пълния граф е оградено от три края, и всеки край е на границата на две лица, така че имаме F = 2E/3, и формулата на Ойлер за пълен граф е :

E = 3V – 6. Сега, всеки край е свързан с два върха, така че пълният брой на свързванията е 2E = 6V – 12, и така че средният брой на свързванията за всеки връх е 6 – 12/V. За всеки непълен граф, пълният брой на свързванията е по- малък. Броят на свързванията за всеки върх в който и да е граф ( с краен брой върхове ) е по- малък от 6, което показва, че най –малко един връх има само пет или по- малко свързвания.


Ако имаме пет възможни цвята , връх само с пет съседни очевидно е, че няма да има никакви ограничения за цветовете на другите върхове, защото без да се интересуваме от цветовете на неговите пет ( или по- малко ) съседа, ние можем да определим/ сложим цвят без да изключваме възможните шест. Следователно, ако изтрием този връх заедно с неговите връзки в графа, образувайки граф с един по- малко върхове, ясно е че ако графът, който се получи е шестцветен, тогава това е бил истинският граф. Освен това, формулата на Ойлер ни убеждава, че този намален граф също съдържа май –малко един връх с пет или по- малко съседа, така че ние можем да приложим този процес няколко пъти, намаляйки графа до един с шест върха, което очевидно е шестцветен граф. Оттук следва, че истинският/ оригиналният граф е шестцветен.
Така че, ние видяхме, че формулата на Ойлер непременно означава, че никой граф не може да изисква шест цвята. Освен това, с малко повече работа, можем да покажем, че никой граф не може да изисква повече от пет цвята. Очевидно всеки граф с пет или по- малко върха е петцветен, така че ако съществува краен граф, който изисква повече от пет цвята, той трябва да има повече от пет върха. Нека с положителното число V6 означим най- малкия брой на върховете, на които съществува граф изискващ шест, девет или повече цвята. Разбира се, всеки граф с по- малко от V6 върха е петцветен.
Сега, приемайки съществуването на граф, изискващ повече от пет цвята, можем да разгледаме един, който има точно V6 върха. От формулата на Ойлер, този граф трябва да има най –малко един връх с шет или по- малко връзки. Въпреки това, той не може да съдържа връх само с четири ( или по- малко ) връзки, защото ако е така, ние ще трябва да изтрием един връх и да оставим графа само с V6 – 1 върха, което по дефиниция е петцветен граф. Вмъквайки изтрития връх няма да има никакъв ефект на петцветния граф, защото върха има само четири ( или по- малко ) съседи, така че истинският граф трябва да е петцветен, което противоречи на нашето предположение. За това, граф с V6 върха, който изисква повече от пет цвята не може да съдържа връх само с четири или по- малко съседа.
Докато формулата на Ойлер показва, че графът съдържа най- малко един връх с пет или по-малко връзки, единствената оставаща възможност е графът да съдържа връх точно с пет връзки. Въпреки това, това също води до противоречие. За да покажем това, е важно да въведем понятието k – cluster , който е определен от k различни цвята и един определен връх , който има един от онези цветове. Истинският връх се съдържа в cluster, като допълним, че всеки връх с един от определените k- цветове, който е в съседство с един връх в cluster, е също в cluster. По дефиниция единствените върхове, извън cluster които са свързани директно с върхове вътре, в cluster имат цветове, които не са от к – цветовете. По тази причина ние можем да сложим която и да е пермутация на к- цветовете към върховете, в cluster без да анулираме оцветяването.
Представете си граф, съдържащ връх с точно пет съседа, с пет различни цвята, както е илюстрирано на картинката:

Неоцветеният граф в центъра има съседи от пет различни цвята, и както изглежда шести цвят се изисква. Въпреки това, можем да отбележим, че може да се размести синият със зеленият цвят от синия/ зелен 2- cluster свързан към горният ляв връх на централния петоъгълник, така че горният ляв връх е зелен вместо син. След като сме направили тази замяна, неоцветеният връх в центъра има съседи само с четири различни цвята. Ако изтрием централният връх, графа има V6 – 1 върхове, така че е петцветен, но ако отново сложим изтрития връх, той не изисква шести цвят ( щом веднъж вече сме разменили синия и зеления цвят в малките 2- cluster както е описано ), и истинският връх е петцветен.
Единственото възражение към разменянето на цветовете в cluster чрез намаляне броя на различните цветове около периметъра на петоъгълника е че ние не можем по необходимост да сменим цвета на върха с цвят от противоположните върхове на петоъгълника, защото два противоположни върха от петоъгълника може да са в един и същ 2- cluster. Това е случаят, например, с жълтия и червен връх на петоъгълника от горната фигура. Ако разменим червения и жълтия цвят в 2- cluster, все още ще има пет различни цветове около периметъра на петоъгълника. Ако такъв cluster съществува - свързващ двата противоположни върха на петоъгълника, ние със сигурност можем да кажем, че най –малко още една двойка върхове се самоизключват един друг, например, те не може да са в един и същ 2- cluster.

Например, син/ зелен cluster, очертан в червено горе на фигурата, не може да бъде част от син/ зелен cluster прикрепен към горният десен връх на петоъгълника. Като цяло, за всеки връх свързан точно с пет други върхове , ние винаги можем да сменим цвета на най- малко един от петте съседа, така че да има четири различни цветове. Както следва, използвайки намалянето на върховете, описано в горния параграф, нито един граф не може да изисква повече от пет цвята.

Ето още един нагледен пример как се променят нещата при изключване на един цвят:

Обаче все още остава отворен въпроса дали найстина се изискват пет цвята, или може и да са четири. Ако има гарфове изискващи пет различни цветове, трябва да има положително число V5 , което е най- малкият брой върховете, въз основа на които може да се изгради един граф. Нека приемем, че граф с V5 върха, изисква пет цвята. От намалянето, описано по- горе, следва че очевидно всеки връх не може да има три или по- малко връзки. Още повече, имайки предвид 2- cluster, можем да докажем, че такъв гарф не може да съдържа връх само с четири връзки. За да видим защо, нека вземем частта от графа илюстрирана долу:



Неоцветеният връх в центъра има точно четири съседа, които са оцветени в червено, жълто, зелено и синьо. Изглежа, че би трябвало да се изисква пети цвет за централния връх, но фактически, ако разменим жълтия и синия цвят в 2- cluster над централния връх, можем да трансформираме това оцветяване, така че централният връх да има само три различни съседа ( червен, зелен и син ). От графа, където бе взета тази конфигурация, преплогахме, че има точно V5 върха, следва че ако изтрием цетралния граф, гарафът, който се получава има само V5 – 1 върха, така че е четирицветен, но ние можем отново да добавим централния връх без да изискваме пети цвят. Това показва, че винаги е възможно да изменим граф, съдържащ връх само с четири връзки така че той да е свързан само с три различни цветове. Само една от двете двойки противоположни върхове може да се върже с общ 2- cluster., защото ако една такава двойка е свързана по този начин, другата не може.
За да обобщим доказателството до този момент, ние показахме, че никой граф не може да изисква повече от пет цвята, и също така ако съществува граф, изискващ пет цвята, трябва да има минимален пет- цветен граф, който не може да има върхове с по –малко от пет връзки. Също така, ако добавим връзки, можем да “допълним “ един граф с V върха, така че всичките му лица да са триъгълници и общият брой на връзките е 6V – 12. Този граф все още може да е минимален пет- цветен граф, защото не сме увеличили броя на върховете, а добавянето на връзки не може да намали броя на изискваните цветове, тъй като никой граф не изисква повече от пет цвята. За това, ако отбележим с a5, a6, a7,... броят на върховете, съответно точно с 5, 6, 7, ... връзки, трябва да получим минимален пет- цветен граф като :

където V = a5 + a6 + a7 + a8 + a9 + ... Ако заместим в горната формула V с неговото равно, получаваме :

Това поставя сериозни ограничения за всеки предполагаем пълен минимален пет- цветен граф. Например, ако вземем графове с не повече от шест връзки за всеки отделен връх, тази формула предполага a5 = 12. С други думи, пълен минимален пет- цветен граф с не повече от шест връзки на връх трябва да има точно 12 върха, всеки с 5 връзки. Това предполага, че тези 12 върха са подредени сферично с модела на двадесетостенника, а останалите върха с шест връзки на връх са в правилен шестоъгълен модел, запълвайки лицата на двадесетостенника. ( Интересно е да се спомене, че този модел е базата на “ геодезните кубове “).

Фундаменталният граф от този тип, с а5 = 12 :


Можем ясно да определим оцветяването в четири цвята на всеки такъв модел, така че всеки такъв граф да изисква не повече от четири цвята. За това, ако един пълен минимален пет- цветен граф съществува, той трябва да има най –малко седем или повече връзки.

Чак през 1976 година, когато с помоща на модерните компютри, четирицветното предположение бе най- накрая доказано за вярно. Доказателството, осъщетвено от Appel и Haken, базирано на идеите на няколко техни предшественици (Heawood, Birkhoff, и други ). То се състои в намирането на серия от подграфа, най- малко един от тях да се съдържа в кой да е нормален граф. И такива че ако един граф, съдържащ един от подграфовете, не е четирицветен, тогава графа е с един по- малко връх. Това веднага води до противоречие, защото показва, че ако предположим съществуването на граф, който не е четирицветен, ние винаги можем да начертаем друг граф, с по- малко върхове, който също да не е четирицветен, евентуално достигащ до граф само с четири върха, но този граф очевидно е четирицветен. Тъй като стигаме до противоречие, можем да заключим, че оригиналната хипотеза е грешна, така че, не съществува граф, който да е четирцветен. Неизбежната серия от подрафове на Appel и Haken се състой от 1500 подграфа, и много от тях изискват значителен анализ от професионалисти.

Развитието на тази неизбежна серия от пографове, и доказателствата на ‘reducubulity’ за всеки негов член, бе направено на компютър, така че доказателството е забележително и е извън човешките възможности (това е и причине на всички да вярват в истинността му).


Интерено е да се разгледаме проблема с определянето на четири цвята на кой да е граф от алгебрична гледна точка. Приемаме, че всеки връх може да се определи с една от четирите възможни стойности, и условията, наложени от връзките ще бъдат представени чрез алгебрични уравнения, едно уравнение за всяка връзка. Част от трудността на този подход е, че условието за съседство не е равенство, а неравенство, така че два върха имат различни стойности ( от четирите възможни ). Има и голяма доза двусмисленост в решението, защото пермутацията на цветовете остава решението неразрешено.Още повече, има друго двусмислие в това, че като цяло може да има повече от четири цвята оцветяване на графа.
Нека четирите възможни стойности са a, b, c, d, можем алгебрически да поставим изискването всеки връх да према една от тези стойности, така че стойността й приложена към всеки връх да удовлетворява f(u) = 0, където полиномът f се определя като:


След това можем алгебрично да дадем на изискваното неравенство стойностите u, v, отнасящи се към два свързани върха с уговорката, че g(uv) = 0, където полиномът „g” има следния вид:


Уравнението g(uv) = 0 е удовлетворено, ако u и v имат различни стойности от

{ a, b, c, d }. Например, ако {-2, -1, 1, 2}, тогава


За да го илюстрираме, представете си отново осмостенния граф ( който е три- цветен ):




Алгебричните условия за всяка стойност на всеки “ цвят “ отнесен към шестте променливи A, B, C, D, E, F са:


и алгебричните условия от 12- те връзки са:


Това прави 18 уравнения в 6- те променливи. Можем да приемем, че цветовете на три от променливите са A = 1, B = -1, C = 2, като тези три променливи трябва да имат различни стойности. Тогава от 12-те уравнения ни остават трите неизвестни D, E и F .

и


Трите уравнениеята f(D) = 0, g(D) = 0, и g(-D) = 0 заедно имат само две решения, D = 2 и D = -2. Следователно тези три уравнения могат да се заместят с

D2  4 = 0. По същият начин трите уравнения съдържащи само E могат да се запишат като: E2 + 3E + 2 = 0, и другите три съдържащи F : F2 + F  2 = 0. Така че сега имаме три уравнения за трите неизвестни.



Различен подход бихме изпозвали, за да отнесем един четири- мерен вектор към всеки връх, и тогава връзката между двата дадени върха ще се представи чрез изискването на двата вектора да са взаимно ортогонални. Трита вектора към върховете на кой да е триъгълник тогава ще образуват правоъгълна тройка с ориентация към четиримерното пространство. По същият начин четирите вектора към върховете на тетраедърен граф ще образуват пълна група от четири взаймносвързани ортогоналти вектора ( четворка ), но все още с произволна ориентация.
Например, условията на шесте вектора A, B, C, D, E, F към върховете на осмостенен граф са написани долу:

В този контекст теоремата за четирите цвята ни показва, че пространството с четири измерения е достатъчно, за да ни позволи да отнесем един от четирите базисни вектора към всеки връх на граф така че векторите на всяка двойка съседни върхове да са ортогонални/ правоъгълни. Приемаме, че всеки вектор е с единица мярка за дължина, така че да има три независими елемента. Тогава имаме като цяло 18 независими елемента, ограничени от 12 уравнения. Разбира се, системата е под особено внимание, защото може да приложим произволна пермутация за всеки вектор.
Тъй като крайщата на пълния граф делят равнината му на три- странни части, чиито върхове са три взаймносвързани точки, ние можем да сложим четвъртия цвят на всеки от тези части. Разултатът е полезен за визуализация на семантиката на цветовете. Например, четирицветният двадесетостенен граф, за който говорихме по- горе се илюстрира така:





База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница