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

Доказательство. Проведем доказательство, определив процедуру построения ядра K для произвольного неориентированого графа G = (V

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

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

1. Положим K = .

2. Возьмем произвольную вершину v Î V, которая не является соседней с вершинами из K. Добавим v к множеству K.

3. Продолжаем процесс добавления вершин к множеству K до тех пор, пока в V имеются вершины, не являющиеся соседними с вершинами, включенными в K.

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


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







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