Прошлый пост об основах теории графов пришёлся вам по душе; видя востребованность такого материала с вашей стороны, выпускаю его продолжение

Подробнее разберём некоторые понятия, связанные с подграфами.

Напоминаю, что подграфом заданного графа называется любая его часть.

Граф называется [исходным графом] или [надграфом] любого своего подграфа. О подграфе говорится, что он [входит в] исходный граф, а исходный граф [включает в себя] любой свой подграф. Эти термины взяты из теории множеств («надмножество» и «подмножество» тоже весьма похожи на «надграф» и «подграф» как слова) и применяются к графам, поскольку любой граф, как уже было показано ранее, может быть представлен в виде множества упорядоченных пар.

Говорится, что подграф [покрывает] входящие в него вершины и рёбра исходного графа, и [не покрывает] остальные вершины и рёбра исходного графа.

Добавление в подграф новых вершин или рёбер исходного графа называется [расширением]

этого подграфа. Противоположное по смыслу действие — исключение части вершин или рёбер из подграфа — называется [уменьшением] этого подграфа.

Подграф, полностью совпадающий со своим надграфом (да, любой граф тоже считается своим подграфом), называется [несобственным подграфом] исходного графа, а любой другой его подграф называется [собственным подграфом] этого графа.

Отмечу, что даже если подграф включает в себя все вершины исходного графа, это ещё не означает, что такой подграф будет несобственным, поскольку в нём могут присутствовать не все рёбра исходного графа. Вообще, подграф, содержащий все вершины исходного графа (т.е. подграф того же порядка), называется [остовным подграфом] или [фактором] исходного графа.

3-полный подграф часто называют [треугольником] (в самом деле, на него такой граф и похож), а в общем случае n-полный подграф иначе называется словом [клика].

У клик есть несколько похожих понятий, между которыми есть важная разница. Клика графа называется [максимальной по включению], если она не является подграфом другой клики исходного графа. Клика, включающая в себя наибольшее количество вершин исходного графа, называется [максимальной по размеру]. Разница между этими понятиями такая: максимальность клики по включению определяется относительно её вершин (т.е. если в исходном графе отсутствует вершина, не входящая в эту клику, но соседствующая со всеми её вершинами, клика будет максимальной по включению), а максимальность клики по размеру — относительно других клик исходного графа (т.е. если в исходный граф не входит клик большего порядка, то клика будет максимальной по размеру).

Вводить понятия минимальной по включению клики и минимальной по размеру клики нет смысла, поскольку в любом графе они будут являться подграфами из одной вершины и нуля рёбер.

У каждого графа есть [кликовое число] — это порядок максимальной по размеру клики графа. Кликовое число графа G обычно обозначается как ?(G).

Наименьшее количество клик графа, которые, будучи взятыми вместе, покрывают все рёбра исходного графа, называется [числом пересечений] этого графа.

Известна тесно связанная с этим задача о кликовом покрытии, заключающаяся в ответе на вопрос, возможно ли разбить весь граф на заданное количество непересекающихся клик. Наименьшее число непересекающихся клик, покрывающих все вершины графа, называется [минимальным размером кликового покрытия] этого графа.

О более сложных структурах, связанных с графами, речь пойдёт в следующий раз.

Кстати говоря, как задача о кликовом покрытии, так и задача о нахождении числа пересечений графа, являются NP-полными: это означает, что нашедший алгоритм, решающий любую из них за полиномиальное (или более быстрое) время фактически решит задачу о равенстве классов P = NP, а это одна из задач тысячелетия.

Дерзайте!

Источник: vk.com

Комментарии: