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