Негізгі анықтамалар
жүктеу/скачать 289,71 Kb.
|
13-15АПТАдәрістері
| 3. Ағаштар мен қаңқа
6.4.1 Ағаш–циклсіз байланысты граф. Ағаштар тәжірибеде әртүрлі иерархияларды салуда кездеседі. Графта циклдің болуы оның цикломатикалық санын (әрине, мұнда графтың сызбасымен жұмыс істемейміз) анықтауда көп көмегін тигізеді: , мұндағы m–қабырғалар саны, n – төбелер саны, k – байланыстылық компоненттерінің саны. Мысалы, 6.10 суретте көрсетілген графта бір ғана байланыстылық компоненті болғандықтан, оның цикломатикалық саны 6–5+1=2 болады. 6.11 суреттегі графта байланыстылық компоненттері екеу: G1 мен G2 ішкі графтары, сондықтан оның цикломатикалық саны: (6+6)–(7+5)+2=2. Егер әрбір байланыстылық компоненттерін жеке-жеке граф деп қарастырсақ, онда олардың цикломатикалық сандары: және . G1 ағаш болатынын көреміз. Келесі теорема теңдігі кездейсоқ емес болғандығын көрсетеді. 6.7 теорема. Кез –келген графтың цикломатикалық саны –теріс емес сан болады, және ол нөлге тең болады, сонда және тек қана сонда, егер графта цикл болмаса. Ағаштардың келесі қасиеттері жиі қолданылады. 6. 8 теорема. N төбелі ағаштардың эквивалентті анықтамалары. а) N-1 қабырғасы бар және циклсіз граф. б) N-1 қабырғасы бар және байланысты граф. в) Байланысты граф және кез-келген қабырғасын жою оны байланыссыз етеді. г) Кез-келген төбелер жұбы жалғыз ғана жолмен (тізбемен) жалғанады. д) Циклсіз граф және кез-келген екі төбенің арасына қабырға қосу тек бір ғана цикл қосуға келтіреді. Байланысты графтың қаңқасы (арқау, арқаулы ағаш) деп графтың барлық төбелері ағаштар болатын, ішкі графты айтамыз. Қаңқаны көрсетерде оны құрап тұрған қабырғаларды жазып шығаыд. Мысалы, 6,11 суреттегі G2 графта (AB), (BD), (DC), (BE) ағашы қаңқа болып табылады. Бір графта бірнеше қаңқа болуы мүмкін екенін көру қиын емес. 6.4.2 Тәжірибелік сабақтар үшін бірқатар маңызды тапсырмаларда (сабақ кестесін құру, құрылғыларды бөліп беруде т.с.с.) графтың төбелерін немесе қабырғаларын бояуға әкеледі. Біз дұрыс төбелік бояуларды ғана қарастырамыз, яғни графтың кез-келген сыбайлас төбелері әртүрлі түске боялған жағдайлар. Мұндай дұрыс төбелік бояуларды қысқаша бояулар деп қана айтамыз. Мысалы, 6. 11 суретте G2 графын үш түске бояуға болады: А, Е және D төбелерін бір түспен бояймыз, В мен С төбелерін – басқа түспен бояймыз, үшінші түс қолданылмай қалды. Сонымен, G2 графы 2-бояулы және 3-бояулы болады. G графы k-бояулы болса, онда k-ның минималды саны осы графтың хроматикалық саны деп аталады және деп белгіленеді. Жалпы жағдайда хроматикалық санды табуға арналған есептер өте күрделі келеді. Бірақ, төбелер саны аз (10-ға дейін) болса, оны «қолмен» санап есептеуге болады. Мысалы, біз G2 графының нақты екі бояуын көрдік, кез-келген бос емес, яғни тым болмаса бір қабырғасы бар графты екіден аз түспен бояуға болмайды, сондықтан Басқа жағдайларда, нақты бір бояулары көрсетілген соң, қандай жолмен түстер санын кемітуге болатыны көрінбейді, минималды бояу алғанымызды негіздеп алуымыз керек. Бұған келесі жағдай көмектесе алады: 1) n төбесі бар Kn толық графтың хроматикалық саны n-ге тең; 2) Kn толық графының бір қабырғасын жою арқылы алынған графтың хроматикалық саны n – 1-ге тең; 3) жұп төбелі жай циклдің хроматикалық саны 2-ге тең, ал тақ болса – 3-ке тең; 4) тұтас бір графтың хроматикалық саны оның кез-келген ішкі графының хроматикалық санынан кем емес. Сондықтан, мысалы, графы 4түске бояуға мүмкіндік болса және одан К4 ішкі графын (диагональдары жүргізілген төртбұрыш) көрсеңіз, онда осы графтың хроматикалық саны 4-ке тең болады. Келесі хроматикалық санды бағалаулардың пайдасы зор. 9 теорема. белгісі G графының төбелерінің ең үлкен дәрежесін білдірсін. Онда келесі теңсіздіктер орынды болаыд: а) ; б) (Брукс) егер G – байланысты және толық емес граф болса және , онда . 6.4.3 Келесі келтірілетін графтар туралы ұғымдардың тәжірибелік маңызы өте зор. Белгіленген граф деп – қабырғасы және/немесе төбесі нөмірленген графтарды айтамыз. Мысалы, 6.2 және 6. 3 суреттердегі G2 мен G3 графтары, сәйкесінше изоморфты граф ретінде бірдей болғанмен, A, B, C, D, E төбелерін алфавиттік түрде реттелген деп есептесек, онда олар белгіленген граф ретінде әртүрлі графтар болады. жүктеу/скачать 289,71 Kb. Достарыңызбен бөлісу:
|