- •Устойчивость, порытия, паросочетания
- •1.1. Основные определения
- •1.2. Определение чисел ε0(g), π0(g), π1(g).
- •Алгоритм выделения пустых подграфов.
- •1.3. Определение чисел β0(g), β1(g).
- •1.5. Плотность p(g) графа g.
- •1.6. Максимальный поток через сеть.
- •Задачи для самостоятельного решения.
- •2. Раскраска вершин и ребер графа.
- •2.1. Понятие раскраски вершин и ребер графа
- •Раскраска вершин графа.
- •Оценки химического числа h(g).
- •2.3. Раскраска ребер графа.
- •2.4. Алгоритм минимальной раскраски вершин (ребер) графа g
- •Задачи для самостоятельного решения.
- •3. Планарность графа.
- •1.1. Основные определения……………………………………………...
- •Для студентов всех форм обучения специальностей «Компьютерные системы и сети», «Системное программирование»
1.5. Плотность p(g) графа g.
Часто в графе требуется определить максимальное число попарно смежных вершин графа G.
Плотностью p(G) графа G=<V, Г> называется максимальная мощность носителя полного подграфа F графа G.
Значит, для определения плотности p(G) графа G необходимо выделить в графе G все полные подграфы.
Алгоритм выделения полных подграфов.
Сопоставляем корню синтезируемого дерева заданный граф.
Фиксируем в графе вершину v0 с максимальной степенью, сопоставив ее концу исходящей из корня дуги. Строим | v0 | исходящих из корня дуг ( | v0 | - мощность носителя неокрестности вершины v0). Конец каждой из этих дуг взаимно однозначно сопоставляем вершине неокрестности (v0).
Каждый конец vα построенных дуг взвешиваем окрестностью G(vα ) вершины vα графа, сопоставленного рассматриваемому корню.
Считаем конец vα п построенного яруса корнем нового дерева.
Устанавливаем, взвешена ли вершина vα символом Ø. Если «нет», то переходим к п.2, если «да» - то к п.6.
Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют полные подграфы заданного графа.
Закон поглощения. Если в k-ом ярусе дерева вершины vi и vj смежны, поддерево с корнем vi построено и если в поддереве с корнем vj, то соответствующая ветвь не строится.
Построение дерева для определения полных подграфов графа G аналогично построению дерева для определения пустых подграфов графа G с учетом особенностей алгоритма выделения полных подграфов и соответствующего закона поглощения.
Пример 11. Определить плотность p(G) графа G (рис. 1.1).
Используя алгоритм выделения полных подграфов, построим искомое ориентированное дерево (рис. 1.13).
1
2 6
3 5
4
1
6 6
3 4 4
3 6 6 6
1
Ø Ø Ø Ø
F1 F2 F3 F4
Рис. 1.13
Здесь Fi – полные подграфы. Из рисунка видно, что мощность носителей всех подграфов равна трем, значит.
р(G) = |{2, 4, 3}| = |{2, 4, 6}| = |{2, 1, 6}|= |{4, 5, 6}| = 3.
Каждое множество состоит из попарно смежных вершин. ■