Полная версия

Главная arrow Туризм arrow Основы функционирования систем сервиса

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Показатели, связанные с ребрами графа

Независимые множества ребер. Реберной &-раскрас- кой графа G= (V, Е) называют присвоение ребрам графа различных цветов, при этом никакие два смежных ребра не получают в ней одинакового цвета. Минимальное число к называется хроматическим индексом или реберным хроматическим числом и обозначается у'( G).

Реберная ^-раскраска графа G= (V, Е) влечет разбиение ь Е2, ... , Ек) множества Е, где ^ — подмножество ребер, которым в раскраске присвоен цвет /. Если при раскраске никакие два смежных ребра не получают одинакового цвета, то каждое подмножество Е, является паросочетанием.

Так как при раскраске ребра, инцидентные одной вершине, получают разные цвета, то у'(G) > max [ 5(v,)]. В случае двудольного графа у'(G) = max[5(v, )]. Известно, что для любого простого графа достаточно' цветов max [ 8(Vj)] +1 [27].

Граф с раскрашенными ребрами

Рис. 4.5. Граф с раскрашенными ребрами

На рис. 4.5 изображен граф с раскрашенными в 4 цвета ребрами. Степень вершины а максимальна и равна 4.

Реберное покрытие. Подмножество Рс Аграфа G=(V,E) называется реберным покрытием графа G, если любая его вершина является концевой хотя бы одного из ребер Р. Реберное покрытие покрывает все вершины графа и минимально, если граф не имеет такого реберного покрытия R, чтоR < [Р|. Число ребер pj(G) в минимальном реберном покрытии графа С называется числом реберного покрытия этого графа. Например, в графе на рис. 4.6 множество ребер и е7, е8} образует минимальное реберное покрытие с числом Pj(G) = 3.

Граф с реберным покрытием

Рис. 4.6. Граф с реберным покрытием

Для простого графа G = (V, Е) на п вершинах без изолированных вершин 0С| + Pi = п. Сумма числа паросочетания и числа реберного покрытия равна числу вершин.

Максимальные полные графы (клики). Клики используются при решении задач сервиса по нахождению таких сообществ объектов, которые наиболее связаны между собой, например находится группа клиентов, связанных между собой родственными узами. При этом необходимо определить максимально возможную мощность такого подмножества S с V, для которого порожденный подграф (5) является полным.

Максимальный полный подграф (клика) графа G есть порожденный подграф, построенный на подмножестве S вершин графа и являющийся полным и максимальным в том смысле, что любой другой подграф графа G, построенный на множестве вершин Р, содержащем S, Р S, не является полным [19]. Максимальный полный граф и максимальное независимое множество вершин — противоположные понятия: в максимальном полном графе все вершины попарно смежны, тогда как в максимальном независимом множестве не могут встретиться две смежные вершины.

Максимальное число вершин в кликах графа называется кли- ковым числом графа. Кликовое число характеризует густоту или плотность графа. У плотного графа кликовое число будет больше, а число независимости меньше, чем у разреженного графа.

Для поиска максимальных независимых множеств или кликов используется алгоритм Брона и Кэрбоша [14], работающий следующим образом. На некотором этапе к независимое множество вершин Sk расширяется путем добавления к нему подходящим образом выбранной вершины. В результате получается новое независимое множество Sk + ,. Так продолжается до тех пор, пока порождаемое множество не станет максимальным независимым множеством.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>