Операции над частями графа.

Граф Н называется частью графа G, , если множество его вершин V(G) и ребер E(H) содержатся в множествах вершин V(G) и ребер E(H) соответственно, т.е. V(H) V(G) и .

Если V(H)=V(G), часть Н графа П называется суграфом. Суграф н является покрывающим для н – графа G, если любая вершина графа G инцидентна хотя бы одному ребру из Н.

Подграфом графа G(V) с множеством вершин называется часть, которой принадлежат все ребра с обоими концами из .

Над частями графа G могут производиться следующие операции:

· Дополнение к части Н – определяется множеством всех ребер графа G, не принадлежащих Н: E(H) , ;

· Сумма частей и графа G.

и ;

· Произведение :

и .

Две части и не пересекаются по вершинам, если они не имеют общих вершин , а значит, и общих ребер . Части и не пересекаются по ребрам, если . Если , то сумма называется прямой.

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

Изображение графа, в котором никакие 2 ребра не имеют общих точек, кроме их общей вершины, наз. плоским представлением графа. Граф, имеющий плоское представление, наз. плоским. Граф, изоморфный плоскому графу, наз. планарным. Н – часть графа G, если соответствующее множество вершин является подмножеством множества вершин G, и множество ребер тоже.

.

Последовательность ребер, в которой каждая пара соседних имеет общую вершину, наз. маршрутом.

Путем из вершины в наз. такой соединяющий маршрут, в котором каждое ребро не встречается более одного раза.

Две вершины в графа G наз. связными, если в графе существует соединяющий их путь.

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

Теорема Понтрягина – Куратовского: Граф является плоским т. и т.т., когда он не имеет подграфом граф типа1 или граф типа 2(др. словами: для того, чтобы граф был плоским необходимо и достаточно, чтобы он не содержал внутри себя никакого графа, которого можно было сжать до 5- и 6 – угольного графа).

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

Существует граф G связный с множеством вершин v деревом покрытия графа G или покрывающим деревом называется подграф с тем же множеством вершин, которое является деревом.

Теорема Эйлера: для любого плоского графа без перегородок справедливо соотношение

v– e + f = 2, v-множество вершин

е-множество ребер

f-множество граней

Доказательство: (проведем метод математической индукции по числу граней).

пусть f=1, следовательно, G – дерево v-(v-1)+1=2, т.е. 2=2

f=2 v-v+2=2, т.е. 2=2р

предположим, что формула справедлива для графа с f гранями. Докажем, что граней f+1. Цикл, ограничивающий эту грань, содержит r ребер, тогда вершин добавляем (r-1)

(Выделением покрывающего дерева)

Будем удалять ребра в плоском графе до тех пор, пока не получим суграфа, являющийся покрывающим деревом. Каждое удаление ребра уменьшает количество граней и ребер на 1, а соотношение v-e+f остается неизменным, следовательно, эта величина будет одинаковой как у исходного графа, так и у его покрывающего дерева, а для дерева v– e + f = 2. ч.т.д.