275
Глава 10
Экстремальные части графа
10.1Основные понятия
Ряд классических задач теории графов сводится к отысканию частей графа, экстремальных относительно некоторого свойства. Речь может идти также о некоторых подмножествах вершин или ребер и о частях, порожденными этими подмножествами.
Определение. Часть G0 графа G называется максимальной (минимальной) , если в G не существует такой части G00, обладающей этим же свойством, которая содержала бы (содержалась бы в) G0, не совпадая с ним.
Определение. Наибольшей (наименьшей) частью графа по некоторому свойству называется максимальная (минимальная) часть с наибольшим (наименьшим) числом элементов графа, определяющих это свойство.
Примеры 10.1.
1. Максимальный полный подграф обыкновенного графа – такой подграф, все вершины которого попарно смежны и он не содержится ни в каком другом подграфе.
276 |
|
|
|
|
|
Глава 10. |
Экстремальные части графа |
|
||
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
4 |
5 |
Максимальные полные подграфы |
|||||
|
|
порождены подмножествами вер- |
||||||||
|
|
|
|
|
|
|
|
|
||
|
¡¡@r |
@ 3 ¡¡ |
r |
r |
||||||
|
шин |
|||||||||
|
¡ |
|
|
@¡ |
|
|
|
|
f1; 2; 3; 7g; f3; 4; 6g; f4; 5g. |
|
r@@ |
¡¡@r @ |
|
|
|
|
|||||
1 |
|
|
|
|
Наибольший полный подграф по- |
|||||
@¡ |
|
@ |
|
|
|
рожден подмножеством вершин |
||||
|
|
r |
7 |
|
r 6 |
|
|
f1; 2; 3; 7g. |
||
2.Простой разрез можно считать минимальным, так как мы определили его, как не содержащий никакого другого разреза. Наименьший простой разрез – это простой разрез с наименьшим числом ребер.
3.Максимальный пустой (безреберный) подграф обыкновенного графа – это такой подграф, все вершины которого попарно несмежны и он не содержится ни в каком другом пустом подграфе. Наибольший пустой подграф – это максимальный пустой подграф с наибольшим числом вершин (среди всех максимальных). J
Если, кроме того, граф взвешенный (по вершинам или ребрам, либо по тем и другим), то обычно отыскивается наибольшая (наименьшая) часть с наибольшим (наименьшим) весом. Очень часто экстремальная часть не единственна и задача сводится к нахождению либо всех экстремальных частей, либо хотя бы одной экстремальной части.
Сэкстремальными частями графа связаны различные его числовые характеристики.
Определение. Граф общего вида называется плотным, если все его вершины попарно смежны.
Число вершин наибольшего плотного подграфа называется плотностью '(G) графа G, а число вершин наибольшего пустого подграфа – неплотностью "(G) графа G.
В литературе встречается и другая терминология. Приведем ряд синонимов:
²наибольший полный подграф – клика, '(G) – кликовое число;
²наибольший пустой подграф – внутренне устойчивое множество
(ВУМ), независимое множество; неплотность – число внутренней устойчивости, число независимости "(G).