Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
матем 3.docx
Скачиваний:
21
Добавлен:
01.05.2015
Размер:
285.94 Кб
Скачать

АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ

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

Методические указания и задания

к выполнению расчетно-графических работ

(для студентов очной формы обучения специальности

050704 – Вычислительная техника и программное обеспечение)

Часть 3

СОСТАВИТЕЛИ: Л.Н. Астраханцева, Л.Н.Ким, М.Ж.Байсалова.

Алгебра и геометрия. Методические указания и задания к

выполнению расчетно-графической работы для студентов очной

формы обучения специальности 050704 – Вычислительная

техника и программное обеспечение.

Методические указания и задания к расчетно-графической работе содержат типовой расчет №3 дисциплины «Алгебра и геометрия» для студентов очной формы обучения специальности 050704 – Вычислительная техника и программное обеспечение. Приведены основные теоретические вопросы программы. Дано решение типового варианта.

1 Типовой расчёт 3. Графы

1.1 Теоретические вопросы

1 Основные понятия и определения теории графов (н-граф и орграф, мультиграф, инцидентность, смежность, степени вершин).

2 Способы задания графов (пара множеств , рисунок, матрица инцидентности, список ребер (дуг)).

3 Связь между графами и бинарными отношениями. Изоморфизм графов. Подграфы. Операции над графами.

4 Маршруты, цепи, пути, циклы, контуры. Связность, сильная связность, компоненты связности.

5 Определение связных и сильно связных компонент. Матрица достижимости.

6 Исследование маршрутов графа (определение маршрутов фиксированной длины и их количество).

7 Расстояния в графах (эксцентриситет, диаметр, радиус, центр)

8 Взвешенные графы. Матрица весов. Взвешенное расстояние. Нахождение кратчайших маршрутов (алгоритм Дейкстры).

9 Деревья, лес. Корневые деревья. Остов графа. Цикломатическое число. Число остовых деревьев графа (теорема Кирхгофа).

10 Определение остового дерева минимального веса (алгоритмы Краскаля и Прима).

1.2 Расчётные задания

1-4 Граф G=(V,E) задан множеством его вершин V={1,2,3,4} и дуг E={a,b,c,d,e,f,k,l}, причём дуги определены парами начальных и конечных вершин.

Найти: 1. Задать этот граф:

а) графически;

б) матрицей инцидентности;

в) матрицей смежности;

г) списком дуг.

2. Найти степени входа и выхода вершин графа и степени вершин соответствующего н-графа. Записать равенства, определяющие связь степеней вершин и числа рёбер графа. 3. Определить соответствующее графу бинарное отношение. Какими свойствами (рефлексивность, симметричность, и т.д.) обладает данное отношение? 4. Привести пример двух достижимых и двух недостижимых вершин (если они имеются). Будет ли данный граф связным, сильно связным? Найти его компоненты связности.

Т а б л и ц а 1

E

E

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.29

1.30

5 Для данного графа G найти:

а) матрицу расстояний;

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

в) центральные и периферийные вершины.

Т а б л и ц а 2

G

G

G

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



2

3 5 2 7 1 2 4

D 4

6

А 2 F 4 Е A C

6

6.3 6.4

В 2 D 2 Е D 1 E

2

A 1 3 5

5 3 2 4 1 2 F

4

3

А 4 C 3 F B 6 C

6.5 6.6

5 E B 8 D

B

4 2 3 4

2 D 3 A 7 1 F

6

A 5

3 C 6 8

C 6 E

6.7 6.8

6.9 6.10

B 4 C B

6

3 3 4 1 2

A

11 8 2

C 5

D 4 F

A 5 E 7 3

E

4

D

6.11 6.12

B 4 C B 8

3 C

A 5 7

3 4 2 15 3

1

9 4 D

E

D

A 8 F 7 E 6

6.13 6.14

B B

9

2 C 3 4

5 2

3 1 5

A 1 D A C

F

11 4 3 6



E E 2 D

6.15 6.16 B

5

B 3

4 1 C 6

3 C 4 2

2 D A 1 D

4 2

A 5 E

3 6

5



F 2 E

6.17 6.18

A 4 B 6 C A 8 D



2

3 5 2 7 3 2 4

C 4

6

F 2 E 4 D E B

6

6.19 6.20

A 2 C 2 D C 1 D

2

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

A

4 2 3 4

2 C 3 F 7 1 E

6

E 5

3 B 6 8

B 6 D

6.23 6. 24

A 4 B A

6

3 3 4 1 2

F

11 8 2

B 5

C 4 E

E 5 D 7 3

D

4

C

6.25 6. 26

A 4 B A 8

3 B

E 5 7

3 4 2 15 3

1

9 D 4 C

C

F 8 E 7 D 6

6.27 A 6.28 A

9

2 B 3 4

5 2

3 1 5

E 1 C E B

F

11 4 3 6



D D 2 C

6.29 6.30 A

5

A 3

4 1 B 6

3 B 4 2

2 C Е 1 C

4 2

F 5 D

3 6

5



E 2 D

1.3 Решение типового варианта

1-4 Граф G=(V,E) задан множеством его вершин V={1,2,3,4,5} и дуг E={a,b,c,d,e,f}=. Найти:

1. Задать этот граф:

а) графически;

б) матрицей инцидентности;

в) матрицей смежности;

г) списком дуг.

2. Найти степени входа и выхода вершин графа и степени вершин соответствующего н-графа. Записать равенства, определяющие связь степеней вершин и числа рёбер графа. 3. Определить соответствующее графу бинарное отношение. Какими свойствами (рефлексивность, симметричность, и т.д.) обладает данное отношение? 4. Привести пример двух достижимых и двух недостижимых вершин (если они имеются). Будет ли данный граф связным, сильно связным? Найти его компоненты связности.

Решение:

1. а)

Рисунок 1

б) матрица инцидентности для орграфа, имеющего m вершин и n рёбер,

имеет вид , где . Таким образом, ;

в) матрица смежности для орграфа, имеющего m вершин, имеет вид , где . Итак,

;

г) список дуг будет

дуги

вершины

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. Вершина v достижима из вершины u, если существует путь с началом в u и концом в v. Таким образом, в нашем графе вершины 2 и 3 взаимно достижимы; вершины 3, 5, 6 достижимы из вершины 1; вершина 1 не достижима ни из одной вершины.

Так как соответствующий н-граф связный (т.е. любые его две вершины взаимно достижимы), то данный орграф также будет связным, но не сильно связным, поскольку в этом орграфе не любые две вершины взаимно достижимы. Для определения компонент сильной связности строят три матрицы:

а) матрицу достижимости , где

;

б) матрицу контрдостижимости ;

в) матрицу , где . Единицы первой строки матрицы S соответствуют вершинам, входящим в первую компоненту сильной связности . Мысленно вычёркиваем строки и столбцы, на которых стоят элементы, соответствующие этим вершинам. В оставшейся матрице единицы первой строки соответствуют вершинам, входящим во вторую сильно связную компоненту и т.д. - число сильно связных компонент графа. Если =1, то орграф сильно связный, если >1, то не сильно связный. Множества вершин сильно связных компонент образуют разбиение множества вершин графа: .

Построим вышеуказанные матрицы для данного графа. - матрица достижимости.

- матрица контрдостижимости.

. В первой строке матрицы S одна единица, соответствующая вершине 1, таким образом, первая компонента сильной связности . После вычёркивания первой строки и первого столбца в оставшейся первой строке две единицы соответствуют вершинам 2 и 3, значит, - вторая сильно связная компонента. Рассуждая аналогично, получим ещё три сильно связные компоненты , , . Число сильно связных компонент =5. Множество вершин графа имеет разбиение .

5 Для данного графа G

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 из вершины А;

в) матрицу весов;

г) кратчайший маршрут из вершины А к остальным вершинам;

д) цикломатическое число;

е) дерево минимального веса.

Решение:

а) - матрица смежности;

б) чтобы найти число маршрутов длины два из каждой вершины, вычислим матрицу

:.

Так как требуется найти все маршруты длины два только из вершины А, то рассмотрим только первую строку матрицы : , следовательно, из вершины А в А есть 2 маршрута длины два; из А в D 2 маршрута; , значит из А в Е есть 1 маршрут длины два.

Чтобы определить, через какие рёбра проходит каждый маршрут, построим вспомогательную матрицу , построенную из А заменой каждого элемента на соответствующие рёбра.

Рисунок 5

Найдём =. Так как , то из А в А есть 2 маршрута длины два: ААА и ААА; так как. , то из А в D есть 2 маршрута длины два: АВD и АСD; т.к. , то из А в Е есть 1 маршрут длины два: АВЕ;

в) - матрица весов, где - вес дуги , если она существует, если не существует, то соответствующий вес обозначается 0 или в зависимости от приложений (- если вершины не смежные). Для данного графа матрица весов имеет вид ;

г) кратчайший маршрут из вершины А к остальным вершинам будем находить по алгоритму Дейкстры 1: дан взвешенный граф G(V,E), имеющий n вершин, - его матрица весов(). Требуется найти взвешенное расстояние от вершины (она называется источником) до некоторой другой вершины. Заметим, что этот алгоритм позволяет сразу определить расстояния от источника до остальных вершин. На первом шаге обозначим , , где ( т.е. - это строка матрицы весов, соответствующая источнику). Пусть на s- ом шаге уже определены множества вершин и строка , чтобы перейти к и , выберем в вершину ,такую, что и положим , , где . На шаге s=n-1 получим строку , в которой равны взвешенным расстояниям от вершины до вершин .

Алгоритм Дейкстры 1 для данного графа:

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.

Содержание

Соседние файлы в предмете Математика