Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
часть I Искусственный интеллект.doc
Скачиваний:
5
Добавлен:
01.05.2025
Размер:
6 Мб
Скачать
☆
    1. Элементы теории графов

Граф – совокупность двух множеств V – точек и Е – линий между элементами которых определено отношение инцидентности (связности). Причем каждый элемент е, принадлежащий Е инцидентен ровно двум элементам V` и V``, принадлежащих V.

Элементы множества V называются вершинами графа G; Элементы множества Е называются ребрами графа G.

В некоторых случаях каждому ребру приписывают направление от одной из инцидентных вершин ко второй.

Направленные ребра называют дугами, а содержащий граф - ориентированным.

4.1.1. Способы задания графов.

1. Графический

а) Рис.16. Ориентированный граф

б) Рис.17. Пустой граф

в) Кратные ребра – различные ребра, инцидентны одной и той же паре вершин. Мультиграф – граф, содержащий кратные ребра.

Рис.18. Мультиграф

г) Петля – ребро, соединяющее вершину саму с собой.

Рис.19. Петля

д) Фрагмент бесконечного графа.

Рис.20. Фрагмент бесконечного графа

2. С помощью матрицы инцидентности.

Рис.21. Неориентированный граф Рис.22. Ориентированный граф

Для неориентированного графа.

Пусть V1, V2,…Vn – вершины графа G. Отношение инцидентности задается матрицей / ξij /, имеющая m – строк и n – столбцов.

Столбцы соответствуют вершинам графа, а строки – ребрам.

Если ребро еi инцидентно вершине Vj, то ξij = 1.

В противном случае ξij = 0.

Для ориентированного графа.

Если вершина Vj – начало ребра еi, то ξij = -1. Если вершина Vj – конец ребра еi, то ξij = 1.

Если - еi петля, а Vj - инцидентная вершина, то ξij = α, где α – любое число отличное от 0, 1 и -1.

Во всех остальных случаях ξij = 0.

Для неориентированного графа: Для ориентированного графа:

Таблица 15 Матрица инцидентности Таблица16 Матрица инцидентности

неориентированного графа ориентированного графа

3. С помощью списка ребер.

Каждая строка списка соответствует ребру, в ней записаны номера вершин, инцидентных этому ребру. Для неориентированного графа порядок вершин произволен; Для ориентированного графа – первым стоит номер начала ребра, а вторым – номер его конца.

Для неориентированного графа: Для ориентированного графа:

Таблица 17 Список рёбер Таблица 18 Список рёбер

для неориентированного графа для ориентированного графа

4. С помощью матрицы смежности.

Матрица смежности – квадратная матрица ||δij|| строкам и столбцам которой соответствуют вершины графа.

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

Для ориентированного графа δij равна количеству ребер с началом в i – вершине и концом в j – вершине.

Для неориентированного графа: Для ориентированного графа:

Таблица 19 Матрица смежности Таблица 20 Матрица смежности

для неориентированного графа для ориентированного графа

Матрица для неориентированного графа симметрична относительно главной диагонали.

Пусть G – неориентированный граф. Маршрутом G называется такая конечная или бесконечная последовательность ребер (е1, е2,…,еn), что каждые два соседних ребра

еi-1, еi имеют общую инцидентную вершину.

Пусть маршрут М, состоящий из (е1, е2,…,еn) ребер, имеет начало V0 и конец Vn.

Если V0 =Vn (начало совпадает с вершиной), то такой маршрут называется циклическим.

Маршрут М называется цепью, если каждое ребро встречается в нем не более 1 раза.

Циклический маршрут называется циклом, если он является цепью.

ПРИМЕР:

Рис.23. Неориентированный граф

Маршрут: М = {VI, IV, III, II, VI, I}

Циклический маршрут: M = {I, VI, IV, III, II, VI, I}

Цепь: M = {IV, III, II, VI, I}

Цикл: M = {IV, III, II}

Вершины V` и V``, принадлежащие графу G, называются связанными, если существует маршрут М с началом V` и концом V``.

Граф G называется связанным, если все его вершины связаны между собой.

Рис.24. Связанный граф

Несвязанный граф:

Рис.25. Несвязанный граф

Неориентированным деревом называется связанный неориентированный граф без циклов.

Рис.26. Дерево

Несвязанный, неориентированный граф без циклов называется лесом.

Рис.27. Лес