Курсът е воден от проф д. м н. Николай Хаджииванов



страница2/4
Дата14.01.2018
Размер1.04 Mb.
#46384
1   2   3   4

Лема 1. Ако v е връх на графа G със степен d h-1 и подграфа G-v е върхово h-оцветим, тогава и графът G е върхово h-оцветим.

Док: Да вземем едно h-оцветяване на върховете на графа G-v. Съседите на v в G са измежду върховете на G-v и следователно всеки от тях получава някакъв цвят при разглежданото h-оцветяване. Ясно е обаче, че поне един цвят не е използван при оцветяването на . Ще го използваме при оцветяването на v. По този начин получаваме h-оцветяване на върховете на графа G. Лема 1 е доказана.

С помощта на лема 1 лесно се доказва следното:



Зад 1.

Док: Ще приложим индукция по броя n на върховете на G. При n=1 твърдението е очевидно. Ще допуснем че то е вярно и за всеки граф с n-1 върха.

Нека G е граф с n върха. Ако отстраним от него произволен връх v заедно с ребрата през него, ще получим подграф G-v с n-1 върха. Съгласно индукционното предположение

Очевидно е, че d(G-v) d(G).

И така, графът G-v e (1 + d(G))-оцветим. Тъй като d(v) d(G), то от лема 1 следва, че графът G e също (1 + d(G))-оцветим, т.е.

Зад 1 е доказана.

Зад 2. за произволен граф G с n върха са в сила неравенствата:

(1) . (2) .



Доказателство: Да вземем едно χ(G)-оцветяване на върховете на G. Да означим с броя на върховете от -ия едноцветен клас Ai. Имаме .

Тъй като Ai. е независимо множество, α(G)

По такъв начин неравенство (1) е доказано.

За да докажем (2), ще вземем независимо множество A с α(G) на брой върхове. Ще оцветим всички върхове от А в един и същ цвят, а всички останали върхове на G в различни цветове (различни от тези на А). Получаваме (1+(n - α(G)))-оцветяване на върховете на G. Следователно χ(G) 1+(n - α(G)).

По такъв начин неравенство (2) е доказано.

Зад 2 е доказана.

От (1) следва, че ако G е граф с n върха, а е допълнителния му, то(3)

И очевидно

Следващата теорема на Нордхауз и Гадум усилва неравенство (2):

Теорема 1. Нека G е граф с n върха, а е допълнителния му. Тогава (4)χ(G)+ χ() n+1

Док: Неравенство (4) ще докажем с индукция по n. при n = 1 е очевидно. Ще допуснем, че (4) е вярно за всеки граф с n-1 на брой върхове.

Нека G е граф с n върха и v е един от тях. Ще означим с Г графа с G-v върха, който се получава от G след премахване на върха v и всички ребра през него. По индукционното предположение имаме: (5) χ(Г)+ χ() n+1

Очевидно (6) χ(G) χ(Г)+1

Тъй като =-v, то и (7) χ() χ()+1

От (5),(6) и (7) следва, че χ+ ≤ n+2, т.е. по- малко от това, което трябва да докажем. Но ако поне от неравенствата (6) или (7) е строго, тогава желаното неравенство (4) е вярно. Поради това трябва да отделим особено внимание на случая, когато и в (6) и в (7) има равенство, т.е. χ(G)= χ(Г)+1 и χ()=χ()+1

От равенството χ(G)= χ(Г)+1 и лема 1 имаме: (8)

Аналогично от равенството χ()=χ()+1 и лема 1 имаме: (9) d(v) χ()

От неравенства (8) и (9) и очевидното следва, че χ(Г)+ χ() n-1

от (6), (7) и (10) следва желаното (4).

Теорема 1 е доказана.

А сега ще докажем, че за всяка тройка естествени числа h, и n, за който h+ = n+1 съществува граф G с n върха, такъв че χ(G)= h и χ()=.

Да вземем пълен граф Кh с h върха и към него да присъединим още n-h върха, през който не минават никакви ребра. Така построения граф удовлетворява всички изисквания.

От теорема 1 и неравенството между средно аритметично и средно геометрично получаваме:

Следствие__1'>Следствие 1. Ако G е граф с n върха, а е допълнителния му граф, тогава:

(11) , където с [x] означаваме цялата част на реалното число x.

Има граф G с n върха, за който (11) преминава в равенство. При четно n такъв е например графът при h= , а при нечетно – графът при h=.

Да отбележим и едно следствие от зад 2 и неравенството между средно аритметично и средно геометрично:



Следствие 2. за произволен граф G с n върха са валидни неравенствата: и χ(G)+χ().

    1. Неравенство на Брукс за хроматично число и степен на един граф.

От Зад 1 знаем, че (12) χ(G) 1 + d(G). Интересен е въпросът, кога се достига равенството. Сега ще дадем отговор на този въпрос.

При d(G)=0, т.е. когато графът G е дискретен, тогава очевидно χ(G)=1. В този случай (12) преминава в равенство.

При d(G)=1 никои две ребра нямат общ връх. И в този случай е очевидно, че χ(G)=2, т.е. в (12) има равенство.

