Основные положения дискретной математики (стр. 10 из 11)

· Линии, изображающие ребра графа могут пересекаться, но точки пересечения не являются вершинами:

· Граф может быть бесконечным:

Каждому неориентированному графу можно поставить в соответствие орграф с тем же множеством вершин заменив лишь ребра неориентированного графа на направленные дуги орграфа. Такое соответствие называется каноническим.

7.2 Матрица инцидентности и списки ребер

Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф конечен для описания его вершин и ребер достаточно их занумеровать. Отношение инцидентности определяют матрицей

_ij, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки – ребрам графа. Если ребро е_iинцидентно вершине v_j, то

_ij= 1, в противном случае

_ij= 0. Это матрица инцидентности для неориентированного графа.

Пример (Задание №9)

Обозначим вершины римскими цифрами, а ребра – арабскими. Матрица инцидентности для данного графа выглядит следующим образом:

I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

В матрице инцидентности орграфа

_ij= -1, если вершина v_j – начало дуги a_i;

_ij= 1, если v_j – конец дуги a_i; если a_i– петля, а v_j – инцидентная ей вершина, то

_ij= а, где а – любое число отличное от 0, 1, -1. В остальных случаях

_ij= 0.

Пример (Задание №10): построим ориентированный граф и матрицу инцидентности для нее:

Из матрицы инцидентности мы видим, что в каждой строке есть только два элемента (или один, если ребро является петлей) отличных от 0. Поэтому такой способ задания графа посчитали неэкономичным. Отношение инцидентности можно задать так же с помощью списков ребер графа. Каждая строка этого списка соответствует ребру, в ней записывают номера вершин, инцидентных ему. Для неориентированного графа порядок вершин в строке произволен, а для орграфа первым записывают номер вершины начала дуги, а вторым – номер вершины конца дуги.

Составим списки ребер для данных графов:

Таб. 8 Списки ребер неориентированного графа

Таб. 9 Списки ребер орграфа

Ребра	Вершины	Ребра	Вершины
1	I, II	1	I, II
2	I, III	2	I, III
3	II, IV	3	II, IV
4	I, V	4	III, V
5	II, VI	5	III, IV
6	III, IV	6	III, VII
7	III, V	7	VI, VII
8	IV, VI
9	V, VII
10	VI, VII

Каждая строка списка ребер соответствует строке матрицы с тем же номером ребра.

7.3 Матрица смежности графа

Матрица смежности – это квадратная матрица

_ij, строкам и столбцам которой соответствуют вершины графа. Для неориентированного графа

_ij ровно количеству ребер, инцидентных i-ой и j-ой вершинам. Для орграфа

_ij ровно количеству ребер с началом в i-ой вершине и концом j-ой вершине. Таким образом матрица смежности неориентированного графа симметрична, а орграфа – необязательно.

Пример: построим матрицы смежности для графов, рассмотренных ранее.

I	II	III	IV	V	VI	VII	I	II	III	IV	V	VI	VII
I	0	1	1	0	1	0	0	I	0	1	1	0	0	0	0
II	1	0	0	1	0	1	0	II	0	0	0	1	0	0	0
III	1	0	0	1	1	0	0	III	0	0	0	0	1	1	1
IV	0	1	1	0	0	1	0	IV	0	0	0	0	0	0	0
V	1	0	1	0	0	0	1	V	0	0	0	0	0	0	0
VI	0	1	0	1	0	0	1	VI	0	0	0	0	0	0	0
VII	0	0	0	0	1	1	0	VII	0	0	0	0	0	0	1

Матрица смежности неориентированного графа

Матрица смежности орграфа.

7.4 Операции над членами графов

1. Дополнение

Н части Н определяется множеством всех ребер графа G, не принадлежащих Н.

2. Объединение Н₁

Н₂определяется:

;

3. Пересечение Н₁

Н₂ частей Н₁ и Н₂ графа G определяется:

;

8 ОСНОВНЫЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Контрольная работа в обязательном порядке должна содержать титульный лист (см. приложение I), условие задачи и подробное описание ее решения. Описание решения должно содержать: используемые при решении формулы и свойства; их название (если таковое имеется); методы или способы решения задачи; результаты вычислений; выводы.

9. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ

1. Множества и подмножества. Основные понятия. Графическое представление множеств и операций над ними.

2. Множества и подмножества. Основные понятия. Свойства операций над множествами. Тождества. Порядок доказательства тождеств.

