-Дәріс тақырыбы. Графтар саны. Ағаштар (2 сағ)

12-Дәріс тақырыбы. Графтар саны. Ағаштар (2 сағ)

4 Теорема.Графта цикл болмауы үшін υ(G)= 0 қажетті және жеткілікті.

Айталық, G(V, E) бағытталмаған граф. G графының S₁, S₂, …,S_k циклдар жүйесі сызықты тәуелді деп аталады, егер қандай да бір i₁, i₂, …,i_r (1≤ i₁ ≤ i₂ ≤…≤ i_r ≤ k) S_i1 ∆ S_i2 ∆ …∆ S_ik ноль граф болса. Керісінше болса S₁, S₂, …,S_k циклдары сызықты тәуелсіз циклдар деп аталады. Сызықты-тәуелсіз циклдардың ең көп саны G графындағы тәуелсіз циклдар саны деп аталады.

5Теорема. Графтың цикломатикалық саны оның тәуелсіз циклдарының санына тең.

Хроматикалық сан. Әр төбесіне қандай да бір бояу сәйкестендірілген және сыбайлас төбелер әртүрлі бояулармен боялған граф деп аталады. G графын дұрыс бояуға қажетті бояулардың саны оның хроматикалық саны деп аталады және χ (G) болып белгіленеді.

6 Теорема.G графы ноль-граф болса ғана бір хроматикалы граф болады.

7 Теорема (Кениг теоремасы). Граф бихроматикалы болуы үшін онда тақ ұзындықты қарапайым цикл болмауы қажетті және жеткілікті.

Ағаштар, ағаштардың негізгі қасиеттері.Шексіз бағытталмаған байланысты граф ағаш деп, ал циклсыз байланыссыз граф орман деп аталады. Анықтама бола алатындай G ағашының кейбір қасиеттерін қарастырамыз:

а) G байланысты және циклы жоқ;

б) G циклы жоқ және n-1 қабырғасы бар;

в) G байланысты және n-1 қабырғасы бар;

г) G графында цикл жоқ, бірақ сыбайлас емес төбелер арасында қабырға қосу тек бір ғана циклдың пайда болуына әкеледі;

д) G байланысты, бірақ бұл қасиетін кез келген қабырға алынып тасталса жоғалтады;

е) G графының кез келген төбелер жұбы тек бір ғана шынжырмен байланысқан.

Граф қаңқасы.

Орман болатын G суграфы қаңқалы ағаш немесе G суграфының қаңқасы деп аталады.

Ең аз қосылу туралы есеп.(Ең аз салмақты қаңқалы ағаш құру.)

