Курсът е воден от проф д. м н. Николай Хаджииванов
Изтегляне 1.04 Mb.
|
- Навигация на страницата:
- 3. Graph Ramsey games
4. Хроматичен индекс На задачата за намиране на минималният брой на цветовете,т.е. хроматичното число Практическото приложение на задачата за минимално оцветяване на ребрата може да се намери при монтажът на електрически схеми. За да се избегнат грешки, понякога, от един възел на схемата излизат проводници с различни цветове. През 1936г. Кьониг доказва, че ако един граф е върхово 2-оцветим, тогава той е реброво d-оцветим, където d е степента на графа. През 1964г. Визинг доказва, че всеки граф е реброво (d+1)-оцветим, където d е степента на графа. За хроматичния индекс се знае твърде малко. Наистина
Дефиниция: Нека G граф,  - съвкупност от цветове. Реброво -оцветяване на G наричаме такова оцветяване на ребрата на G, че всяко ребро е оцветено в някой цвят от S и при това никои две еднакво оцветени ребра не са съседни. Тогава можем да кажем и че ребрата на G са оцветени правилно в цвята.
Дефиниция: Минималното , за което графът G има реброво -оцветване, се нарича хроматичен индекс на G и се означава с .
При n-ъгълника Тук виждаме, че при опита да оцветим 7-ъгълника в 2 цвята се получават две ребра с еднакъв цвят излизащи от един връх, следователно 2 цвята не са достатъчни за оцветяването на 7-ъгълника. Виждаме на картинката, че при 3-озветяване на 7-ъгълника се изпълняват условията за хроматичен индекс, следователно 3 е най-малкият брой цветове в които можем да оцветим Виждаме, че в графиката на  Във всеки връх x присъстват точно  цвята. Следователно .
Ребрата на тетраедъра могат да се оцветят правилно в три цвята, така че може да има равенство между хроматичния индекс и степента на графа. От друга страна, ребрата на триъгълника не могат да се оцветят правилно в два цвята, следователно хроматичният индекс може да е строго по голям от степента на графа. Зад.1. Вярно е неравенството .
Док. За граф с едно ребро неравенството е очевидно: , ;
Да допуснем, че неравенството е в сила за граф с n-1 на брой ребра. Нека G е гаф с n ребра. Да вземем едно от тях – нека е означено с - и да го отстраним от графа. Получаваме граф с n-1 ребра. Според индукционното предположение има правилно оцветяване в цвята. Тъй-като , има правилно оцветяване в цвята. Във върха на присъстват най-много цвята. Същото се отнася и за върха .Следователно общо в и участват не повече от цвята. Тогава никой от дадените цвята отсъства и в , и в .С него можем да оцветим реброто . По такъв начин получаваме правилно оцветяване на ребрата на G в цвята .
Дефиниция: Нека G е граф с правилно оцветени ребра и s и t са два различни цвята. -верига ще наричаме такава верига на G, всяко ребро на която е оцветено в s или t. Една -верига може да съдържа само едно ребро. Всяка -верига е проста; тя може да бъде и цикъл.
Дефиниция: Една -верига наричаме максимална, ако не се съдържа в различна от нея -верига. Всяка -верига се съдържа в максималната.
Леми на Шенон: Лема 1. Павилността на оцветяването на G не се наушава, ако разменим цветовете в коя да е максимална двуцветна верига. Доказателството на тази лема е очевидно.Например, ако разменим цветовете на оцветяване в Лема 2. Нека ,и са три различни върха на графа G с правилно оцветени ребра и във всеки един от тези върхове отсъства поне един от различните цветове s и t. Тогава поне един от върховете ,и не може да се съедини нито с един от останалите с помоща на -верига.
Док. От всеки от върховете ,и може да излиза ребро само в един цвят s или t. Нека x и y са свързани с s ребро. Понеже от тях вече могат да излизат само s ребра, то те се свързват с останалите върхове на графа с s ребра. Следователно, ако от z илизат t ребра, то x и y не могат да се свържат с него. Следователно не съществува -верига за върховете ,и . Ако пък от z излизат s ребра, то във свързването на ,и не участва t ребро.Следователно отново нямаме -верига. Следователно z не може да се свърже с x и y чрез -верига.
Дефиниция: При зададено реброво оцветяване на един граф G съвкупността на всички ребра с един и същи цвят се нарича ребров едноцветен клас на оцветяването. Всеки ребров клас е независимо множество от ебра и поади това броят на елементите му не надминава числото на реброва независимост . Обединението на едноцветните класове е множеството на всички ребра на G, следователно и . Ако означим с n броя на върховете на G. Ако n е четно, тогава очевидно , следователно при четно n. Ако n е нечетно, и следователно при нечетно n.
Дефиниция: Под регулярен граф разбираме граф степените на върховете на който са равни. Ако G е регулярен граф и Зад.1. Нека G е регулярен граф с нечетен брой върхове. Тогава .
Док. Зад.1. следва от Тъй като малко по-късно ще докажем, че неравенството, обратно на Сега ще пресметнем хоматичният индекс на пълния граф. Теорема 1. За пълния граф имаме
Док: Неравенството е очевидно, тъй като . Неравенството при нечетно n е тривиално следствие от зад.1.
Ще докажем обратните неравенства. Нека n е нечетно. Ще вземем върховете на Получаваме правилно оцветяване, поеже еднакво оцветените отсечки са успоредни. Доказахме, че при нечетно n е в сила неравенството Остана да се разгледа случаят на четно n, Тогава не може да се разсъждава по същия начин. Сега един от върховете на Да забележим, че отсечката съединяваща центъра с някой връх на (n-1)-ъгълника, е перпендикуляна на точно една страна на (n-1)-ъгълника. Ще оцветим всяка такава отсечка в цвета на станата, на която е перпендикулярна. Отнов получаваме правилно оцветяване. Следователно С това теорема 1 е доказана.
Теорема 2 (Кьониг). Ако графът G е върхово 2-оцветим, тогава  .
Док.(по Визинг). Да вземем подграф на G, който съдържа всички въхове на G и е реброво d-оцветим (например дискретният подгаф). Да допуснем, че има ребро на G, което не влиза в (ако такова няма, G е реброво d-оцветим). Ще оцветим правилно в d цвята ребрата на . Ще покажем, че съществува правилно оцветяване в d цвята и на ребрата на графа , който се получава от чрез писъединяване на реброто e.
Ако някой от цветовете, с които е оцветен Поради това можем да предполагаме че всеки цвят присъства в поне един от върховете Върховете Да разменим цветовете на максималната И така, Теорема 2 е доказана.
Теорема 3(Визинг). За всеки граф G е в сила неравенството .
Док.(по Визинг). Нека . Да вземем подграф на G, който съдържа всички върхове на G и е реброво k оцветим. Да допуснем, че е ребро на G, което не влиза в .
Ще оцветим равилно с помоща на k цвята ребрата на Ако това успеем да направим, теоремата ще бъде доказана. За всеки връх x на G с Ако Нека сега Нека Нека Нека на реброто 1 случай. Ще преоцветим реброто 2 случай. Възможни са следните три подслучая: а) Да вземем цвят t от a-1) Ако а-2) Ако и са съединими с -верига, тогава съгласно лема 2, приложена за върховете , и и цветовете и , върхът не може да се съедини с -верига нито с , нито с . В този случай ще разменим цветовете в максималната -верига през ( ако в отсъства не само , но и , тогава няма -верига през и няма да променяме никакви цветове). Получаваме ребово k оцветяване на . При новото оцветяване цветът отсъства със сърха , тъй като преди промяната на цветовете в е отсъствал цветът . Тъй като не минава през , направената промяна на цветовете не е засегнала цветовете на ребрата през и специално на ребрата ,,...,. Освен това и при новото оцветяване имаме , тъй като във върха няма как да се появи цветът , щом преди това не е бил. ПРи новото оцветяване имаме пак , тъй като цветът на никое ребро през не е променен. Ако направим ново съпоставяне на цвят на реброто , а именно вместо му съпоставим цвета ( който сега отсъства и в ), то, тъй като и при новото оцветяване, ще се окажем в условията на случай 1, когато знаем, че е възможно реброво k оцветяване на .
б) б-1) Ако върхът е съединим поседством - верига с върха , тогава съгласно лема 2, приложена за въховете , , и цветовете и , върхът не е съединим посредством - верига нито с върха , нито с върха .
Ще разсъждаваме както в а-2). Разменяме цветовете в максималната - верига и през върха (ако в отсъства не само , но и , тогава нищо няма да променяме). При новото оцветяване цветът отсъства във върха . Тъй като не минава през , цветовете на ребрата не са се поменили. И пи новото оцветяване имаме . При това е очевидно, а при следва от факта, че веригата не минава през и следователно цветът на никое ебро през не е поменен. Да забележим също, че при новото оцветяване пак е в сила включването , тъй като във върха няма как да се появи цветът , след като преди помяната той там е отсъствал. Ако съпоставим на реброто цвета (вместо ), който сега отсъства в и в , ще се окажем в условията на случая I и следователно съществува реброво k оцветяване на .
б-2) Нека сега върхът не е съединим с - верига с върха . Ще азсъждаваме аналогично. Да разменим цветовете в максималната - верига през върха (ако в отсъства не само , но и , тогава нищо не променяме). При новото реброво k оцветяване на във върха отсъства цветът , тъй като преди това е отсъствал . Във върха не да настъпили промени на цветовете и в частност ребрата ,,..., са запазили цветовете си, а също така пак имаме . И при новото оцветяване имаме , тъй като във върха няма как да се появи цветът , щом по-рано е отсъствал. Да забележим, че и в новото оцветяване имаме , тъй като и и в не може да се появи , щом по-рано е отсъствал. Да съпоставим на реброто цвета ( вместо ), който сега отсъства в . По отношение на ребрата ,,...,се намираме в условията на случая I и следователно съществува реброво k оцветяване на .
в) От върха Теорема 3 е доказана.
Ще казваме, че е зададено 2-оцветяване на ребрата на един граф G, ако всяко от тях е оцветено в един от два предварително взети цвята. Ще считаме, че единият е черен, другият – червен. До сега разглеждахме k оцветявания при които никои две еднакво оцветени ребра не са съседни и нарекохме това оцветяване реброво 2-оцветяване. Дефиниция: Наичаме една съвкупност от ребра на гафа G едноцветна, ако при дадено 2-оцветяване на ребрата му ребрата от съвкупността имат един и същ цвят. Дефиниция: Наричаме едно 2-оцветяване на ребрата на графа G нормално, ако няма нито един едноцветен триъгълник. Ако в G няма триъгълници, тогава всяко 2-оцветяване на ребрата му е нормално. Всеки граф с не повече от 5 върха притежава поне едно нормално 2 оцветяване.
 Но вече пълният граф с 6 върха  няма нито едно нормално 2 оцветяване.
Дефиниция: Наричаме един граф G граф на Рамзи, ако няма нито едно нормално 2-оцветяване на ребрата му, т.е. ако съществува поне един едноцветен триъгълник при произволно 2-оцветяване. Очевидно, ако G е подграф на H и G е граф на Рамзи, то H също е граф на Рамзи. Тъй като
Свойство 1. Ако и не съдържат триъгълници, то не е граф на Рамзи.
Док. Ако оцветим ребрата на и в червено, а в черно междинните ребра в G, получаваме нормално 2-оцветяване на ребрата.
Свойство 2. Ако графът G е върхово 5 оцветим, то той не е граф на Рамзи.  Док. Графът G е подграф на съединението  , където са дискретни графи. Ще оцветим в черно ребрата, съединяващи върховете на с върховете на , i=1,2,3,4,5.(). Всички останали ребра ще оцветим в бяло. Получаваме нормално 2 оцветяване.
Свойство 3. Да предположим, че не е граф на Рамзи. Тогава при всяко нормално 2 оцветяване на ребрата на G всички ребра на H имат един и същи цвят, две от ребрата на имат същия цвят, а през общия им връх всички междинни ребра на G са също едноцветни. Освен това графът H е върхово 2 оцветим.
Док. Нека 1, 2 и 3 са върхове на  и ребрата (1,2) и (1,3) са черни, тогава (2,3) е червено. Тогава всички междинни ребра излизащи от 1 са червени, понеже ако 1 се свързва с връх на H чрез черно ребро, то от този връх на H към 2 и 3 отиват червени ребра, но тогава се получава червен триъгълник от върховете 2, 3 и въхът на H.
Всяко ребро на H е черно понеже двата му края са свързани с 1 чрез червени ребра. Всеки връх на H е свързан с черно ребро с поне един от върховете 2 и 3(иначе ще има червен триъгълник. Останалите ребра са червени. Нека разделим H на 2 подкласа : A – състоящ се от 4 и 6(въховете които се свързват с 2 с черно ребро) и B – състоящ се от 5 и 7(въховете които се свъзват с 3 с черно ребро). А и B са независими понеже не образуват черен триъгълник, следователно H е върхово 2 оцветим. Следствие 1. Графът е граф на Рамзи тогава и само тогава, когато .
Свойство 4. Нека Ако G не е граф на Рамзи, тогава ри всяко номално 2 оцветяване на ребрата на G двете ребра на имат еднакъв цвят.
Док. Да допуснем, че при някое нормално 2 оцветяване на ребрата на G двете ребра на са оцветени различно. Нека например е бялото ребро на , е черното. Да означим с A множеството на онези върхове на H, които са съединени с с бяло ребро, а с B – множеството на останалите въхове на H. Съвсем просто се поверява, че A и B са независими множества, а това противоречи на факта, че .
Следствие 2. При всяко нормално оцветяване на ребрата на графа всичките ребра на имат еднакъв цвят.(G не е граф на Рамзи)
Знаем,че всеки граф с кликово число поне 6 е граф на Рамзи. От следствие 1 непоседствено получаваме, че има графи на Рамзи с кликово число 5. Споед това следствие е граф на Рамзи за всякo r и знаем че при . Измежду всички графи най-интересен е , понеже има най-малко върхове – само 8. По-долу ще покажем че няма графи на Рамзи с кликово число 5 и по-малко от 8 върха, а е единственият граф на Рамзи с кликово число 5 и 8 върха.
Лема 1. Нека G е граф с , в който е дадено върхово h оцветяване. Тогава в кой да е едноцветен клас съществува връх, който притежава съсед във всеки друг едноцветен клас.
Док. Понеже , т.е. h е минималният брой цветове нужен за оцветяването на върховете на G, нека означим с тези различни цветове. Допускаме обратното, т.е. че не съществува връх от даден цвят който притежава съсед във всеки друг цвят. Нека x е този връх и нека е цветът в който са оцветени върховете които не притежават съсед на x. Щом върховете от не са свързани по никакав начин с x следователно могат да се оцветят в неговия цвят, но тогава получаваме, че h-1 е минималният брой цветове нужен за оцветяването на върховете на G, но това е противоречие. Следователно допускането е грешно.
Теорема 1. Нека G има не повече от 8 върха Тогава .
Док. Да положим И така, Лема 1 ни дава право без оганичение на общността да считаме, че Върхът Върхът По същите съображения Върхът От последните два абзаца следва, че По същите съображения Нека забележим, че  и са съседни, защто иначе можем да си присъединим към и да получим 6 оцветяване с триелементен едноцветен клас.
Да означим с H графа, породен от върховете Теорема 1 е доказана.
Формулираното предложение е просто следствие от свойство 2 и теорема 1. Забележка. Тъй като
Преди малко доказахме,че има граф на Рамзи с кликово число 5 и 8 върха, но няма такъв граф с по-малко върхове. Аналогичната задача за кликово число 4 не е решена напълно. Ще построим граф на Рамзи с кликово число 4 и 16 върха. Нека означим с  и графите, изобразени на схемата. С помощта на графите и ще конструираме желания граф Г по следния начин. За върхове на Г обявим всички върхове на и и само тях. За ребра на Г ще обявим ребрата на и и освен тях още всевъзможните отсечки, съединяващи неизолираните върхове на подграфа с върховете на петоъгълника при
Теорема 2. Г е граф на Рамзи с кликово число 4 и 16 върха. Док. Отначало ще докажем, че Г е граф на Рамзи. Да допуснем противното и да вземем едно нормално 2 оцветяване на ребрата на Г. Прилагаме следствие 2 при Това показва, че Г е граф на Рамзи. За да завършим доказателството на теоремата остава само да покажем, че Върхът Доказахме, че няма 5-клики в Г, а съществуването на 4-клики е очевидно. Теоремата е доказана. 6. Любопитни факти Интересни са иследванията на Уейн Хейс, асистент професор в училището по информатика и компютърни науки на Калифорнийския университет, в областа на графи на Рамзи. Той полага сериозни усилия за намирането на по-ниски граници на малките числа на Рамзи. Използва 114 работни места в университета на Торонто за да търси Друг интересен аспект на графите на рамзи са игрите свързани с тях. Известна е следната игра: играчите се редуват в оцветяването на неоцветени върхове на граф G, като на всеки играч е зададен различен цвят, избиайки един връх за ход. При отбягващите игри, завършването на монохроматичен подграф изоморфен на дуг граф A води до незабавна загуба или е забранено и първият играч който не може да направи ход губи. В други игри играчът успял да завърши монохроматичен подграф изоморфен на A печели.
1. „Числа на Рамзи” проф. д.м.н. Николай Хаджииванов 2. „Small Ramsey Numbers” Stanisław P. Radziszowski: http://www.combinatorics.org/Surveys/ds1/sur.pdf
Каталог: files -> files files -> Р е п у б л и к а б ъ л г а р и я files -> Дебелината на армираната изравнителна циментова замазка /позиция 3/ е 4 см files -> „Европейско законодателство и практики в помощ на добри управленски решения, която се състоя на 24 септември 2009 г в София files -> В сила oт 16. 03. 2011 Разяснение на нап здравни Вноски при Неплатен Отпуск ззо files -> В сила oт 23. 05. 2008 Указание нои прилагане на ксо и нпос ксо files -> 1. По пътя към паметник „1300 години България files -> Георги Димитров – Kreston BulMar files -> В сила oт 13. 05. 2005 Писмо мтсп обезщетение Неизползван Отпуск кт Изтегляне 1.04 Mb. Сподели с приятели:
|