Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Операции над частями графа.
Граф Н называется частью графа 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. ч.т.д.
|