Жол тұрғызу есебі түрінде өрнектеуге болатын мына есептің практикалық мағынасы үлкен. Жолдар желісімен қосылуы қажет бірнеше қалалар болсын. Әр екі қаланы қосатын жолдың бағасы белгілі. Мүмкін болатын жолдар желісінің ең арзанын салу қажет болсын. (Жолдардың орнына электр желісін, мұнай құбыры желісі, т.б. алуға болады.

Негізгі әдебиет: 1 [161-180]; 2[108-114] .

Қосымша әдебиет: 7[88-130] .

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

1.Қандай графтар ағаштар деп аталады?

2.Графтың цикломатикалық санын қандай формуламен есептеуге болады?

3.Графтың хроматикалық саны деп нені айтады?

4.Граф каркасы деген не?

13-Дәріс тақырыбы. Графтардағы маршруттар( 2 сағат)

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

Маршруттар Айталық G= Н-граф болсын. Мұндағы a1, a2, … , an+1M U1 U2, … , UnR Анықтама: Егер Ui=(ai, ai+1), i=1, 2, …, n (екі көрші төбені қосатын қабырға ) болса

a₁, U₁, a₂, U₂, a₃, …, Un , a_n+1 (*) маршрут деп аталады. а₁-төбесі маршруттың басы, а_n+1-соңы болады. (*) Маршрутты төбелердің тізбегі арқылы беруге болады.Маршрут доғаларының саны оның ұзындығы деп аталады. Айталық, G н-граф болсын. Егер (*) маршрутта қабырғалар [a₁a₂],…, [a_na_n+1] әртүрлі болса, яғни әр қабырға бірден артық кездеспесе, маршрут шынжыр деп аталады, ал графтың кез келген төбесі 2-ден артық емес қабырғаға инцидентті болса (төбелер әртүрлі ), онда маршрут қарапайым шынжыр деп аталады.

Анықтама. Егер a₁=a_n+1 болса (*) маршруты циклды деп аталады (басы мен соңы бірдей маршрут).

Анықтама. Циклы бар маршрут шынжыр болса цикл деп аталады, ал маршрут қарапайым шынжыр болса қарапайым цикл деп аталады.

Анықтама. Бағытталмаған циклсыз граф ациклды граф деп аталады. Бағытталмаған графтың циклдарының ұзындықтарының ең кішісі құлаш деп аталады (обхват).

Бұл графта (1,2),(1,2,4,7),(3,4,5,6)-қарапайым шынжыр.(1,2,4,7,8,4) -қарапайым емес шынжыр(4-екі рет). (1, 2, 4, 7, 8, 4, 2) – шынжыр емес маршрут; (1, 2, 4, 7, 8, 4, 1) – қрапайым емес цикл; (1, 2, 4, 1) – қарапайым цикл; Графтың құлашы 3-ке тең. Айталық граф бағытталған болсын. Егер (*) маршруттарындағы доғалар әртүрлі болса, маршрут жол деп аталады.Егер a1=an+1 болса маршрут контур деп аталады. Контур жоқ графтар контурсыз граф деп аталады.

Маршруттың (жолдың) қабырғаларынаң (доғаларының)саны оның ұзындығы деп аталады.

Анықтама. Егер (a, b) жолы бар болса, онда b төбесі а дан жекізетін (достижымый) төбе деп аталады.

Мысал: Контур бар (1,2,3). 5-төбеге басқа кез-келген төбеден жетуге болады, ал 5-тен ешқандай басқа төбе жеткізбейді.

Графтың байланыс компоненттері.

Анықтама. Бірдей емес екі төбесі (,) G маршрутпен қосылған (-басы, -соңы) бағытталмаған G графы байланысты граф деп аталады. Анықтама: Егер бағытталмаған G графының әртүрлі а,в төбелері үшін (а,в) және

(в,а)маршруттары бар болса,онда G мықты байланысқан граф деп аталады.Мұндай ұғымды мультиграф үшін де енгізуге болады.Мысалдар:

Байланысты граф

Байланысты граф, бірақ мықты байланыс емес.

Байланысты емес граф

Кез келген байланысты бағытталмаған графтар мықты байланысқан граф екендігін байқауға болады.

Маршрутпен байланысты төбелер қарапайым шынжыр мен де байланысқан болады.

Байланыстылық қатынастың эквиваленттік қасиеті бар және ол граф төбелерін өзара қиылыспайтын V_i, i=1, 2, …, k ішкі жиындарға бөлінуін анықтайды. Сондықтан барлық ішкі графтар G(V_i) байланысқан және олар графтың байланыс компоненттері деп аталады..Бағытталған G графы доғалардың бағыты ескерілмесе байланысқан делінеді, ал егер кез келген V¹ төбесінен V¹¹ төбесіне жол болса мықты байланысқан болады.

Мысалы, мына суреттегі графта екі {1, 2, 3, 4} және {5, 6, 7} байланыс компонент тері бар. Ал мына төмендегі суреттегі бағытталған графта
{1,2,3},{4}және {5} төбелерімен берілген 3 мықты компоненттері бар. Теорема Кез келген графты қиылыспайтын байланыс компоненттерінің бірігуімен өрнектеуге болады. Графтың байланыс компоненттеріне жіктелуі бір мәнді анықталады. G=Ui G(Vi)

Сонымен, төбелердің байланысты компоненттері мен мықты компоненттер жиыны төбелер жиындарын бөлшектейді, ал байл. компоненттерінің саны бір мәнді анықталады.

Келесі теорема сыбайлас A_G матрицасы бойынша G графының маршруттарын зерттеуге мүмкіндік береді.

Теорема егер A_G - G графыың іргелестік матрицасы болса, онда матрицасының (i,j)-ші элементі ұзындығы к-ға тең (а_i,j) - маршруттарының санын анықтайды.

Салдар. A_G++…+ матрицасының (i,j) -ші элементі 0-ге тең болмаса ғана n қуатты G графында a_i төбесі ішінде болатын (a_i,a_j) - маршрут (a_i≠a_j) бар. Мысалы.

Сыбайлас AG матрицаның көмегімен G графында (1,3) маршрутының бар екендігін анықтаймыз.
	(1,3)- элемент 0-ге тең, демек ұзындығы 1-ге тең маршрут жоқ

(1,3)- элемент тағыда 0-ге тең. Ұзындығы 2-ге тең (1,3)- маршруты жоқ Ұзындығы 3-ге тең (1,3)- маршруттың саны 1-ге тең

Графтың суретінен бұл маршрут (1, 4, 2, 3) төбелерімен анықталады. Бұл тізбекті іргелестік матрицаны көбейту арқылы алуға болады: матр-ң (1, 3) элементі матр-ң (1, 2) элементімен A_G матрицаның (2, 3) элементін көбейткеннен алынады.

Өз кезегінде м-ң (1, 2) элементі A_G матрицаның (1, 4) эл-н A_G (4,2)-ге көб-нен алынды. Демек 1-ден 3-ке жылжи отыра үшқадамнан кейін (1, 4, 2, 3) маршруты алынады.

матриц-да (4, 2) элементі 3 ке тең, демек, ұзындығы 3 ке тең (4, 2)- маршрутының саны үшеу. Олар: (4, 1, 4, 2), (4, 2, 4, 2), (4, 2, 3, 2)

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

Айталық, төбелері υ1, υ2, υ3, υ4 бағытталған G графының сыбайлас матрицасы болсын. матрицасын қарастырайық. Жалпы алғанда, орындалатындай к саны бар болса ғана болады, басқаша айтқанда υі төбесімен υк төбесін және υк төбесімен υі төбелерін қосатын қабырға бар. Сондықтан υі төбесінен υj төбесіне апаратын ұзындығы 2-ге тең жол бар.

Теорема. Айталық, G төбелері υ1, υ2, υ3 ... υn және сыбайлас А матрицасы берілген бағытталған граф болсын. мен төбелерінің арасында (1≤к≤n) шарты орындалса ғана ұзындығы к –ға тең жол бар болады.

жүктеу 19,56 Mb.

Достарыңызбен бөлісу: