Алгоритм раскраски графа (точный) — страница 2

  • Просмотров 4005
  • Скачиваний 89
  • Размер файла 133
    Кб

некоторой вершине, называют локальной степенью данной вершины. Граф, в котором любая пара вершин соединена ребром называется полным. Полный граф обычно обозначают через Кn (n – число вершин в графе). Число ребер полного графа m=n*(n-1)/2. Полный подграф G`=(X`,U`)графа G=(Х,U), X`εX называется максимальным полным подграфом (МПП) или кликой , если этот подграф не содержится в большем (по числу вершин) полном подграфе. Максимальный полный подграф,

содержащий наибольшее число вершин из всех МПП графа называется наибольшим полным подграфом (НПП). Число вершин наибольшего полного подграфа называется плотностью графа – φ(G). Если две любые вершины подмножества X` графа G(Х,U), где X`εX не смежны, то подмножество X` называется внутренне устойчивым. Подмножество ψi X графа G(Х,U) называется максимальным внутренне устойчивым подмножеством (МВУП), или независимым подмножеством (НП), если

добавление к нему любой вершины xjεХ делает его не внутренне устойчивым. Подмножество Yi будет определяться как хjεψi (Гхj uψi =) МВУП различаются по числу входящих в них элементов. МВУП, содержащее наибольшее число элементов (вершин), называют наибольшим (предельным). Мощность НВУП (число вершин наибольшего ВУП) называется числом внутренней устойчивости h (G) = |mах ψi |, где ψiεψ, ψ-семейство всех МВУП. Число внутренней устойчивости

называет также неплотностью графа. Задачи определения наибольших полных подграфов и НВУП являются дополнительными друг к другу. Наибольшему полному подгра­фу графа G=(Х,U) соответствует наибольшее ВУП в графе G=(Х,U), где Uполн\U, Uполн – множество ребер полного графа, построенного на n вершинах. Аналогичные рассуждения могут быть сделаны и для максимальных НП и МВУП. Все эти задачи относятся к так называемым NP полным задачам,

временная сложность которых экспоненциальна относительно входа (числа вершин или ребер графа). Согласно классификации всех задач теории графов по их сложности, приведенной в основополагающей работе Э. Рейнгольда и других, задачи определения МВУП и МПП (нахождение клик) графа по сложности относятся к четвертому классу задач, для которых не существует и не может существовать точного полиноминального алгоритма, так как задачи

этого класса обязательно экспоненциальные относительно входа. Задачи определения НПП и МВУП (наибольшей клики) относятся к третьему классу, для которого открытие полиноминального алгоритма возможно. 2. Алгоритмы раскраски вершин графа Раскраской вершин графа G называется разбиение множества вершин Х на l непересекающихся подмножеств Х1, Х2, ..., Хl; ХХI; XiXj=; i,jI={1,2,..,l}, (1) таких, что внутри каждого подмножества Xi не должно