Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану



бет18/30
Дата23.12.2021
өлшемі0,66 Mb.
#127967
1   ...   14   15   16   17   18   19   20   21   ...   30
Байланысты:
darismatlogidm

Бақылау сұрақтары:

  1. Ағаштар дегеніміз не?

  2. Циклдылық деген не?

  3. Ациклдылық дегеніміз не?

  4. Префиксті код деген қандай код?

  5. Макмиллан теңсіздігі.

Дәріс №10. Графтарда маршруттарды іздеу

Егер k=1…n үшін ek   Vik 1,Vik G графтың тізбектелген төбелері мен қырлары Vi0 e1 Vi1 e2 … Vin-1 en Vin (*) Vi0төбесінен шығып Vin төбесіне беттесе, онда ол Vi0 төбесі - төбесі жолдың басы, Vin төбесі - жолдың соңы деп аталады (ұзындығы нольге тең болса, онда төбе біреуге ғана болады). Жалпы алғанда (*) тізбегіндегі төбелер мен қырлардың ішінде қайталандыратын болуы мүмкін. Әрбір қыр үшін жолдың бағыты болуы тиісті. (Vi0 -ден шығып Vin –ге жеткізуге тиісті) не бағытсыздығы.

Графтың еселіксіз қырлары үшін жолды төбелердің тізбегі арқылы беруге болады. Бағытсыз графтың жолдарынан тұратын тізбектелген төбелер мен қырлар тізбек деп аталады.

Бұдан кез – келген жол тізбек болады да, керісінше бағытсыз графтар үшін жол және тізбек ұғымдары бір мағынасын бере алады.

Егер тізбегін керісінше қарастырсақ, керісінше жазылған тізбек кейінгі жағдайда бұл тізбектерде айырмашылық жоқ, сондықтан бұл тізбектер Vi0 мен Vin төбелерінен тұрады. Егер Vi0 = Vin тізбектің басы шекті төбелері дәл келсе, онда мұндай жолды n ұзындығы бар нұсқа (оған сәйкес цикл) деп аталады. (*) тізбегіне әрбір төбе және әрбір қыр бір рет кіретін болса, онда мұндай жол тізбек, контур, цикл қарапайымдылықтар (элементарлықтар) деп аталады.

Графта тізбекті қозғалған дененің жолы деп қарастыруға болады. Онда жолды - әрбір қыр арқылы бағдарлама бойынша өтетін траектория екендігін көрсетуге болады.

Қарапайым жол екі рет бір қыр арқылы өтпейді. (*) тізбегіндегі қырға тек санда ғана қайталануы мүмкін, онда қайталанатын кейбір төбе, не (*) тізбектің мынадай түрі болуы мүмкін Vi0 l1 Vi1 l2 … Vin-1 ln Vin (*)

Элементарлық жол, тізбек, нұсқа(контур), цикл G графтарының астындағы кейбір графты қарастырайық. 1–ші суреттегі бейнеленген V1 l1 V2 l3 V4 l5 V3 l4 V5l5V6 қарапайым тізбекті көрсетеді де, бірақ элементарлық бола алмайды, себебі l1 және l2 қырлары қарама–қарсы бағытталған):

V4 l3 V2 l2 V3l5V4 - элементарлық нұсқа (контур).

Егер Vi0 e1 Vi1 e2 … Vin-1 en Vin тізбегі (**) тізбегінен бөлек, элементарлық тізбек емес болса, онда V төбесі (*) тізбегіне кем дегенде екі рет кіруі мүмкін. Vik төбесіне екі рет кіретін (*) тізбегінің бөлігі цикл болады да, оларды сызған сан (*) тізбегінен қалғандарын Vi0 және Vin бар тізбекті құрайды. Осылай элементарлық тізбекті, не (**) тізбегінен алуға болады. Оны бір Vi0 төбесіне ауыстыруға болады. Қарапайым циклге де осыны қолдануға болады:

1) [V1, V2] кез – келген тізбек элементарлық тізбектің төменгі бөлігін сол соңғыларымен ішінде сақтайды.

2) Қарапайым, бірақ элементарлық емес тізбек элементарлық циклді бөлігі ете алады.

3) l қыры (V төбесі) қарапайым цикл элементарлық төменгі циклді өзінің бө-лігі етеді, ол l(V) арқылы өтеді.

Осындай тәсілмен жол және контур үшін ұқсас пікірлерді айқындайды.

2. Кез – келген графта төбелердің бір – бірімен қатынасы байланысқан

тізбектің болуы бұл тұйықталған транзитивтілік қатынастағы көршілестер (сыбайластар). Олар рефлексивтік қасиетті қанағаттандыратын (төбенің өзі ұзындығы нольге тең екенін көрсетеді), симетриялық қатынаста тізбектің бағытының шамасы болмайды және транзитивтік қатынаста (желімдеп жапсыру т. б.) біртіндеп өтетін тізбектер [a,b], [b,c],[ c, a] тізбегін береді. Графтық төбелер эквиваленттік сыныптарға бөлінеді. Төменгі графтың керілген кластағы төбелерін байланысқан компоненттер деп атаймыз. Кезкелген екі төбені кем дегенде цепь арқылы бір қоспадағы компонентті қосады. Ол әртүрлі компонентті төбелер тізбегі арқылы байланыспайды.

Графтың екі төбесі тізбек арқылы байланысса, ондай графты қоспалы граф деп атаймыз. Компонентті қоспасы бар кез – келген граф G оған байланыстыратын G графикалық компонентке, графқа жатпайтын біраз көп төбелермен қырларды қоссақ, онда пайда болған графтың бөлігі байланыспайтын болады. Көптеген есептер шығарғанда тек қана байланысты графтарды қарастырады, себебі байланыспайтын графқа есепті шешу әрбір қоспа компонентінің қарастыруға қажет етеді.

Графикалық байланыстығын тексеру үшін (берілген қырлардың тізімінен, бір матрицадан) еріксіз алынған оның төбесінен байланысқан компонентті құру жеткілікті.

Ол үшін көптеген қырларды іріктеп, оған басында көршілестерді, одан кейін көршілестерді іргелестермен қоса т. б. осы процессті мүмкіндігінше соза беруге болады. Егер графтың барлық төбелері іргелестен тұрса, онда байланысқан граф, басқаша графтың бөлігі, кіретін құралған төбелері қоспа компонентінен тұрады. Осы процессті қалған төбелеріне қолданып, барлық байланыстық компонентті айқындауға болады.

Байланысқан графтан көптеген төбелеріне V ара қашықтықты тізбектегі аз қырлардың саны d(V1, V2) ретінде V1 және V2 байланыстырады. Арақашықтың D(V1, V2) үшін барлық қасиеттер орындалады:



  1. d(V1, V2)=0, d(V1, V2)>0; (V1V2)болғанда

б) d(V1, V2)= d(V2, V1)

в) d(V1, V2)+ d(V2, V3)≥ d(V1, V3)үшбұрыш теңсіздігі.

Сондықтан V метрикалық кеңістікте тұрады.




Достарыңызбен бөлісу:
1   ...   14   15   16   17   18   19   20   21   ...   30




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет