10) Отношения на множествах и графы

Рефлексивному отношению - должна соответствовать на графе петля в вершине.

Если это отношение соблюдается во всех вершинах x ∈ X, то соответствующий граф должен иметь петлю в каждой своей вершине.

Антирефлексивное отношение – ни одной петли

Симметрическому отношению на множестве соответствует граф с неориентированными ребрами.

В случае антисимметрического отношения на графе невозможно присутствие двух дуг на графе, то есть существование неориентированного ребра. Антисимметрическое отношение антирефлексивно.

Свойство тождественности, соответствует графу с антисимметричным отношением на множестве вершин (ориентированному графу) и добавлением петли в каждой вершине. Этот граф не должен иметь контуров.

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

Отношение полноты, определено на множестве вершин полного ориентированного графа.

Нулевое отношение определено на множестве вершин ноль-графа.

Универсальное отношение определено на множестве вершин полного неориентированного графа с петлями.

Дополнительное отношение определено на множестве вершин дополнительного графа к графу.

Эквивалентность, представляет собой совокупность компонент

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

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

Отношение порядка: граф имеет петли во всех вершинах, для каждого пути должен иметь замыкающую дугу, не должен иметь контуров и все ребра должны быть ориентированы. Если удалить все петли получится граф строгого порядка

Отношение полного порядка соответствует каждой компоненте связности графа, на множестве вершин которого определено отношение порядка.

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

Матрица смежности — квадратная матрица, в которой каждый элемент принимает значения 1 или 0.

1 — путь идет из одной точки в другую

0 — вершины не смежны

Матрица инцидентности для ребер графа (для неориентированного графа)

1 — вершина инцидентна ребру.

0 — вершина не инцидентна ребру.

Инцидентность — если ребро проходит через точку

Матрица инцидентности для дуг графа (для ориентированного графа)

1 — вершина инцидентна ребру и является его началом

0 — вершина не инцидентна ребру -1 — вершина инцидентна ребру и является его концом

12. Сумма и пересечение графов

Сумма графов. Тут и объяснять, по сути, ничего не нужно. Дано два графа — их сумма это они оба, объединенные в одном.

Пересечение графа — только те линии, что есть и в первом и во втором графе

13. Композиция и транзитивное замыкание графов

Пусть имеется нетранзитивный ориентированный граф. Его можно сделать транзитивным, добавив дуги, с целью получения замыкающей дуги для каждой из его последовательных дуг. Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин u ,v и w из того, что из u в вершину v ведет ребро и из вершины v в вершину w ведет ребро, следует, что из вершины u в вершину w ведет ребро.