Негізгі анықтамалар
жүктеу/скачать 289,71 Kb.
|
13-15АПТАдәрістері
| 2. Іздер мен өтулер
6.3.1 Жол (тізбе) – деп графтың қабырғалары екі рет кездеспейтін ізді айтамыз. Мысалы, 6.4 суреттегі G5 графында А1А2А3А1А6АА4А3А1 ізі жол болмайды, себебі мұнда А1А3қабырғасы екі рет кіріп тұр. Графта Эйлер жолы (өтуі) деп графтың барлық қабырғаларын құрайтын жолды айтады, яғни жолда графтың әр қабырғасы бір рет кездесу керек (төбелеріне қатысты ештеңе айтылған жоқ, сондықтан кез-келген жолда төбелер қайталанып кездесуі мүмкін). Эйлер жолы бар граф эйлер графы деп аталады, егер осы жолдың басы мен соңы беттессе, онда граф эйлер циклі деп аталады. Жеңіл дәлелденеді. 6.4 теорема. а) Байланысты граф эйлер циклі деп аталады, сонда және тек қана сонда, егер оның барлық төбелері жұп дәрежелі болса. б) Байланысты графта басы А төбесінде, соңы В төбесінде болатын эйлер өтуі болады, сонда және тек қана сонда, егер А мен В төбелерінің дәрежелері тақ, ал қалған төбелерінің дәрежесі жұп болса. 6.3.2 Мағынасы бойынша жақын болатыны – гамильтондық граф. Гамильтондық цикл (жол) деп бастапқа төбені қоспағанда, графтың әрбір төбесінен бір реттен өтетін (кейбір қабырғалардан мүлдем өтпеуі де мүмкін) циклді (жолды) айтамыз. Эйлер циклі есебінің сыртқы ұқсастығына қарамастан, гамильтондық цикл бар граф анағұрлым күрделі. Қазіргі таңға дейін гамильтондық белгілердің біраз ғана жеткілікті белгілері бар ал, қажетті бергілері әлі де аз. 6.5 теорема. Байланысты графтың n төбесі болсын. а) (Оре). Егер кез-келген төбелер жұбының дәрежелерінің қосындысы n-1 –ден аз емес болса, онда берілген графта гамильтон циклі болады. б) (Дирак). Егер графтың әр төбесінің дәрежесі n/2-ден аз емес болса, степень каждой вершины графа не менее n/2, берілген графта гамильтон циклі болады. в) (Хватал) (d1,d2,…,dn) – G графының вектор-дәрежесі болса және ,және кез-келген k үшін және және теңсіздігі орындалса, онда G графы – гамильтондық цикл болады. Аспалы төбелері бар графтар, яғни дәрежесі 1-ге тең болатын графтар, гамильтондық емес цикл болып табылады. Сонымен қоса, 6.10 суретте көрсетілген графта гамильтондық цикл жоқ. Одан біртіндеп қабырғаларын бөлу арқылы алынған графғ яғни дәрежесі екіге тең төбелер қосылғанда, тэтта-граф деп аталады. Бұдан төмендегі теореманы алуға болады. 6.6 теорема. Егер графта тэтта-ішкіграф болса, онда ол гамильтондық цикл емес. Қарапайым жағдайларда, есептердегі графтар қандай болады, осы екі белгілер графтың гамильтондық еместігін анықтауға толығымен жеткілікті. Егер сызбадан гамильтондық өту көре алсаңыз, оны көрсетіңіз, бірақ, егер 5-теореманы қолдана алсаңыз онда бұл сізге қосымша артықшылықтар болады. жүктеу/скачать 289,71 Kb. Достарыңызбен бөлісу:
|