Су "Св. Климент Охридски" Факултет по математика и информатика

1. Биографична справка

Родителите му са Артър Стенли Рамзи и Агнес Мари Уилсън. Артър Рамзи е бил президент на колежа „Магдалена” в Кеймбридж и преподавател по математика в същия колеж. Франк е бил най-големия от четирите деца в семейството. Имал е един брат и две сестри. Брат му става Кентърберийски архиепископ.

Рамзи постъпва в колежа „Уинчестър” през 1915г. и там той спечелва стипендия за колежа „Тринити” в Кеймбридж. През 1920г., след завършването си в Уинчестър, постъпва в колежа Тринити да учи математика. В Кеймбридж Рамзи става стипендиант в по-горните курсове през 1921г. и завършва с титлата Wrangler(студент завършващ с отличие по математика в Кеймбриджския университет) след Mathematical Tripos(изпит за получаване на научна степен в Кеймбридж) през 1923.

След завършването си Рамзи е във Виена за известно време и се връща в Кеймбридж след като е избран за член на научно дружество на King's College Cambridge (някои университети в Кеймбридж) през 1924. Това е изключение, като се има в предвид, че Рамзи е едва втория човек, който някога е избиран за член на King's College, без да е бил преди това студент там.

През 1925г. Рамзи се жени за Летисия Бейкър, с която имат две дъщери. Следващата година той е назначен за университетски преподавател по математика и по-късно става ръководител на Катедрата по Математика в King's College. Кариерата му е била кратка, защото за нещастие Рамзи умира в началото на 1930г – на 19 януари в Лондон.

Въпреки краткото време, през което той е изнасял лекции в Кеймбридж, си е спечелил славата на изключителен преподавател.

Макар, че Рамзи е работил основно в областта на математиката, той е творил в забележително широк кръг области за краткото време на своя живот. В областта на математиката, Рамзи поставя основите на нова математическа теория, сега наречена “Теорията на Рамзи”, той пише и за основите на икономиката (“Статия за теорията на облагането с данъци” и “Математическа теория за спестяванията”) и философията (“Факти и твърдения” и “Общоизвестното за правото и фактите”).

2. Основни понятия

Ако графът G´=(V´, E´) е съставен от върхове и ребра на графа G=(V, E), казваме че е G´ подграф на G. Ако два върха на подграфа G´ са съединени с ребро на G´ тогава и само тогава когато са съединени с ребро на G, казваме че G´ е породен подграф G.

Два графа G´и G´´ са изоморфни тогава, когато съществува еднозначно-обратимо съответствие между V´ и V´´, при което два върха на V´ са съединени с ребро в G´ точно тогава, когато съответните им върхове са съседни с ребро в G´´.

Ако всеки два върха са на един n-върхов граф са съединени с ребро, наричаме го пълен и го бележим с Кn. Нека Г е подграф на Kn, т.е. Г имам не повече от n върха. С К˜n ще означаваме подграфа на Кn, който се получава, като отстраним от Кn ребрата на Г. Следователно Кn˜ има върховете на Кn, а негови ребра са всички ребра на Кn, които не са ребра на подграфа Г. В частност, ако Г има едно ребро, графа Кn˜ ще означаваме с Кn¹. С други думи Кn¹, е подграфът на Кn, който се получава след отстраняване на едно ребро от Кn. К10* е подграфът на Кn, който се получава след отстраняване на 3 ребра от Кn, а Кn" е подграфът, който се получава от Кn след отстраняване на 4 ребра.

На черт. 1 са изобразени всички 3-реброви графи без изолирани върхове, т.е. без върхове, които не са краища на ребра.

Сега ще въведем понятието оцветяване на ребрата на граф. Нека G=(V, E) е един граф и E=E1 U E2. Тогава ще казваме че е зададено 2-оцветяване на ребрата на графа G, като ребрата от E са оцветени в първия цвят, а ребрата от E2 –във втория. Един подграф на G ще наричаме едноцветен при разглежданото оцветяване, ако всичките му ребра са с един и същ цвят. Съгласно една известна теорема на английския математик Ф. Рамзи, за всеки граф Г може да се намери такова n, че при всяко оцветяване на ребрата на Кn да се появи едноцветен подграф, изоморфен на Г. Ако при всяко 2-оцветяване на ребрата на един граф G сигурно се появява подграф, изоморфен на Г, тогава G се нарича Г-граф.

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

Черт. 1

3. Задачи за оцветяване на ребрата на 10-върхови графи

Лема 1. На чертеж 2а и чертеж 2б е изобразено отделно чрез черните и белите ребра единственото оцветяване на К8, при което няма едноцветни К4¹. Черният и белият граф на това оцветяване са изоморфни.

Лема 2. Ако към графа от чертеж 2а присъединим нов връх и го съединим с ребра с поне 4 върха, така че да не се получи К4¹, тогава ще получим графа от чертеж 3.
Четр.2а Черт. 2б


Черт. 3 Черт. 4

3.1. Формулировка и доказателство на основното твърдение

Теорема. Ако графът G е получен от К10 чрез отстраняване на трите ребра на път с дължина 3, тогава при всяко черно-бяло оцветяване на ребрата на G имаме едноцветен К4¹.

