Материал: 5540
v1 |
|
|
v5 |
|
v2 |
|
v4 |
v2 |
v1 |
v2 |
|
|
|||
|
|
v4 |
|
|
|||
v4 |
v3 |
v4 |
|
|
v5 |
|
|
|
|
v1 |
v1 |
v5 |
|||
|
|
|
v3 |
v3 |
|||
|
|
|
|
|
|
||
G1 |
|
G2 |
|
G1 |
|
G2 |
|
|
|
5) |
|
|
6) |
|
|
Рисунок 5.11 – Задание графов G1 и G2 (1 – 6 – варианты)
Задача 5.8. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом G. Найдите число степеней входа и выхода этого графа, дайте ему характеристику (рисунок 5.12).
В |
В |
В |
А |
|
С |
А |
С |
|
А |
С |
|
1) |
|
|
2) |
|
|
3) |
|
В |
|
|
В |
|
|
В |
А |
С |
|
А |
|
С |
А |
С |
|
|
|
|
|
|||
|
4) |
|
|
5) |
|
|
6) |
Рисунок 5.12 – Задание графа G (1 – 6 – варианты)
Задача 5.9. Орграф задан матрицей смежности. Постройте его рисунок (схему, диаграмму), определите степени вершин графа и найдите маршрут длины 5.
116
|
0 |
1 |
1 |
0 |
0 |
1 |
|
|
0 |
|
1 |
1 |
0 |
0 |
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
0 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
|
0 |
0 |
1 |
0 |
0 |
|
|||
1) G |
0 1 0 0 0 0 |
; |
2) G |
0 0 0 0 1 1 |
; |
||||||||||||||
|
0 |
0 |
1 |
0 |
0 |
0 |
|
|
1 |
|
0 |
0 |
0 |
0 |
1 |
|
|||
|
1 |
1 |
0 |
0 |
0 |
1 |
|
|
0 |
|
0 |
|
1 |
1 |
0 |
0 |
|
||
|
1 |
1 |
0 |
0 |
1 |
0 |
|
|
0 |
|
1 |
|
1 |
0 |
0 |
0 |
|
||
|
0 |
|
1 |
1 |
0 |
0 |
0 |
|
|
0 |
|
1 |
0 |
|
0 |
1 |
0 |
|
|
|
0 |
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
|
0 |
0 |
|
0 |
0 |
1 |
|
|
3) G |
1 |
0 0 0 0 1 |
; |
4) G |
1 |
0 0 1 0 0 ; |
|
||||||||||||
|
1 |
|
1 |
1 |
0 |
0 |
1 |
|
|
0 |
|
1 |
1 |
|
0 |
0 |
0 |
|
|
|
0 |
|
0 |
0 |
0 |
0 |
1 |
|
|
0 |
|
1 |
|
1 |
|
0 |
0 |
1 |
|
|
1 |
|
0 |
1 |
1 |
0 |
0 |
|
|
1 |
|
1 |
|
0 |
|
0 |
0 |
0 |
|
|
0 |
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
|
1 |
|
0 |
|
0 |
1 |
0 |
|
|
0 |
|
0 |
0 |
1 |
1 |
0 |
|
|
0 |
|
0 |
|
1 |
|
1 |
0 |
1 |
|
5) G |
0 |
0 0 0 0 1 ; |
6) G |
1 |
0 0 0 1 0 . |
|
|||||||||||||
|
1 |
|
0 |
1 |
0 |
0 |
0 |
|
|
1 |
|
0 |
|
0 |
|
0 |
1 |
0 |
|
|
0 |
|
0 |
1 |
1 |
0 |
0 |
|
|
0 |
|
1 |
1 |
0 |
0 |
1 |
|
||
|
0 |
|
1 |
1 |
0 |
0 |
0 |
|
|
0 |
|
1 |
1 |
0 |
0 |
0 |
|
||
Задача 5.10. Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта М в пункт N, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут (рисунок 5.13)?
117
А
С
В
M
N
E
F
D
K
Рисунок 5.13 – Граф путешествия по историческим местам
Задача 5.11. Ориентированный граф G с множеством вершин V =
{1, 2, 3, 4, 5, 6, 7} задан списком дуг Е.
1.Постройте граф G.
2.Постройте матрицу инцидентности графа G.
3.Постройте матрицу смежности G.
4.Задайте соответствующий неориентированный граф матрицей смежности.
5. Укажите степени вершин полученных графов, найдите цикломатическое число графа G:
а) Е = {(1, 2), (2, 3), (4, 3), (4, 5), (6, 5), (7, 6), (7, 1), (7, 7), (7, 2), (6, 4), (4, 4), (2, 7), (6, 4), (5, 3)};
б) Е = {(1, 4), (2, 1), (4, 3), (4, 5), (2, 6), (2, 6), (7, 1), (7, 6), (3, 2), (5, 4), (3, 4), (2, 2), (6, 2), (5, 5)};
в) Е = {(1, 5), (2, 3), (2, 3), (4, 5), (4, 6), (5, 6), (5, 1), (6, 6), (3, 2), (5, 4), (6, 4), (7, 2), (6, 7), (7, 5)};
г) Е = {(1, 1), (2, 2), (2, 3), (3, 5), (4, 6), (4, 6), (5, 1), (5, 6), (5, 2), (6, 4), (7, 4), (7, 2), (7, 2), (7, 5)};
д) Е = {(1, 1), (1, 3), (1, 3), (2, 5), (2, 6), (3, 6), (3, 1), (3, 6), (3, 7), (4, 4), (4, 6), (5, 2), (6, 3), (6, 5)};
е) Е = {(1, 3), (2, 3), (2, 3), (3, 5), (3, 6), (2, 7), (4, 1), (4, 6), (4, 2), (6, 4), (6, 4), (7, 2), (6, 6), (7, 6)}.
118
Библиографический список
1.Джеймс А. Дискретная математика и комбинаторика : пер. с англ. – М. : Вильямс, 2004.
2.Акимов О. Е. Дискретная математика. Логика, группы, графы / О. Е. Акимов. – М. : Лаборатория базовых знаний, 2003.
3.Виленкин Н. Я. Факультативный курс. Избранные вопросы
математики / Н. Я. Виленкин, Р. С. Гутер, А. Н. Земляков, И. Л. Никольская. – М. : Просвещение, 1978.
4.Гетманов А. Д. Логика для юристов : учеб. пособие / А. Д. Гетманов. – М. : Омега-Л, 2007.
5.Гудинг Д., Леннокс Дж. Мировоззрение : человек в поисках истины и реальности / Д. Гудинг, Дж. Леннокс. – Ярославль : Норд, 2004.
Т.2. Кн. 1.
6.Гончаров Г. А. Элементы дискретной математики / Г. А. Гончаров. – М. : ФОРУМ : ИНФА-М, 2003.
7.Григулецкий В. Г., Ященко З. В. Высшая математика для экономистов : учеб. пособие для вузов / В. Г. Григулецкий, З. В. Ященко. – Ростов н/Д : Феникс, 2004.
8.Жоль К. К. Логика в лицах и символах / К. К. Жоль. – М. : Педагогика-Пресс, 1993.
9.Игошин В. И. Математическая логика и теория алгоритмов : учеб.
|
пособие для |
студентов высших учебных заведений. |
2-е изд. |
/ |
|
|
В. И. Игошин. – М. : Академия, 2008. |
|
|
||
10. |
Москинова |
Г. |
И. Дискретная математика. Математика для |
||
|
менеджеров |
в |
примерах и упражнениях : учеб. |
пособие |
/ |
|
Г. И. Москинова. – М. : Логос, 2000. |
|
|
||
11. |
Никитин А. |
А. |
Математика : учебник для десятых-одиннадцатых |
||
|
классов средних общеобразовательных учебных заведений. Часть I / |
||||
А. А. Никитин, В. С. Белоносов, М. П. Вишневский, В. В. Войтишек, Т. И. Зеленяк, А. А. Мальцев, А. С. Марковичев, Ю. В. Михеев,
119
А. И. Саханенко, Д. М. Смирнов. – Новосибирск : Изд-во ИДМИ, 2000.
12.Пономарёв В. Ф. Основы дискретной математики : учеб. пособие / В. Ф. Пономарёв. – Калининград : КГТУ, 1997.
13.Пономарёв В. Ф. Дискретная математика для информатиковэкономистов : учеб. пособие / В. Ф. Пономарёв. – Калининград :
КГТУ, 2002.
14.Спирина М. С. Дискретная математика : учебник для студентов учреждений среднего профессионального образования / М. С. Спирина. – М. : Академия, 2004.
15.Столл Р. Множества. Логика. Аксиоматические теории / Р. Столл. – М. : Просвещение, 1968.
16.Чалых Е. В. Математическая логика. Часть 1. Алгебра высказываний : учеб. пособие. – Биробиджан : БГПИ, 2003.
120