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

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

Прочитайте:
  1. Доказательство
  2. Доказательство
  3. Доказательство
  4. Доказательство
  5. Доказательство
  6. Доказательство
  7. Доказательство
  8. Доказательство
  9. Доказательство
  10. Доказательство

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

Пусть 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 | Просмотры: 415 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)