Типовой расчёт №3(Дискретная математика)

АЛМАТЫ ЭНЕРГЕТИКА ЖӘНЕ БАЙЛАНЫС ИНСТИТУТЫ

ЖОҒАРЫ МАТЕМАТИКА КАФЕДРАСЫ

Дискрет математика

Есептеу-графикалық жұмыстарды орындауға

арналған әдістемелік нұсқаулар мен тапсырмалар

(050704 – Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері үшін)

3 бөлім

ҚҰРАСТЫРУШЫЛАР: Л.Н. Астраханцева, М.Ж.Байсалова.

Дискрет математика. 050704 – Есептеу техникасы және бағдарламалық

қамтамасыз ету мамандығы бойынша оқитын барлық бөлім студенттері

үшін есептеу-графикалық жұмыстарды орындауға арналған әдістемелік

нұсқаулар мен тапсырмалар. 3 бөлім - Алматы: АЭжБИ, 2008. - 22 б.

«Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығы

бойынша оқитын барлық бөлім студенттеріне арналған есептеу графикалық жұмыстарды орындауға арналған әдістемелік нұсқаулар мен тапсырмалар

«Дискрет математика» пәнінің № 3 типтік есептеулерден тұрады.

Бағдарламаның теориялық сұрақтары енгізілген. Типтік варианттың шешімі

келтірілген.

1 Есептік-графикалық жұмыс 3. Графтар

1.1 Теориялық сұрақтар

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

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

3 Графтар мен бинарлы қатынастар арасындағы байланыс. Графтардың изоморфизмі. Ішкі графтар. Графтарға қолданылатын қисаптар.

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

5 Байланыстылық және мықты байланыстылық компоненталарының анықтамасы. Жетерлік матрицасы.

6 Графтың маршруттарын зерттеу (берілген ұзындықты маршрутты анықтау және олардың саны).

7 Графтағы ара қашықтық (эксцентриситет, диаметр, радиус, центр)

8 Өлшенген графтар. Салмақ матрицасы. Өлшенген ара қашықтық. Ең қысқа жолды табу (Дейкстра алгоритмі).

9 Ағаштар, орман. Діңгекті ағаштар. Діңгек граф. Цикломатикалық сан. Графтағы діңгекті ағаштар саны (Кирхгоф теоремасы).

10 Ең аз салмақты діңгек ағашты табу (Краскаль және Прим алгоритмдері).

1.2 Есептік тапсырмалар

1-4 V={1,2,3,4} төбелері мен E={a,b,c,d,e,f,k,l} доғалар жиынынан тұратын G=(V,E) графы берілген. Доғалар бастапқы және соңғы төбелерімен анықталған.

1. Осы графты салыңыз:

а) графиктік жолмен;

ә) инциденттік матрицасы көмегімен;

б) сыбайластық матрицасы көмегімен;

в) доғаларының тізімімен;

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

3. Егер бар болса, екі қолжетерлік және екі қолжетерлік емес төбелерге мысал келтір. Берілген граф байланысты бола ма? Мықты байланысты бола ма?

4. Графқа сәйкес бинарлы қатынасты анықтаңыз. Берілген қатынас қандай қасиеттерге ие болады (рефлексивтік, симметриялық және т.б.)?

1 К е с т е

_1.1

_1.2

_1.3

_1.4

_1.5

_1.6

_1.7

_1.8

_1.9

_1.10

_1.11

_1.12

_1.13

_1.14

_1.15

_1.16

_1.17

_1.18

_1.19

_1.20

_1.21

_1.22

_1.23

_1.24

_1.25

_1.26

_1.27

_1.28

1 кестенің жалғасы

_1.29

_1.30

5 Берілген G графы үшін

а) ара қашықтық матрицасын;

ә) эксцентриситетін, диаметрін, радиусын;

б) орталық және алшақ орналасқан төбелерін табу керек.

2 К е с т е

5.1

5.2

5.3

5.4

5.5

5.6

5.7

5.8

5.9

5.10

5.11

5.12

5.13

5.14

5.15

5.16

5.17

5.18

5.19

5.20

5.21

5.22

5.23

5.24

5.25

5.26

5.27

5.28

5.29

5.30

6 Берілген н-граф үшін:

а) сыбайластық матрицасын;

ә) А төбесінен шығатын ұзындығы 2 болатын барлық маршруттарды;

б) салмақ матрицасын;

в) А төбесінен қалған төбелерге дейінгі ең қысқа маршрутты;

г) цикломатикалық санды;

