Определение. Графы м бинарные отношения

Графы м бинарные отношения

Любой граф возможно с петлями, но без кратных ребер задает бинарное отношение Е на множестве вершин V и обратно. А. именно, пара элементов (a, b) принадлежит отношению Е () тогда и только тогда, когда в графе G есть ребро (дуга) (a, b).

Полный граф соответствует универсальному отношению (E=VxV). Неориентированный граф – симметричному отношению.

Дополнение графа есть дополнение отношения.

Изменение направлений всех дуг ориентированного графа соответствует обратному отношению.

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

Связность графа

Неориентированный граф

Определение

Неориентированный граф называется связным, если любые две вершины графа соединены цепью.

Определение

Компонента связности неориентированного графа – это максимально связный подграф (максимальный по числу вершин).

Как мы уже говорили в неориентированном графе две вершины, соединенные цепью, связаны отношением достижимости. Если граф неориентированный, то отношение достижимости является отношением эквивалентности. Покажем это. Отношение достижимости:

1) рефлексивно.

Каждая вершина достижима сама из себя.

2) симметрично

Если существует цепь, соединяющая вершину v с вершиной w, то, естественно, существует цепь, соединяющая вершину w с вершиной v.

3) транзитивно

Если существует цепь, соединяющая вершину v с вершиной w, и цепь, соединяющая вершину w с вершиной u, то, существует цепь, соединяющая вершину v с вершиной u.

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

Пример

1 2 5 6

3 4 7

Этот граф не является связным. Он состоит из трех компонент связности. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости:

{1, 2, 3, 4}, {5, 6}, {7}