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

Доказательство. Пусть графG = (V, U) удовлетворяет условиям теоремы

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

Пусть граф G = (V, U) удовлетворяет условиям теоремы. Построим ядро графа G с помощью следующей процедуры.

1. Обозначим S 1 базу графа G. Определим множество

V 1 = S 1 È G - 1 (S 1).

Удалим из G вершины V 1 вместе с ведущими в них ребрами.

3. В полученном графе G 1 найдем базу S 2, для которой

S 2 Г -1 (Г -1 (S 1) \ V 1) (1).

То есть в базе S 2 содержатся только такие вершины G, из которых в вершины S 1 ведут пути длины 2.

Такая база существует, поскольку в графе G из всякой вершины v Î V \ S 1 ведет путь в некоторую вершину множества S 1. Тогда всякий такой путь из вершины, не являющейся соседней с вершинами множества S 1, проходит через вершины, лежащие от вершин множества S 1 на расстоянии 2. Поэтому в G 1 существует база, удовлетворяющая условию (1). Она состоит из вершин, находящихся на расстоянии 2 от вершин множества S 1.

Образуем множество V 2 = V 1 È S 2 È Г - 1 (S 2).

3. Удалим из G 1вершины S 2 È Г - 1 (S 2) вместе с ведущими в них ребрами.

4. Если еще удалены не все вершины исходного графа, то повторим действия 2 и 3.

Описанный процесс продолжаем до тех пор, пока не будут удалены все вершины исходного графа.

В результате будет построено семейство множеств вершин:

S 1,..., Sm.

Образуем множество S = .

Покажем, что S является ядром графа G.

1. Множество S является внешне устойчивым, поскольку всякая вершина графа G в процессе удаления вершин этого графа попадает либо в некоторое множество Si либо во множество Г - 1 (Si). Поэтому, если v V\S, то i (v Г -1 (Si)), т.е. из v ведет ребро в некоторую вершину множества Si, а значит и в вершину S.

2. Множество S является внутренне устойчивым. Докажем это утверждение методом от противного. Предположим, что во множестве S содержатся две соседние вершины v 1 и v 2 графа G.

Положим для определенности, что v 1 Si и v 2 Sj, причем i < j. Это означает, что ребро, соединяющее эти вершины, ведет из v 1 в v 2. Эта ситуация изображена на рис. 5.29:

 

                   
   
     
     
 
   
 
 
 
 

 


S 1 S 2 ... Si... Sj...

v 1 v 2

 
 


v 0

 

 

Рис. 5.29

По определению последовательности множеств S 1,.., Sm из вершины v 2 в некоторую вершину v 0 Si ведет путь четной длины. Обозначим такой путь как W.

Так как Si - это база подграфа, полученного из графа G на одном из шагов работы описанной выше процедуры, и последовательность v 1, W - это путь в этом же подграфе, то
v 0 = v 1, поскольку в противном случае вершина v 1 не может входить в базу Si.

Поэтому путь v 1, W образует цикл нечетной длины в графе G. Это противоречит условиям теоремы. Следовательно, множество S является внутренне устойчивым.


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







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