д) ең аз салмақты ағашты табу керек.

6.1 6.2

В 4 С 6 D B 8 E

3 5 2 7 1 2 4

D 4

А 2 F 4 Е A C

6.3 6.4

В 2 D 2 Е D 1 E

A 1 3 5

5 3 2 4 1 2 F

А 4 C 3 F B 6 C

6.5 6.6

5 E B 8 D

4 3 4

2 D 3 A 7 1 F

A 5

3 C 6 8

C 6 E

6.7 6.8

6.9 6.10

B 4 C B

3 3 4 1 2

11 8 2

C 5

D 4 F

A 5 E 7 3

6.11 6.12

B 4 C B 8

3 C

A 5 7

3 4 2 15 3

9 4 D

A 8 F 7 E 6

6.13 6.14

B B

2 C 3 4

5 2

3 1 5

A 1 D A C

11 4 3 6

E E 2 D

6.15 6.16 B

B 3

4 1 C 6

3 C 4 2

2 D A 1 D

4 2

A E

3 6

F 2 E

6.17 6.18

A 4 B 6 C A 8 D

3 5 2 7 2 4

C 4

F 2 E 4 D E B

6.19 6.20

A 2 C 2 D C 1 D

F 1 3 5

5 3 2 4 1 2 E

3 4

F 4 B 3 E A 6 B

6.21 6.22

5 D A 8 C

4 3 4

2 C 3 F 7 1 E

E 5

3 B 6 8

B 6 D

6.23 6. 24

A 4 B A

3 3 4 1 2

11 8 2

B 5

C 4 E

E 5 D 7 3

6.25 6. 26

A 4 B A 8

3 B

E 5 7

3 4 2 15 3

9 D 4 C

F 8 E 7 D 6

6.27 A 6.28 A

2 B 3 4

5 2

3 1 5

E 1 C E B

11 4 3 6

D D 2 C

6.29 6.30 A

A 3

4 1 B 6

3 B 4 2

2 C Е 1 C

4 2

F D

3 6

E 2 D

1.3 Типтік варианттың шешуі

1-4 V={1,2,3,4,5} төбелері мен E={a,b,c,d,e,f}= = доғалар жиынынан тұратын G=(V,E) графы берілген. Доғалар бастапқы және соңғы төбелерімен анықталған.

1. Осы графты салыңыз:

а) графиктік жолмен;

ә) инциденттік матрицасы көмегімен;

б) сыбайластық матрицасы көмегімен;

в) доғаларының тізімімен.

3. Егер бар болса, екі қолжертерлік және екі қолжертерлік емес төбелерге мысал келтір. Берілген граф байланысты бола ма? Мықты байланысты бола ма?

Шешуі:

1. а)

1 Сурет

б) m төбелі және n қабырғалы орграф үшін инциденттік матрицасы

келесі түрде жазылады , мұндағы

Сонымен, ;

в) m төбелі және n қабырғалы орграф үшін сыбайластық матрицасы келесі түрде жазылады мұндағы

Сонымен, ;

г) доғалар тізімі

доғалар	Төбелер
a	1,2
b	1,4
c	2,3
d	3,2
e	4,5
f	4,6

2. (v)- v төбесінің дәрежесі, ол v төбесіне инцидентті қабырғалар санына тең.

, n - қабырғалар саны. Орграф үшін - v төбесінің шығу дәрежесі, ол басы v төбесінде болатын доғалар санына тең; - кіру дәрежесі, соңы v төбесінде болатын доғалар санына тең. , .

Біздің есепте шығу дәрежесі: , ,,, ; кіру дәрежесі: , ,. Сәйкес н-граф үшін төбелер дәрежесі , , , , , . .

3. Біздің графқа сәйкес бинарлық қатынас келесі түрде болады P=, оның матрицасы графтың сыбайлас матрицасына тең . матрицасының бас диагоналында бірліктер болмағандықтан, Р қатынасы рефлексивті емес. Ал , сондықтан Р симметриялы емес. Мысалы, , бірақ , бұдан Р транзитивті емес.

4. Егер басы u және соңы v болатын жол бар болса, онда v төбесі u төбесінен жетерлік болады. Сонымен біздің графта 2 және 3 төбелері өзара жетерлік; 3, 5, 6 төбелері 1 төбесінен қолжетерлік; 1 төбесі ешқандай төбеден жетерлік емес.

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

1, егер j төбесі i -ші төбеден қолжетерлік болса,

с_ij =

0, қарсы жағдайда;

