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

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

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


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

ОБОБЩЕННЫЕ СТРУКТУРНЫЕ ПОКАЗАТЕЛИ СЕРВИСА НА ГРАФАХ

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

В сервисе часто возникает задача получения показателей, характеризующих сервис в целом, обобщенных показателей. Например, в системе потребителей и производителей можно определить степень связи потребителей или производителей друг с другом; найти такие предприятия, удаление которых приводит к образованию групп независимых предприятий; выявить тех потребителей, которые образуют тесно связанную группу, определить влияние этой группы на других; вычислить степень надежности сервиса, найти самый ненадежный элемент в системе и определить меры по повышению ее надежности.

Все эти задачи связаны с поиском таких подмножеств множества вершин Vи ребер Е графа G = (V, Е), которые обладают определенными свойствами.

Независимые множества вершин

  • 1. Пусть нужно сформировать группу клиентов из всех клиентов, причем некоторые из них попарно несовместимы. Если каждому клиенту поставить в соответствие вершину, а ребрами отобразить факт несовместимости, то на графе необходимо найти такое множество вершин, которое бы не содержало двух смежных вершин; иначе говоря, найти несвязный подграф и максимальную мощность подмножества S с V, такого, что порожденный подграф (S) вполне несвязный.
  • 2. Пусть имеется п работ, которые необходимо выполнить. Обозначим эти работы вершинами графа. Некоторые работы требуют одних и тех же ресурсов. Наличие общих ресурсов для обеспечения работ отобразим ребрами графа. Максимальное независимое множество графа представляет тогда максимальное множество работ, которое можно выполнить одновременно за один и тот же промежуток времени.

В неориентированном графе G = (V, Е) подмножество вершин называется независимым множеством графа G, если никакие две вершины Sне смежны в графе G [27], т.е. никакая пара вершин не соединена ребром. Такое множество называется также внутренне устойчивым множеством. Независимое множество графа максимально, если не существует такого независимого множества Р, что Р > |5|. Число вершин a0(G) в максимальном независимом множестве графа G называется числом независимости (числом внутренней устойчивости) графа и является обобщенным структурным показателем, характеризующим степень независимости рассматриваемых объектов.

Граф с независимым множеством вершин

Рис. 4.1. Граф с независимым множеством вершин

Рассмотрим граф взаимоотношений клиентов на рис. 4.1. В графе можно выделить независимые подмножества {a, d), {b, е}, {с, е}, {b,f d), причем {b,f d} — максимальное подмножество. Число независимости a0(G) = 3.

Независимое множество можно рассматривать как вершинный аналог паросочетания. Так же, как в паросочетании, здесь можно определить чередующуюся последовательность вершин. Например, в графе на рис. 4.1 последовательность {с, b, a,f е, d) является максимальной чередующейся последовательностью по отношению к независимому множеству {b,f d).

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

Рассмотрим простой неориентированный граф G= (V, Е), т.е. без петель и кратных ребер. Граф G называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов так, что не найдется двух смежных вершин одного цвета [19, 27]. Наименьшее число цветов у((7) называют хроматическим числом графа, а задачу нахождения этого числа — задачей о раскраске. /-раскраска графа G= (V, Е) порождает разбиение (Vx, V2, ..., Vr) множества V, где Vt — подмножество вершин, которым присвоен цвет /, и поэтому является независимым множеством.

Граф с вершинами, раскрашенными в три цвета

Рис. 4.2. Граф с вершинами, раскрашенными в три цвета

На рис. 4.2 показан граф, вершины которого раскрашены в три цвета.

Для у(G) предложены оценки:

О нижняя

О верхняя

О для полных графов

В рассмотренном примере

Известно, что каждый планарный граф 4-раскрашиваемый, а каждое дерево имеет хроматическое число, равное 2. В более общем случае справедлива следующая теорема [6].

Теорема 4.1. Пусть G— обыкновенный граф с п вершинами, в котором каждой вершине инцидентны не более чем к ребер (к> 2). Предположим, что в (7не существует связной компоненты, которая является полным графом с к + 1 вершинами. Тогда вершины G можно раскрасить к цветами так, чтобы не было двух смежных вершин, окрашенных одним цветом.

Между хроматическим числом графа и понятием /:-дольного графа имеется тесная связь. Хроматическое число графа Gявляется просто наименьшим к, при котором (/является ^-дольным. Например, дерево имеет хроматическое число 2, поэтому его можно изобразить двудольным графом.

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