Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм нахождения полных подграфов




Читайте также:
  1. Алгоритм RSA
  2. Алгоритм виконання часткового технологічного процесу
  3. Алгоритм виявлення, оцінки та зменшення ризиків виникнення небезпечних ситуацій на виробництві
  4. Алгоритм выборки сообщений из очереди потока
  5. Алгоритм выполнения манипуляции
  6. Алгоритм выполнения манипуляции
  7. Алгоритм выполнения манипуляции
  8. Алгоритм выполнения синтаксического разбора
  9. Алгоритм выполнения синтаксического разбора
  10. Алгоритм вычисления выражений в обратной польской записи

Начальный шаг: строится вершина – корень дерева, которой сопоставляется граф .
Итерационный шаг: на -ом ярусе есть вершина, которой сопоставлен граф .
а) Из выбирается любая вершина и выносится на ярус.
б) На ярус выносятся все вершины, которые входят в .
в) Каждая из вершин яруса взвешивается соответствующим графом – окрестностью от графа .
Заключительный шаг: вершина дерева будет висячей, если соответствующий ей граф – пустой граф.
Замечание
В пункте а) желательно выбирать ту вершину, которая имеет максимальную степень.

Задачу нахождения полных подграфов в можно свести к задаче нахождения пустых подграфов в .

Пример

Полные подграфы графа (или пустые подграфы графа ):



Пример

:    

Пример

: :

Выделяем пустые подграфы:


Дата добавления: 2015-02-10; просмотров: 17; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.02 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты