Распознавание свойств графов. Операции над графами.

1. Граф G=(V, E) представляет собой конечное множество вершин V = и некоторое множество E неупорядоченных пар вершин, называемых ребрами. Число элементов множеств V и E будем обозначать соответственно через n и m. В дальнейшем для удобства будем предполагать, что вершины графа перенумерованы и имя вершины совпадает с её номером, т.е. V={1, 2, …, n}.

Граф, имеющий конечное множество вершин называют конечным.

Вершины, соединённые ребром, называются смежными. Рёбра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными.

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

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

Два ребра также называют смежными, если они различны и имеют общую вершину.

Изучаются также ориентированные графы. Ориентированный граф (или орграф) – это пара G = (V, A), где V – множество вершин, A – множество упорядоченных пар элементов множества V (ориентированных ребер), которые называются дугами.

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

Граф, не имеющий ребер, называется пустым.

Рис. 3. Полный граф.

Рис. 4. Пустой граф.

Граф D =(R, W) называется подграфом графа G=(V, E), если и .

Два ребра вида (i, j), (i, j) называются параллельными.

Граф называется простым, если он не имеет петель − ребер вида (i, i) и параллельных ребер. В дальнейшем будем предполагать, что все рассматриваемые графы простые.

Граф G можно задавать матрицей смежности или матрицей инцидентности.

Матрица W размера n n называется матрицей смежности графа G, если W[i, j] =1 тогда и только тогда, когда вершины i и j смежны в графе G, а все остальные элементы матрицы равны 0.

Матрица W размера n m называется матрицей инцидентности графа, если

W[i, j] =

Последовательность S = смежных вершин графа G называют маршрутом. Длина маршрута равна числу рёбер этого маршрута. Например, длина маршрута S равна (k− 1).

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

Цикл графа, содержащий все его ребра, называют эйлеровым. Граф, имеющий эйлеров цикл, также называют эйлеровым.

Простой цикл графа, содержащий все его вершины, называют гамильтоновым. Граф, имеющий гамильтоновым цикл, также называют гамильтоновым.

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

Максимальный по включению связный подграф графа называют его компонентой связности.

Граф G называют деревом, если он связный, но не имеет циклов.

Граф G называют лесом, если каждая компонента связности этого графа является деревом.

Рис.5. Граф типа дерево.

Рис.6. Граф типа лес.

Граф G называют двудольным, если множество его вершин можно разбить на два не пустых подмножества такие, что концевые вершины любого ребра принадлежат различным подмножествам.

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

Опишем некоторые теоремы о свойствах графа, необходимые в дальнейшем.

Теорема 1. Конечный граф G эйлеров тогда и только тогда, когда он связан и степени всех его вершин четны.

Теорема 2. Граф G является двудольным тогда и только тогда, когда n > 1 и любой его цикл имеет четную длину.

Теорема 3. Граф G является двудольным тогда и только тогда, когда для него существует правильная вершинная раскраска в два цвета.

Теорема 4. Граф G является деревом тогда и только тогда, когда он связен и число ребер на единицу меньше числа вершин − выполняется равенство m = n − 1.

2. Над графами можно производить различные операции.

Граф называют дополнением графа G, если он имеет такое же множество вершин и две вершины смежны в тогда и только тогда, когда они не смежны в графе G.

Пусть v – вершина графа G. Тогда операцию построения графа H=G–v назы-

вают удалением вершины v: удаляется вершина v и все инцидентные ей ребра.

Пусть e – ребро графа G. Тогда операцию построения графа H=G–e называют

удалением ребра e: из G удаляется ребро e, а все вершины сохраняются.

Граф H = (R, W) называется объединением графов G =(V , E ) и G = (V , E ), если R = V V и W = E E . В этой ситуации пишут H = G G . Объединение H называется дизъюнктивным, если V ∩ V = Ø. Аналогично определяются объединение и дизъюнктивное объединение любого множества графов, причем в последнем случае никакие два из объединяемых графов не должны иметь общих вершин.

Граф H = (R, W) называется пересечением графов G =(V , E ) и G = (V , E ), если R = V V и W = E E . В этой ситуации пишут H = G G . Аналогично определяются пересечение любого множества графов.

Граф H = (R, W) называется соединением графов G =(V , E ) и G = (V , E ), если он получается из графа G G добавлением всех ребер, соединяющих вершины V и V . В этой ситуации пишут H = G + G .