АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Доказательство. Заметим, что поскольку петли в графе считается неориентированными ребрами, то ориентированные графы не имеют петель.

Заметим, что поскольку петли в графе считается неориентированными ребрами, то ориентированные графы не имеют петель.

Пусть G = (V, U) - ориентированный граф. Выделим множество D,состоящее из всех таких вершин в G, для которых не существует путей, ведущих в вершины, не лежащие с ними на одном цикле. При этом сами циклы могут быть любыми.

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

На множестве D определим отношение эквивалентности r соотношением " a, b Î D (a r b a и b лежат на одном цикле).

Образуем множество S, включив в него по одной вершине из каждого класса эквивалентности для отношения r.

Покажем, что множество S образует базу графа G.

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

2. Если v Î V \ S и v Î D, тогда из v ведет путь в такую вершину из S, которая лежит с v на одном цикле.

Если же v D, то из v ведут пути в вершины, не лежащие с v на одном цикле. Возьмем любой такой путь. Дополнительно потребуем, чтобы он был простым и имел максимальную длину среди всех подобных путей.

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

В первом случае путь заканчивается в вершине из S. Во втором случае выбранный путь может быть продолжен до вершины класса эквивалентности, которая была включена в S.

Следовательно, множество S является базой графа G.

Дата добавления: 2015-09-27 | Просмотры: 378 | Нарушение авторских прав