Доказателство: Ще номерираме върховете на G с числата 1, 2, ..,10, така че 9 и 10 да имат значението от чертеж 4, където са изобразени отстранените от К10 ребра.
Черт. 5 Черт. 6 Черт. 7


Ясно е, че всеки два измежду върховете 1,2,..8 са съседни с ребро и следователно те са върхове на пълен 8-върхов подграф К8.

Да допуснем, че твърдението не е вярно и следователно има чернобяло оцветяване на G без едноцветни К4¹. Това оцветяване поражда върху графа К8 оцветяването, за което става дума в лема 1.

От върха 9 към върховете 1, 2,..8 излизат 7 ребра и понеже цветовете са само два, то поне 4 ребра измежду тях имат един и същ цвят. Без ограничение на общността можем да приемем, че този цвят е черен, защото иначе можем да разменим цветовете на всички ребра, при което оцветяването на К8 няма да се промени.

И така, от 9 към 1, 2,..,8 излизат поне 4 черни ребра. Според лема 2 те са точно 4 и при това са разклонени като на чертеж 3. Тогава останалите три ребра от 9 към 1, 2,.., 8 са бели и очевидно без ограничение на общността можем да считаме, че имаме оцветяването посочено на чертеж 5.

От върха 10 към върховете 1, 2,..8 също излизат 7 ребра. Както по-горе достигнахме до заключението, че 4 от тях имат един и същ цвят, а останалите 3-друг цвят. Но сега бихме ограничили общността, ако приемем че черните са 4. Всъщност, ако те наистина са 4, тогава имаме оцветяването от чертеж 6, а ако белите са 4-оцветяването от чертеж 7. В първия случай имаме черни К4¹, а във втория -бял К4¹, т.е. и в двата случая достигаме до противоречие и по такъв начин теоремата е доказана.

4. Едно интересно свойство на 10-върховите графи с 42 ребра

Свойството е следното: ако оцветим всяко от ребрата на такъв граф в черен или бял цвят, сигурно е, че ще има два едноцветни триъгълника с обща страна.

4.1. Предварителни сведения

При всяко оцветяване в черен или бял цвят на всяко от ребрата на пълния 10-върхов граф К10 със сигурност могат да се намерят два едноцветни триъгълника с обща страна. При това в току-що изказаното твърдение графът К10 не може да бъде заменен с К9. На чертеж 8а е изобразено чрез черния си граф оцветяване на К9, при което няма едноцветен К4¹. Белият граф на същото оцветяване е изобразен на чертеж 8б.

Вече доказахме че оцветяването от чертеж 8 е единствено оцветяване на К9, при което няма едноцветни К4¹. Всички върхове играят еднаква роля при оцветяването, така че върхът с номер 9 може да се смята за който и да е от тях.

Разбира се, пълният граф К8 може да бъде оцветен, така че да няма едноцветен К4¹. Това оцветяване можем да получим от оцветяването на чертеж 8, като отстраним върха 9 и всички ребра с край този връх. Полученото оцветяване и изобразено на чертеж 9.

Максималният брой ребра в един 10-върхов граф е =45; 45 ребра има само К10. следователно 10-върховите графи с 42 ребра се получават от К10 след отстраняване на 3 ребра.

Черт. 8а Черт. 8б


Черт. 9а Черт. 9б

4.2.При всяко оцветяване на К10* има едноцветен К4¹

Ще номерираме върховете на графа К10* с 1,2,…10, като оставим номера 10 за онзи връх, през който минават трите отстранени ребра.

Да допуснем, че обявеното в заглавието на параграфа твърдение не е вярно, и да разгледаме оцветяване на К10* без едноцветни К4¹. Върху пълния подграф К9 с върхове 1,2,..9 това оцветяване трябва да съвпадне с изобразеното на чертеж 8. Можем да приемем, че реброто [10,9] е черно, тъй като не е възможно всички ребра през 10 да са бели, а върхът 9 е който и да е от върховете на подграфа К9.

Върховете 10 и 2 не са съседни с черно ребро, защото иначе реброто [9,2] би било обща страна на два черни триъгълника. Аналогично твърдение е в сила и за върховете 4,6 и 8.

И така, върхът 10 не е съседен с черно ребро с никой от върховете 2, 4, 6, 8. От върха 10 към върховете на черния триъгълник (1, 3, 5, 7) излизат най-много две черни ребра, и то към противоположни върхове, защото всяка от страните на този четириъгълник е страна на черен триъгълник в подграфа К9.

Така доказахме, че ако има оцветяване на К10* без едноцветни К4¹, тогава 10 е съседен с черни ребра най-много с 3 от останалите върхове (с 9 и с два противоположни върха на черния четириъгълник (1, 3, 5, 7)). Такива три върха са върховете на бял триъгълник в К9.

Разбира се, нямаме основания да предпочетем черния цвят, ето защо можем да твърдим, че 10 е свързан с бели ребра най-много с 3 от останалите върхове и че тези 3 върха са върхове на черен триъгълник в подграфа К9.

