Подграфы. Операции над графами.

Граф Н называется подграфом графа G, если множество вершин графа Н есть подмножество вершин графа G, и множество ребер графа Н есть подмножество ребер графа G: V_H V_G E_H E_G . Подграф Н называется оставным, если множество вершин V_H=V_G. Говорят, что подграф Н порожден вершинами V_H V_G, где V_H не пустое, если он содержит те и только те дуги(ребра), оба конца которых принадлежат множеству V_H. Очевидно, что если мы имеем матрицу смежности, то чтобы получить матрицу смежности подграфа, порожденного какими-то вершинами, нужно вычеркнуть соответствующие строки и столбцы матрицы исходного графа, тогда на пересечении этих строк и столбцов будет находиться матрица смежности графа, порожденного соответствующими вершинами. Это справедливо и для псевдо- и для мультиграфов.

1. добавление ребра x=(Vi,Vj) в графе G. H=G+x, V_H=V_G, E_H=E_G{x}= E_G{(Vi,Vj)}. Замечание: ребра добавляются только между несмежными вершинами, иначе получим мультиграф.

2. удаление ребра H=G-(Vi,Vj). V_H=V_G, E_H=E_G/{(Vi,Vj)}.

3. удаление вершины H=G-Vi, V_H=V_G/{Vi}, E_H=E_G/{x| x – ребра, инцидентные Vi)}.

4. объединение графов GH, V_HV_G, E_HÈE_G. Обычно полагают, что множества вершин и ребер не пересекаются. В противном случае операция объединения сводится к наложению графов друг на друга.

5. пересечение графов GH. Эта операция полагает, что пересечение вершин – не пустое множество. Тогда получаем граф, у которого пересекаются вершины и пересекаются ребра. V_HV_G, E_HE_G.

6. сложение графов G+H, V_HV_G, E_HÈE_GÈ{x=(u,v)|uV_G, vV_H}, т.е. из каждой вершины первого графа строим ребра к каждой вершине второго графа.

Степени вершин графа.

Назовем граф максимальным (минимальным) по отношению к некоторому свойству, если граф обладает этим свойством, и никакой другой граф, полученный из данного прибавлением (удалением) вершины или ребра, этим свойством не обладает. Назовем степенью i-ой вершины графа G((i)) число ребер, инцидентных i-ой вершине.

2 (1)=1- висячая вершина, (4)=2 - 3 транзитивная.

Очевидно, что сумма всех степеней 1 вершин неориентированного графа дает 4 2n, где n- число ребер. Число ребер такого графа N=1/2d(i) (1). Если граф ориентированный, то вводят степень d^-(i) – число выходящих дуг из i-ой вершины, и d⁺(i)- число входящих дуг в i-ю вершину. Для ориентированного графа число ребер N=d^-(i)= d⁺(i). Назовем в неор-графе вершину нечетной, если d(i)- нечетное число, и четной в противном случае. Змечание: для ор-графа рассматриваем d^-(i) и d⁺(i). Теорема: число нечетных вершин графа всегда четно. Доказательство из формулы (1). Если в формуле (1) удалить все четные вершины, то сумма оставшихся вершин все равно делится на 2. Граф называется однородным, если степени вершин одинаковы. Для ор-графа d^-= d⁺. Если степень каждой вершины k, то число ребер равно N={nk/2 – для неор-графа, nk- для ор-графа}. Граф называется полным, если каждая его вершина связана ребром (дугой) со всеми остальными. Очевидно, что это однородный граф, где d(i)=n-1, поэтому полный неор-граф имеет ребер N=n(n-1)/2, а ор-граф – N=n(n-1).

Изоморфизм графов.

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

2 1 1 2 3 4 3 1 2 3 4 Два графа G и

1 0 1 0 0 1 4 1 0 0 0 1 H называются

G 2 1 0 1 1 2 0 0 1 1 изоморфными,

3 0 1 0 1 3 0 1 0 1 если

4 0 1 1 0 Н 2 4 1 1 1 0 существует

3 4 биективное отображение  его вершин :V_GV_H, сохраняющее отношение смежности, т.е. дуга (ребро) принадлежит множеству Е_G тогда и только тогда, когда (Vi,Vj)Е_G((Vi),(Vj)) Е_H. Из определения вытекает, что в изоморфных графах одинаковое число вершин, одинаковое число ребер(дуг). Если образ вершины Vi в изоморфном графе Н есть (Vi), то степени их равны. Если две вершины в графе G не смежные, то их образы в графе Н также не смежные. Если графы заданы матицами смежности и они изоморфны, то, производя одинаковые (т.е если переставить местами 1 и 2-ю строки, то нужно переставить 1 и 2 столбцы) перестановки строк и столбцов первого графа, можно получить матрицу изоморфного графа. Чтобы доказать, что графы не изоморфны, нужно выполнить n! перестановок строк и столбцов. Иногда удобней проверит на изоморфность графы через дополнения графов. G- дополнение графа G до полного. Граф G называется дополнением к графу G, если число вершин у них одинаковое (V_H=V_G), а каждое ребро, если оно Е_`G , то оно Е_G. Граф называется самодополнительным, если он изоморфен своему дополнению. Если графы изоморфны, то и их дополнения тоже изоморфны.

Маршруты и пути на графах. Теорема о выделении простого маршрута (пути).

Пусть граф G не ориентированный. Маршрутом называется такая конечная или бесконечная последовательность ребер, что начало каждого следующего совпадает с концом предыдущего. Часть рассматриваемого маршрута называется подмаршрутом. Вершина, от которой начинается маршрут, называется начальной; кончается – конечной. Длиной маршрута называется число ребер в нем. Причем каждое ребро считается столько раз, сколько раз оно явно входит в маршрут. Маршрут, все ребра которого различны, называется цепью(вершины могут повторяться). Цепь, вершины которой различны, называется элементарной. Замкнутая цепь называется циклом. Замкнутая элементарная цепь называется элементарным циклом. Пусть теперь G- ор-граф. Для ор-графа вводятся понятия ориентированного маршрута или нет. Ориентированный маршрут называется путем. Путь, у которого все дуги различны, называется цепью. Элементарная цепь – все вершины различны. Замкнутая цепь называется контуром. Замкнутая элементарная цепь – элементарный контур. Замечание: когда говорят о контуре графа, то считают, что он всегда ориентирован.

Теорема1: из всякого незамкнутого маршрута (пути) можно всегда выделить элементарную цепь с той же начальной и конечной точкой. Доказательство: пусть мы имеем не элементарную цепь, тогда найдется вершина V, кот. инцидентна. Пронумеруем все ребра, инцидентные вершине V. Отсюда следует, что если какие-нибудь вершины V и U соединены цепью, то они соединены и элементарной цепью. Аналогичная теорема имеет место для замкнутых маршрутов и путей. Из псевдографов, мультиграфов(ор. или нет), из всякого цикла (контура) можно выделить элементарный цикл (контур).