Қолданылған әдебиеттер
[1], [2], [3], [5], [16], [18].
Бақылау сұрақтары:
Графтың цикломатикалық саны деген не?
Гамильтондық жол деген не?
Дәріс №9. Ағаштар. Ағаштардың қасиеттері
Дәріс мақсаты:Графтармен орындалатын операциялармен таныстыру.
Кілттік сөздер:графтағы цикл,ациклдық,ағаштар,байланысқан графтар.
Жоспары:
Графтағы циклдылық
Ағаштар
Графтағы циклдылық
Егер кезкелген G графтың қыры кем дегенде бір элементарлық циклге жататын болса, онда ол графтың қырын циклділік қыр деп атайды, ал қарсы жағдайда ациклділік деп атайды: Ациклділікке мысал ретінде ілінген қырды келтіруге болады. Төмендегі екі пікір орындалады:
1)Байланысты графтан циклдік қырды шығарғанда, оның байланыстылығы сақталады.
2)Ациклдік қырды шығарғанда байланыспайтын граф болып өзгереді.
Біріншіден кезкелген тізбек үшін циклдік қырды циклдегі қалған қырлардың тізбегімен өзгертуге болады.
Екіншісі қарсы жолмен дәлелденеді, егер байланысты қалпында қалатын болса, онда алынған қырдың соңы элементарлық тізбекпен байланыста болар еді; алынған қырды орнына қойсақ, онда элементарлық цикл шығар еді, бұл мүмкін емес, себебі бұл қыр ациклді.
Ағаштар
Циклсіз байланысқан графты ағаш дейміз. Басқаша айтқанда барлық қырлары ациклділік болатын графты ағаш дейміз.
Төмендегі төрт шартты қанағаттандыратын графты ағаш дейміз:
Кезкелген қырды алып тастағанда байланысты граф байланыспайтын болады.
Қырлар саны төбелер санынан біреуі аз болатын байланысты граф.
Бір элементарлық тізбекте байланыста болатын граф.
Екі төбені байланыстыратын қырларды қосқаннан кейін пайда болған циклсіз граф.
Ағаштан кезкелген 0 төбені аламыз және оны тамыр , не ноль қабаттағы төбе дейміз. Көрші төбелерді 1-ші қабаттағы төбе, көрші i1 қабаттағы төбені
-ші қабаттағы төбе дейміз, тағы сол сияқты.
Ағаштағы әрбір төбе белгілі бір қабатқа жатады. Қабаттың номері ағаштағы төбелердің ара қашықтығы мен тамырына тура келеді. 3-ші қасиет
бойыншы әрбір байланыс i -ші қабаттағы қыр арқылы i1 -ші қабаттағы номермен төбемен байланыста болады да, ешқандай i -ші қабаттағы төбемен байланысты болмайды. Ағаштың осындай көрінісі өте қолайлы. Мұндай көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ақырғы қабаттағы төбе, бірақ басқалары болуы мүмкін).
1-сурет
Тамырды D ағашында бөлу оның төбелерінің жиынында жартылай реттелгенін анықтайдыда, егер және элементарлық тізбек тамырдан төбесінде -ні ұстайды.
Әрбір 0
|
төбе D2
|
ағаштың тамырын анықтайды, осы төбелерге іліну болып
|
табылады, мұнда
|
|
осы әрбір
|
D
|
ағаштың бөлігінде
|
D 0 D
|
.
|
|
|
|
|
|
|
|
Тамырды
|
D ағашында бөлу
|
оның
|
төбелерінің
|
|
жиынында жартылай
|
реттелгеніне
|
анықтайды да,
|
егер
|
және
|
|
элементарлық
|
тізбек
|
тамырдан төбесінде - ні ұстайды. Әрбір 0 төбеде
|
D ағаштың тамырын
|
анықтайды, осы төбелерге іліну болып табылады, мұнда
|
. Осы
|
әрбір
|
D ағаштың
|
бөлігіндеD 0D.
|
Барлық D0 ағаштың
|
бөліктері
|
өзінің
|
бұтақтарынан тамырына желімдеу арқылы пайда болады.
|
|
|
|
G байланысты графта біртіндеп барлық циклді қырларды алып тастаймыз. Сонда G графтың байланысты бөлігі сол төбелердің жиынынан тұратын элементарлық циклсіз ағашқа G графтың тұлғасын аламыз. Тұлға бір мағыналы емес таңдалады да, бірақ ациклді қырлары кезкелген тұлғаға кіреді.
D тұлғасына қарағанда граф бөлігінің барлық қырларынG/ D -діхордадейміз. Әрбір хорда тұлғаның екі төбесін байланыстырады.
Бақылау сұрақтары:
Ағаштар дегеніміз не?
Циклдылық деген не?
Ациклдылық дегеніміз не?
Префиксті код деген қандай код?
Макмиллан теңсіздігі.
Дәріс №10. Графтарда маршруттарды іздеу
Дәріс мақсаты:Графтармен орындалатын операциялармен таныстыру.
Кілттік сөздер:жол,цикл,тізбек.
Егер
|
k 1,n үшін
|
|
ekVik1,VikGграфтың тізбектелген төбелері мен
|
қырлары
|
|
|
|
|
|
|
|
|
|
Vi
|
e
|
Vi
|
e Vi
|
2 …
|
Vi
|
n 1
|
e
|
Vi
|
n
|
(*)
|
|
0 1
|
1
|
2
|
|
n
|
|
Vi0
|
төбесінен шығып Vin төбесіне беттесе, онда ол Vi0 - төбесі жолдың басы,
|
Vinжолдың соңы деп аталады (ұзындығы нольге тең болса, онда төбе біреугеғана болады). Жалпы алғанда (*) тізбегіндегі төбелер мен қырлардың ішінде қайталандыратын болуы мүмкін. Әрбір қыр үшін жолдың бағыты болуы тиісті.
(Vi0 - ден шығып Vin - ге жеткізуге тиісті ) не бағытсыздығы.
[Vi0 ,Vin ] жолы 1 , 2 , ..., n қырлары бойынша біртіндеп
Vi0,Vi1,…,Vinтөбелері арқылы жүріле алады.Жолды табиғи қарастырғанда графтөбелері мен қырлары арқылы өтіп, қозғалған дененің үздіксіз (траекториясы) жолы деген мағынаны береді.
Графтың еселіксіз қырлары үшін жолды төбелердің тізбегі арқылы беруге болады.
Бағытсыз графтың жолдарынан тұратын тізбектелген төбелер мен қырлар тізбек деп аталады.
Бұдан кез – келген жол тізбек болады да, керісінше бағытсыз графтар үшін жол және тізбек ұғымдары бір мағынасын бере алады.
Егер (*) тізбегін керісінше қарастырсақ VinnVn1n1Vn2 …V11V0 - керісінше жазылған тізбек кейінгі жағдайда бұл тізбектерде айырмашылық жоқ,
сондықтан бұл тізбектер Vi0 мен Vin төбелерінен тұрады.
Егер (*) тізбегінде Vi0Vinn0 тізбегенің басы шекті төбелері дәл келсе, онда мұндай жолды n ұзындығы бар нұсқа (оған сәйкес цикл) деп аталады. (*) тізбегіне әрбір төбе және әрбір қыр бір рет кіретін болса, онда мұндай жол тізбек, контур, цикл қарапайымдылықтар (элементарлықтар) деп аталады.
Графта тізбекті қозғалған дененің жолы деп қарастыруға болады. Онда жолды - әрбір қыр арқылы бағдарлама бойынша өтетін траектория екендігін көрсетуге болады.
Қарапайым жол екі рет бір қыр арқылы өтпейді. (*) тізбегіндегі қырға тек санда ғана қайталануы мүмкін, онда қайталанатын кейбір төбе, не (*) тізбектің
мынадай түрі болуы мүмкін Vi01Vi1
|
1 V0
|
(**)
|
|
|
Элементарлық жол, тізбек,
|
нұсқа (контур), цикл
|
G графтарының
|
астындағы кейбір графты қарастырайық.
|
|
|
|
1–ші
|
суреттегі бейнеленген
|
V1 1 V23 V45V34 V46V5қарапайым
|
тізбекті
|
көрсетеді де, бірақ элементарлық бола алмайды (V4 төбесін екі рет кездестіруге
|
болады)
|
жол болмайды, себебі
|
( 1
|
және 6 қырлары
|
қарама –
|
қарсы
|
бағытталған): V43V2 2V3 5V4 - элементарлық нұсқа (контур).
Егер [Vi0 ,Vin ] тізбегі (**) тізбегінен бөлек, элементарлық тізбек емес болса, онда V төбесі (*) тізбегіне кем дегенде екі рет кіруі мүмкін.
Vik төбесіне екі рет кіретін(*)тізбегінің бөлігі цикл болады да,олардысызған сан (*) тізбегінен қалғандарын Vi0 және Vin бар тізбекті құрайды. Осылай
элементарлық тізбекті, не (**) тізбегінен алуға болады. Оны бір Vi0 төбесіне ауыстыруға болады. Қарапайым циклге де осыны қолдануға болады:
a,b,b,c,a,c тізбегін береді. Графтық
V1,V2 кез – келген тізбек элементарлық тізбектің төменгі бөлігін сол соңғыларымен ішінде сақтайды.
Қарапайым, бірақ элементарлық емес тізбек элементарлық циклді бөлігі ете алады.
қыры (V төбесі) қарапайым цикл элементарлық төменгі циклді өзінің
бөлігі етеді, ол V арқылы өтеді.
Осындай тәсілмен жол және контур үшін ұқсас пікірлерді айқындайды.
Кез – келген графта төбелердің бір – бірімен қатынасы байланысқан тізбектің болуы бұл тұйықталған транзитивтілік қатынастағы көршілестер (сыбайластар). Олар рефлексивтік қасиетті қанағаттандыратын (төбенің өзі ұзындығы нольге тең екенін көрсетеді), симетриялық қатынаста тізбектің бағытының шамасы болмайды және транзитивтік қатынаста (желімдеп
жапсыру т. б.) біртіндеп өтетін тізбектер төбелер эквиваленттік сыныптарға бөлінеді.
Төменгі графтың керілген кластағы төбелерін байланысқан компоненттер деп атаймыз. Кезкелген екі төбені кем дегенде цепь арқылы бір қоспадағы компонентті қосады. Ол әртүрлі компонентті төбелер тізбегі арқылы байланыспайды.
Графтың екі төбесі тізбек арқылы байланысса, ондай графты қоспалы граф деп атаймыз. Компонентті қоспасы бар кез – келген граф G оған байланыстыратын G графикалық компонентке, графқа жатпайтын біраз көп төбелермен қырларды қоссақ, онда пайда болған графтың бөлігі байланыспайтын болады. Көптеген есептер шығарғанда тек қана байланысты графтарды қарастырады, себебі байланыспайтын графқа есепті шешу әрбір қоспа компонентінің қарастыруға қажет етеді.
Графикалық байланыстығын тексеру үшін (берілген қырлардың тізімінен, бір матрицадан) еріксіз алынған оның төбесінен байланысқан компонентті құру жеткілікті.
Ол үшін көптеген қырларды іріктеп, оған басында көршілестерді, одан кейін көршілестерді іргелестермен қоса т. б. осы процессті мүмкіндігінше соза беруге болады. Егер графтың барлық төбелері іргелестен тұрса, онда байланысқан граф, басқаша графтың бөлігі, кіретін құралған төбелері қоспа компонентінен тұрады. Осы процессті қалған төбелеріне қолданып, барлық байланыстық компонентті айқындауға болады.
Байланысқан графтан көптеген төбелеріне V ара қашықтықты тізбектегі аз қырлардың саны d V1,V2 ретінде V1 және V2 байланыстырады.
Арақашықтың d V1,V2 үшін барлық қасиеттер орындалады:
А) d V1,V2 0,d V1,V20;V1V2болғанда;
Б) d V1,V2 = d V2,V1 ;
В) d V1,V2+d V2,V3 d V1,V3үшбұрыш теңсіздігі.
Сондықтан V метрикалық кеңістікте тұрады.
Достарыңызбен бөлісу: |