А сега да разгледаме случая, когато d(G)=2.



Зад 3. Нека е G граф със степен d(G)=2. При това предложение равенството χ(G)=3 е налице, т.е. в (12) има равенство, тогава и само тогава, когато G има подграф от вида C2r+1

Док: Да забележим, че щом d(G)=2, то от всеки връх на графа G излизат най-много две ребра, така че G има за компоненти само прости вериги. Всяка незатворена проста верига е върхово 2-оцветима. Една затворена проста верига Cm е върхово 2-оцветима само тогава, когато m е четно число.

Направените разсъждения правят очевидна зад 3.

Да преминем към разглеждане на случая d=d(G)≥3 . Ако в G има (d+1)-клика, тогава очевидно χ(G)1+d, така че в (12) трябва да има равенство. Нека да се убедим, че и обратното е вярно, като докажем следното твърдение на Брукс:

Теорема 2. Нека графът G има степен d=d(G)≥3 и χ(G)=1+d. Тогава в G има (d+1)-клика.

Док: Ще направим доказателството с индукция по броя n на върховете на графа G.

Преди да направим първата стъпка на индукцията, да забележим, че щом G удовлетворява условията на теоремата, то очевидно n≥d+1. Следователно първата стъпка на индукцията се свежда до доказване на твърдението за граф с d+1 на брой върхове. В този случай е очевидно, че множеството на всички d+1 върхове на графа е клика.

Първата стъпка на индукцията е направена.

Да допуснем сега, че твърдението е вярно за графи с n-1 върхове и нека G е граф с n върхове, за които d=d(G)≥3 и χ(G)=1+d.

Ще вземем един връх v0 на G със степен d(v0)= d и ще положим Г= G-v0.

От очевидното неравенство χ(G) χ(Г) +1 следва, че χ(Г)≥d.

Ако d(Г)≤d-1, чрез зад 1 получаваме χ(Г)≤ d(Г)+1≤d, така че (13)

Ако d(Г)= d и χ(Г)=d +1, от индукционното предположение следва, че Г съдържа (d+1)-клика. Следователно G съдържа (d+1)-клика и в този случай индукционната стъпка от n-1 към n е направена.

Поради това можем да считаме, че и при d(Г)= d равенство (13) е на лице.

Направеното разсъждение ни помага да считаме отсега и до края на доказателството, че (13) е изпълнено.

И така, Г притежава върхови d–оцветявания. Поради това ще се запасим с d на брой цветове, които ще използваме за върхови d–оцветявания на Г; да ги означим с

Разсъжденията, който следват, ще извършим на няколко етапа.



  1. При всяко върхово d-оцветяване на Г съседите на v0 получават d

различни цвята.

Наистина, ако например c1 не е използван за оцветяване на съсед на v0, тогава можем да оцветим v0 в c1 и по такъв начин да получим върхово d–оцветяване на G, което е невъзможно понеже χ(G)=d +1.

Твърдението I е доказано.


  • При произволно върхово d-оцветяване на Г съседите на vi в Г получават d-1

различни цвята (1≤i≤d). Следователно съседите на vi в Г са d-1 и всеки е оцветен различно (и различно от vi).

От I знаем, че всички съседи на на v са оцветени различно. Нека е върхът, оцветен в cm, 1≤m≤d. Ако допуснем, че цветът при не е използван за оцветяване на никой съсед на v, тогава можем да преоцветим vi в и да получим противоречие с I, тъй като в новото d–оцветяване на Г върховете vi и имат един и същ цвят.

Твърдение II е доказано.

Нека γ е фиксирано d–оцветяване на Г. Както по-горе, цветовете на γ означаваме с . Под -верига (при оцветяването γ) ще разбираме такава верига в Г, всеки от върховете на която е оцветен или в или в .



  • Нека γ е фиксирано d–оцветяване на Г и а е връх на Г. Да означим с М

множеството на онези върхове на Г, всеки от които можем да съединим с а чрез -верига. Ако разменим цветовете на и на върховете на М, а запазим всички останали както са в γ, получаваме все пак върхово d-оцветяване на Г.

  • При произволно d-върхово оцветяване γ на Г за всеки два цвята и има –верига, съединяваща два съседа vi и на v0 в G .

Нека γ е фиксирано d–оцветяване на Г и е съсед на v0 в G, който има за цвят cm (1≤m≤d ). Твърдението II, показа че има точно един връх a1, съседен на vi, който е оцветен в. Ако vi и са съседни, тогава, разбира се, a1=. Ако vi и не са съседни, тогава a1≠vj. Ще считаме, че vi и не са съседни.

Очевидно, ако μ е -верига, съединяваща vi и (такава съществува съгласно IV ), трябва a1 да е първият връх в μ след vi.

Върхът a1 има точно един съсед, различен от vi, който е оцветен в. Един такъв съсед е първият след a1 връх на μ.

Да допуснем, че a1 има два такива съседа a2’и a2”. Самият a1 е оцветен в, а съседите му . За останалите съседи на a1 (те са най-много d-3 на брой) са използвани най-много d-3 цвята. Следователно общо за a1 и съседите му са изразходвани не повече от d-1 цвята (между който и). Да означим с ck цвят, различен от въпросните d-1 цвята (следователно).