ә) жетерлік емес матрицасын ; 3) матрицасын, мұндағы . S матрицасының бірінші жолының бірлері мықты байланыстылығының компонентасына енетін төбелерге сәйкес келеді. Ойша осы төбеге сәйкес келетін элемент тұрған жол мен бағанды сызып тастаймыз.

Қалған матрицадағы бірінші жолдағы бірлер екінші мықты байланыстылығының компонентасына енетін төбелерге сәйкес келеді, т.с.с. - графтың саны. Егер =1, онда орграф мықты байланысқан, егер >1, онда мықты байланыспаған. Мықты байланыстылық компоненталарының төбелер жиыны граф төбелерінің жиынының бөлікшесін құрайды: .

Біздің граф үшін аталған матрицаларды құрайық.

– жетерлік матрицасы.

– жетерлік емес матрицсы.

. S матрицасының бірінші жолында жалғыз бір бар, ол 1 төбесіне сәйкес келеді. Сонымен, мықты байланыстылығының бірінші компонентасы. Бірінші жол мен бірінші бағанды сызып тастағаннан кейін қалған бірінші жолда 2 және 3 төбелеріне сәйкес келетін екі бір бар, яғни – мықты байланыстылығының екінші компонентасы. Ойымызды осылай жалғастырсақ, тағы да үш мықты байланыстылығының компонентасын аламыз , , . Мықты байланыстық компонентасының саны =5. Граф төбелерінің жиынының бөлікшелері .

5 Берілген G графы үшін:

2 Сурет

а) ара қашықтық матрицасын;

ә) эксцентриситетін, диаметрін, радиусын;

б) орталық және алшақ орналасқан төбелерін табу керек.

Шешуі:

а) – ара қашықтық матрицасы, мұндағы – және төбелерінің арасындығы ара қашықтық, яғни ұштары және болатын жай шынжырдың ұзындығы.

Графтағы төбелерді нөмірлейік.

3 Сурет

Сосын ара қашықтық матрицасын табамыз:

;

ә) төбесінің эксцентриситеті (белгіленуі ) – бұл осы төбеден ең алшақ орналасқан төбеге дейінгі ара қашықтық болғандықтан, ара қашықтық матрицасындағы i-ші жолда тұрған ең үлкен санға тең. Сонымен, е(1)=3, е(2)=2, е(3)=3, е(5)=2, е(6)=3. Графтың диаметрі – =3; радиусы – =2;

б) егер төбесі үшін орындалса, онда алшақ орналасқан деп, ал болса, онда орталық төбе деп аталады. Сонымен, 1, 3, 4, 6 төбелері – алшақ орналасқан, 2, 5 – орталық.

6 Берілген н-граф үшін:

4 Сурет

а) сыбайластық матрицасын;

ә) А төбесінен шығатын ұзындығы 2 болатын барлық маршруттарды;

б) салмақ матрицасын;

в) А төбесінен қалған төбелерге дейінгі ең қысқа маршрутты;

г) цикломатикалық санды;

д) ең аз салмақты ағашты табу керек.

Шешуі:

5 Сурет

а) - сыбайластық матрицасы;

ә) әрбір төбеден ұзындығы екіге тең маршрутты табу үшін келесі матрицаны есептейміз

Тек А төбесінен ұзындығы екіге тең маршрутты табу керек болғандықтан, матрицасының тек бірінші жолын қарастырамыз: . Бұл А-дан А-ға ұзындығы екіге тең 2 маршрут бар екендігін білдіреді; А-дан D-ға 2 маршрут бар; , А-дан В-ға ұзындығы екіге тең 1 маршрут бар.

Маршрут қай қабырға арқылы өтетінін білу үшін қоымша матрица құраймыз . Бұл матрица А-ның әрбір элементін сәйкес төбеге айырбастау арқылы алынады.

болғандықтан, А-дан А-ға ұзындығы екіге тең 2 маршрут бар: ААА және ААА; болғандықтан, А-дан D-ға ұзындығы екіге тең 2 маршрут бар: АВD және АСD; , бұдан А-дан Е-ге ұзындығы екіге тең 1 маршрут бар: АВЕ;

б) - салмақ матрицасы, мұндағы - доғасының салмағы. Егер мұндай доға болмаса сәйкес салмақ орнына 0 немесе қоямыз (егер төбелер сыбайлас болмаса, онда ). Берілген граф үшін салмақ матрицасы ;

