Графтар мен бинарлы қатынастар.

V жиынында берілген R қатынасына өзара бір мәнді анықталған, орындалса ғана қабырғасы бар болатын V төбелер жиындарымен қабырғалар еселі емес бағытталған G(R) графы сәйкес келеді.

1-мысал: Симметриялы, антисиметриялы, рефлексивті, антирефлексивті, транзитивті R бинарлы қатынасына өзара бір мәнді сәйкес G графының қандай ерекшеліктері бар?

Айталық , R бинарлы қатынасы жиынында анықталсын.

а) симметриялы R қатынасына еселі қабырғалары жоқ, орындалса ғана қабырғасы бар болатын бағытталмаған G(R) графы сәйкес келеді (симметриялы болғандықтан ).

б) Антисиметриялы R қатынасына еселі қабырғаларсыз,(әртүрлі төбелерге қарама-қарсы бағытталған қабырғалары бар төбелер болмайтын) өзара бір мәнді бағытталған G(R) графы сәйкес келеді .

в) Егер R рефлексивті болса, барлық төбелерінде ілгектері бар еселі қабырғаларсыз G(R) графы сәйкес келеді.

г) Егер R антирефлексивті болса, еселі қабырғаларсыз G(R) графында бір де бір ілгек болмайды.

д) Егер R транзитивті болса, еселі қабырғаларсыз G(R) графының әрбір және қабырғалар жұбына оларды тұйықтайтын қабырғасы бар болады.

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

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

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

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

2. Қандай графтар бағытталмаған деп аталады?

3. Графтарда қандай төбелер сыбайлас төбелер деп аталады?

4. Төбелер дәрежесі деген не?

5. Графтардың берілу тәсілдерін атаңыз.

6. Графтармен қандай операциялар орындалады.

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

Дәріс тақырыбы:

Цикломатикалық сан.Бағытталмаған G(V, E) графы берілсін. υ(G)=m-n+p, Мұндағы m–граф қабырғаларының саны; n–граф төбелерінің саны; p–байланысты компоненттер саны G(V, E) графының цикломатикалық саны деп аталады. Цикломатикалық санының физикалық мағынасы бар: ол графтың тәуелсіз циклдарының санына тең. Электр шынжырларын есептеген кезде цикломатикалық сан тәуелсіз контурлар санын есептеуге қолданылады.

1-Теорема.Егер G1 графы G графының суграфы болса, онда υ(G1)≤ υ(G).

2-Теорема.Байланысты графтацикл болмауы үшін υ(G)=0 қажетті және жеткілікті.

3-Теорема. Егер G графтың екі байланысты G₁ және G₂ компоненттері бар болса, онда υ(G)=υ(G₁)+υ(G₂).

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 графының кез келген төбелер жұбы тек бір ғана шынжырмен байланысқан.

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

8-Теорема. Граф байланысты болса ғана орман болатын суграф болады.

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

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

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

Ең арзан жолдар желісін кескіндейтін граф әрқашан ағаш болады. Себебі, егер цикл бар болса, циклдың бір қабырғасын алып тастауға болар еді, ал төбелер қосылған болып қала берер еді. Есептің математикалық қойылуы. Айталық, бағытталмаған G(V, E), |V|=n, графының әр қабырғасына осы қабырғаның салмағы болып саналатын қандай да бір μ(e) нақты сан бекітілген болсын. G графында салмағы ең аз, ең кіші қосылу, яғни G графының Т қаңқасын салу керек болсын.

μ(T)= .

Краскал алгоритмін қарастырайық (ең аз салмақты қаңқалы ағаш сызу).

Сызу жұмысын салмағы μ(e₁ ) ең аз e₁ қабырғасын таңдаудан басталады. Егер мұндай қабырғалар бірнешеу болса, олардың кез келгенін алуға болады. Таңдалған қабырғаға E\{e₁} алынған ең аз салмақты е2 қабырғасы е3 ретінде цикл құрмайтын E\{e₁,е₂} деп алынған ең аз салмақты E\{ e₁,е₂, e₃} таңдалады. Қабырға таңдау процесі кез келген қабырға қосу цикл пайда болуына әкеліп соққанға дейін жүргізіледі. Осы граф ең аз салмақты қаңқалы ағаш болып саналады.

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

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

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

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

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

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

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

5. Ағаштардың негізгі қасиеттерін атаңыз?

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

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

Маршруттар.Айталық G=<M,R> Н-граф болсын.

Мұндағы a₁, a₂,…,a_n+1 M U₁ U₂, … , U_n R

Анықтама: Егер U_i=(a_i, a_i+1), i=1, 2,…,n (екі көрші төбені қосатын қабырға ) болса a₁, U₁, a₂, U₂, a₃,…,U_n, 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-ке тең. Айталық граф бағытталған болсын. Егер (*) маршруттарындағы доғалар әртүрлі болса, маршрут жол деп аталады. Егер a₁=a_n+1 болса маршрут контур деп аталады. Контур жоқ графтар контурсыз граф деп аталады.

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

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

Мысал: Контур бар (1,2,3).

5-төбеге басқа кез-келген төбеден жетуге болады, ал 5-тен ешқандай басқа төбе жеткізбейді.