Ще изменим оцветяването само на a1, като заменим цвета му с ck. Получаваме пак върхово d–оцветяване на Г; ще го означим с γ’.

Съгласно IV можем да съединим vi и с –верига при μ’ оцветяването γ’. Тъй като всички върхове , които са оцветени в или при γ’, са оцветени в същите цветове и при γ, то μ’ е –верига и при γ. Но малко по-горе се убедихме, че във всяка -верига при γ, която съединява vi и, a1 е първият връх след vi. И така a1 е от μ’, но това не е възможно, понеже a1 има цвят ck при γ’().

Окончателно доказахме, че има едноцветен връх; различен от vi, който е оцветен в при γ и е съседен на a1; ще означим този връх с a2.

Ясно е тогава, че във всяка -верига (при γ), съединяваща vi и , a1 и a2 са първите два върха след vi.

След неколкократно повторение на горните разсъждения достигаме до следния извод:


  • При произволно върхово d–оцветяване на Г съществува единствена -верига, съединяваща vi с . Тази верига е проста и при това, ако някой връх на Г не е от веригата, но има цвят или , то той не е съседен на никой връх от веригата.

При даденото върхово d–оцветяване на Г единствената -верига съединяваща два съседа на v0 в G, ще означаваме с . Ясно е, че единият край на веригата е оцветен с , а другият с .

  1. При произволно върхово d–оцветяване γ на Г веригите и при имат

единствен общ връх (и той е онзи съсед на v0 в G, който е оцветен в ).

Ще означим с vi онзи съсед на v0 в G, който е оцветен в . Аналогично с vi и . означаваме съседите на v0 в G, който са оцветени съответно в и ck. Тогава краищата на са vi и , а на и . Ще докажем, че единственият общ връх на и е .

Да допуснем, че a е общ връх за е , който е различен от . Преди всичко е ясно, че a е оцветен в . Да означим с a- онзи връх от , който непосредствено предшества a, с a+ - онзи, който го следва. Аналогично с b и b+ ще означим върховете от , които са съседни на a. Върховете a и a+ са оцветени в , а b-, b+ - в ck. Освен тези четири съседа върхът a има още най-много d-4 съседа. За тяхното оцветяване с употребени най-много d-4 на брой цветове. Значи за оцветяване на a и всичките му съседи са използвани най-много d-1 на брой цветове (измежду които са , и ck). Тогава има поне един цвят , различен от тези d-1 цветове (и следователно различен от , и ck ). Ще преоцветим само върха a от в . По този начин получаваме ново върхово d–оцветяване γ’ на Г.

Да разгледаме веригата Тя има краища vi и , но не съдържа a, тъй като a има при цвят. Ако един връх е оцветен в или при , той има и при γ същия цвят. Следователно е -верига и при γ(съединяваща очевидно vi и ). Съгласно V а това не е възможно, тъй като a е връх от .

Полученото противоречие завършва доказателството на твърдение VI.


  • Множеството от съседите на v0 в G е dклика в Г.

Да допуснем противното и нека например v1 и v2 са съседи на v0 в G, които не са съседни помежду си, а v3 е произволен съсед на v0 в G, различен от v1 и v2.

Нека γ е върхово dоцветяване на Г. Ще означим с c1, c2 , c3 цветовете, в които са оцветени v1, v2 и v3. Да разменим цветовете c1 и c3 на върховете на μ13(γ), но да запазим оцветяването на всички останали върхове. Съгласно V и III получаваме пак върхово dоцветяване на Г; ще го означим с γ’. При оцветяването γ’ върховете v1, v2, v3 имат цветове съответно c3, c2, c1.

Да означим с a първия връх след v1 във веригата μ12(γ). Да отстраним от тази верига v1 и получената верига да означим с μ. Направеното преоцветяване не е засегнало върховете на μ, тъй като единственият общ връх на μ12(γ)и μ13(γ) е v1. Тогава с помощта на V заключваме, че μ е част от веригата μ12(γ). Следователно върхът a е от μ12(γ).

Тъй като a е оцветен и при γ’ в c2 и е съседен на v1, а v1 е от μ23(γ) (v1 е край на тази верига), то съгласно V върхът a е също от тази верига.

Доказахме, че a е общ връх за веригите μ12(γ) и μ23(γ). Върхът v2 също е от тези две вериги. От VI следва, че av2. Това е невъзможно, тъй като v1 и v2 не са съседни, а v1и a са съседни.

Полученото противоречие завършва доказателството на твърдение VII.

От VII следва, че v0 заедно с всичките си съседи образуват (d+1)-клика в G.

Индукционната стъпка от n-1 към n е направена.

Теорема 2 е доказана.

Проведените разсъждения за доказване на теорема 2 фактически дават нещо повече. Вярна е следната



Теорема 3. Hека и Ако, тогава v0 се съдържа в ()-клика.

Каталог: 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   2   3   4




©obuch.info 2024
отнасят до администрацията

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