в) А төбесінен басқа төбелерге ең қысқа маршрут I Дейкстра алгоритмы бойынша табамыз: n төбелі өлшенген G(V,E) графы берілсін. - оның салмақ матрицасы (). төбесінен (ол бастамасы деп аталады) қандай-да бір басқа төбеге дейінгі өлшенген ара қашықтықты табу керек. Айта кетелік, бұл алгоритм бастамадан басқа төбеге дейінгі ара қашықтықты бірден табуға мүмкіндік береді. Бірінші қадамда , белгілеуін енгіземіз, мұндағы (яғни - бастамаға сәйкес салмақ матрицасының жолы). s-ші қадамда төбелер жиыны мен жолдары анықталған болсын. және -лерге көшу үшін, -де төбесін таңдап аламыз: .

, болсын, мұндағы

s=n-1 қадамда жолын аламыз, онда шамасы төбесінен төбесіне дейінгі өлшенген ара қашықтыққа тең.

Берілген граф үшін I Дейкстра алгоритмі:

1 қадам. А- бастамасы , , .

2 қадам. -де ^ таңбасымен белгіленген элементтердің ішінен (яғни бастамасына сәйкес келетін элементтен басқалары) ең кішісін іздейміз және оның астын сызып қоямыз. -ден асты сызылған элементке сәйкес келетін төбені алып тастаймыз (бұл С төбесі).

саламыз. -ні анықтау үшін қосымша жазу жүргіземіз: W матрицасынан С-ға сәйкес жолды жазамыз, сосын оның барлық элементтеріне (бірінші мен үшіншіден басқа) таңбаланған 1 санын қосамыз. . Қосу келесі ережемен жүргізіледі , , . Алынған сандарды -мен салыстырамыз және -де сәйкес орындарға ең аздарын қоямыз:.

3 қадам.

, , .

4 қадам.

, , .

5 қадам. , , .

n=6, n-1=5, яғни бұл соңғы қадам. түріне қарап, А төбесінен қалған төбелерге дейінгі салмақты ара қашықтықтарды білуге болады , , , , , ;

г) саны цикломатикалық сан деп аталынады (немесе цикломатикалық ранг), мұндағы m – қабырғалар саны, n – төбелер саны, k – байланысты компоненталар саны. Ол діңгек алу үшін қанша қабырға алып тастау керектігін анықтайды. саны коранг деп аталынады және діңгектегі қабырғалар санын анықтайды. Біздің жағдайда , ;

д) ең аз салмақты ағаш (діңгек) салу үшін Краскаль алгоритмін қолданамыз: G(V,E) графы берілген.

1. V төбелер жиынынан және ең аз салмақты қабырғасынан тұратын графын саламыз (яғни , мұндағы ).

2. Егер графы салынған болса және , онда қабырғалар жиынына -ға енбейтін қабырғалардың ішінде ең аз салмақты қабырғасын қоса отырып графын саламыз ( яғни , мұндағы ). 3. болғанда алгоритм аяқталады және - ең аз салмақты діңгек, оның салмағы қабырғаларының салмақтарының қосындысына тең.

Берілген граф үшін Краскаль алгоритмі: .

1) , ;

2) , ;

3) , ;

4) , ;

5) , .

- ең аз салмақты діңгек (6 сурет), оның салмағы 1+3+1+3+2=10. Айта кетелік, ең аз салмақты діңгекті салуды , -ды анықтаумен қатар жүргізу керек. Әрі қарай әрбір қадамда бір қабырғадан қосып отыру керек.

6 Сурет

Әдебиеттер тізімі

1. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.

2. Москинова Г.И. Дискретная математика. Математика для менеджера

в примерах и упражнениях: Учебное пособие. – М.: Логос, 2004. – 240 с.

3. Новиков Ф.А. Дискретная математика для программистов: Учебник

для вузов. 2-е изд. – СПб.: Питер, 2004. – 364 с.: ил. – (Серия «Учебник для вузов»).

4. Андерсон Д. Дискретная математика и комбинаторика.: Пер. с англ. –

М.: Издатель- ский дом «Вильямс», 2004. – 960 с.: ил. – Парал. тит. англ.

5. Шапорев С.Д. Дискретная математика. Курс лекций и практических

занятий. – СПб.: БХВ-Петербург, 2006.

6. Яблонский С.В. Введение в дискретную математику. – М. «Высшая

школа», 2001.

Мазмұны

1 Есептік-графикалық жұмыс 3. Графтар

1.1 Теориялық сұрақтар

1.2 Есептік тапсырмалар

1.3 Типтік варианттың шешуі

Әдебиеттер тізімі