3. Отношение на множествах. Декартово произведение.

4. Отношения на множествах. Одноместные, бинарные, n- местные отношения.

5. Отношения на множествах. Свойства отношений.

6. Функция как отношение на множествах. Отношение порядка. Отношение эквивалентности.

7. Математическое моделирование. Понятие модели. Этапы приведения к модели. Способы моделирования.

8. Алгебраические модели. Общие понятия. Алгебраические модели с одной определяющей операцией.

9. Алгебраические модели. Общие понятия. Алгебраические модели с двумя определяющими операциями.

10. Алгебраические модели. Общие понятия. Алгебраические модели, содержащие более одного класса математических объектов.

11. Теория кодирования. Общие понятия. Показать построение трехзначного двоичного кода на примере куба. Описать все возможные ситуации.

12. Теория кодирования. Общие понятия. Кодовые расстояния. Методы обнаружения ошибок.

13. Теория кодирования. Общие понятия. Групповые коды.

14. Линейная алгебра. Общие понятия. Линейные подпространства.

15. Реляционная алгебра. Понятия домена, кортежа. Операции выбора, проекции, объединения.

16. Математическая логика. Общие понятия алгебры логики. Функции алгебры логики и их таблицы истинности.

17. Булева алгебра. Общие понятия. Свойства операций и элементов булевой алгебры.

18. Булева алгебра. Дизъюнктивные нормальные формы. Совершенные дизъюнктивные нормальные формы.

19. Булева алгебра. Алгоритм преобразования формулы в совершенную дизъюнктивную нормальную форму.

20. Булева алгебра. Конъюнктивные нормальные формы. Совершенные конъюнктивные нормальные формы.

21. Исчисление высказываний. Общие понятия. Понятие равносильной формулы.

22. Исчисление высказываний. Равносильности. Способы доказательства равносильностей.

23. Исчисление высказываний. Правила равносильных преобразований. Тавтологии. Основные понятия.

24. Исчисление высказываний. Тавтологии. Методы доказательства тождественной истинности. высказываний.

25. Аксиоматическая система в исчислении. Основные понятия. Выводимые формулы. Правила вывода.

26. Булевы функции. Полнота системы булевых функций. Теорема Поста.

27. Булевы функции. Замкнутые классы. Контактные схемы.

28. Логика предикатов. Основные понятия. Операции над предикатами.

29. Логика предикатов. Основные понятия. Кванторы. Исчисление предикатов.

I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

I	II	III	IV	V	VI	VII	I	II	III	IV	V	VI	VII
I	0	1	1	0	1	0	0	I	0	1	1	0	0	0	0
II	1	0	0	1	0	1	0	II	0	0	0	1	0	0	0
III	1	0	0	1	1	0	0	III	0	0	0	0	1	1	1
IV	0	1	1	0	0	1	0	IV	0	0	0	0	0	0	0
V	1	0	1	0	0	0	1	V	0	0	0	0	0	0	0
VI	0	1	0	1	0	0	1	VI	0	0	0	0	0	0	0
VII	0	0	0	0	1	1	0	VII	0	0	0	0	0	0	1

I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

I	II	III	IV	V	VI	VII	I	II	III	IV	V	VI	VII
I	0	1	1	0	1	0	0	I	0	1	1	0	0	0	0
II	1	0	0	1	0	1	0	II	0	0	0	1	0	0	0
III	1	0	0	1	1	0	0	III	0	0	0	0	1	1	1
IV	0	1	1	0	0	1	0	IV	0	0	0	0	0	0	0
V	1	0	1	0	0	0	1	V	0	0	0	0	0	0	0
VI	0	1	0	1	0	0	1	VI	0	0	0	0	0	0	0
VII	0	0	0	0	1	1	0	VII	0	0	0	0	0	0	1

I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

I	II	III	IV	V	VI	VII	I	II	III	IV	V	VI	VII
I	0	1	1	0	1	0	0	I	0	1	1	0	0	0	0
II	1	0	0	1	0	1	0	II	0	0	0	1	0	0	0
III	1	0	0	1	1	0	0	III	0	0	0	0	1	1	1
IV	0	1	1	0	0	1	0	IV	0	0	0	0	0	0	0
V	1	0	1	0	0	0	1	V	0	0	0	0	0	0	0
VI	0	1	0	1	0	0	1	VI	0	0	0	0	0	0	0
VII	0	0	0	0	1	1	0	VII	0	0	0	0	0	0	1