И така, ако има оцветяване на К10* без едноцветен К4¹, то в оцветяването на К9 от чертеж 8 трябва да има бял и черен триъгълник без общи върхове. Но такива два триъгълника няма.

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

4.3. При всяко оцветяване на К10" има едноцветен К4¹

Ще номерираме върховете на графа К10" с 1, 2, ..10, като оставим номерата 9 и 10 за два от върховете на отстранените ребра- 9 е връх на изолираното отстранено ребро, а 10 е общият връх на двете инцидентни отстранени ребра.

Да допуснем, че обявеното в заглавието твърдение не е вярно, и да разгледаме оцветяване на К10" без едноцветни К4¹. Върху пълния подграф К8 с върхове 1, 2, ..8 това оцветяване изглежда така, както е показано на чертеж 9. От върха 9 излизат 7 ребра към върховете на подграфа К8 и следователно поне 4 от тях имат един и същ цвят. Тъй като черният и белият графи от чертеж 9 са изоморфни, без ограничение на общността можем да предполагаме, че от върха 9 излизат 4 черни ребра към върховете на подграфа К8. Лесно е да се съобрази, че в такъв случай върхът 9 е съединен с черни ребра с върховете 2, 4, 6, 8 и други черни ребра от 9 към върховете на подграфа К8 няма. Тогава останалите 3 ребра от 9 към тези върхове са бели и без ограничение можем да смятаме, че тези бели ребра са [9,1], [9, 3], [9, 7].

От върха 10 излизат 6 ребра към върховете на подграфа К8. Ако допуснем, че 4 от тях са черни, тогава, както лесно се вижда, това са ребрата [10, 2], [10, 4], [10, 6], [10, 8] и по такъв начин получаваме черен К4¹. По същия начин, ако 4 ребрата са бели, тогава те са [10, 1], [10, 3], [10, 5], [10, 7] и получаваме бял К4¹.

Следователно от върха 10 към върховете на подграфа К8 излизат три бели и три черни ребра.

Ще разгледаме отделно двата случая, които могат да възникнат за цвета на реброто [9, 10].

Нека [9, 10] е черно. Тогава е ясно, че върхът 10 не може да бъде съединен с черно ребро с никой от върховете 2, 4, 6, 8 (иначе ще има черен К4¹) и следователно е съединен с черни ребра с 3 от върховете на черния четириъгълник (1, 3, 5, 7). Тогава 10 ще бъде съединен с черни ребра с два последователни върха на този четириъгълник, така че ще се образува черен К4¹, което е противоречие.

Нека сега [9, 10] е бяло ребро. Ако допуснем, че 10 е съединен с бяло ребро с 3, тогава [3, 9, 7] и [3, 9, 10] са бели триъгълници с обща страна, т.е. има бял К4¹, което е противоречие. Върхът 10 не е съединен с бяло ребро и със 7 по същите съображения.

Да допуснем, че 10 е съединен с бяло ребро с 1. Върховете 10 и 5 са съединени с ребро и това ребро не може да бъде бяло, защото иначе [1, 10, 5] и [1, 10, 9] ще бъдат бели триъгълници с обща страна. Следователно [10, 5] е черно ребро.

Върховете 10 и 3 не могат да бъдат съединени с бяло ребро, защото [9, 10, 3] и [9, 10, 1] биха били бели триъгълници с обща страна. Но 10 и 3 не могат да бъдат съединени и с черно ребро, защото [3, 5, 10] и [3, 5, 4] биха били черни триъгълници с обща страна. Следователно 10 и 3 не са съединени с ребро. Поради симетрията 10 и 7 не са съединени с ребро. Със същите съображения се доказва, че 10 и 4 не са съединени с ребро. Наистина, ако 10 и 4 са съединени с бяло ребро, тогава [10, 4, 1] и [10, 9, 1] са бели триъгълници с обща страна, а ако 10 и 4 са съединени с черно ребро, тогава [10, 4, 5] и [3, 4, 5] са черни триъгълници с обща страна.

Така достигнахме до противоречието, че броят на ребрата на графа К10" е по-малък от 42. това противоречие се дължи на допускането, че 10 е съединен с бяло ребро с 1. По-горе доказахме, че 10 не е съединен с бяло ребро нито с върха 3, нито с върха 7. Всяка от страните на белия четириъгълник (2, 4, 6, 8) е страна на бял триъгълник в подграфа К8, така че 10 не е съединен с бели ребра с никои два съседни върха на този четириъгълник.

От 10 излизат 3 бели ребра към върховете на К8. следователно 10 е съединен с бели ребра с 5 и с два противоположни върха на белия четириъгълник (2, 4, 6, 8). Тогава 10 е съединен с 5 и с поне един от върховете 2, 8 с бели ребра; поради симетрията можем да предполагаме, че 10 е съединен с бяло ребро с 2. тогава [2, 5, 8] и [2, 5, 10] са два бели триъгълника с обща страна, което е противоречие.

С това доказателството на обявеното твърдение е завършено.

Каталог: 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 Писмо мтсп обезщетение Неизползван Отпуск кт

Изтегляне 103.5 Kb.

Сподели с приятели: