Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Числа внутренней и внешней устойчивости графа

Читайте также:
  1. Figure 6. Ежедневная оценка числа сотрудников в зависимости от времени обработки запросов и количества инцидентов
  2. H. Числа Армстронга
  3. IV этап. Анализ и оценка финансовой устойчивости предприятия.
  4. J. Числа Смита
  5. А17. Какие из перечисленных устройств относятся к внешней памяти?
  6. Алгебраическая форма комплексного числа
  7. Анализ внешней среды компании

Рассмотрим теперь число внутренней устойчивости. Если две любые вершины подмножества X’ графа G = (X, U), X’ Í X не смежны, то оно называется внутренне устойчивым. Подмножество y i Í X графа G = (X, U) называется максимальным внутренне устойчивым подмножеством (МВУП) или независимым (НП), если добавление к нему любой вершины xi Î X делает его не внутренне устойчивым. Подмножество y i будет независимым, если

" xi Î y ixi Ç y i = Æ). (17.8)

Независимые подмножества различаются по числу входящих в них элементов. В произвольном графе G можно выделить семейство всех НП вида y = {y1, y2,..., y s }. Независимые подмножества, содержащие наибольшее число элементов, называются предельными. Тогда число внутренней устойчивости h(G) определяется мощностью предельного НП

h(G) = |max y i |, y i Î y. (17.9)

Число внутренней устойчивости h(G) можно связать с хроматическим числом c(G) следующим образом: h(G)c(G) ³ n.

Рассмотрим вопросы построения семейства независимых подмножеств на основе матрицы смежности или ее списка. Данный алгоритм описан А. Кофманом на основе идей предложенных К. Магу. Идея алгоритма построения семейства y = {y1, y2,..., y l } заключается в следующем. В списке смежности графа G определяется строка, имеющая наибольшее число элементов. Если таких строк несколько, то выбирается любая. Для определенной строки i записывается элемент C i = (xi + xk × xl ×... × xq), (где знак сложения “ xi + xk ” — подразумевает операцию дизъюнкции, а знак умножения “ xk × xl ” или “ xk xl ” – операцию конъюнкции). Здесь xi – вершина графа, соответствующая выделенной строке i, а xk, xl,..., xq – вершины, смежные с xi. Далее в списке смежности исключается строка i, а также элементы с индексом i из всех оставшихся строк списка. Указанная операция соответствует выделению из графа G звездного подграфа с вершиной xi. В списке снова определяется строка j с наибольшим числом элементов и записывается элемент C j = (xj + xp × xr ×... × xv). Далее процесс выполняется аналогично до тех пор, пока в списке для оставшихся строк не будет содержаться ни одного элемента. Затем составляется произведение П = C i × C j ×... × C k, в котором раскрываются скобки, и в полученной сумме выполняется минимизация с учетом выражений

xi n = xi, xi + xi +... + xi = xi; xi + 1 = 1; xi + xi xj = xi. (17.10)

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

Методика определения МНП используется для раскраски вершин графа G.

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

Если получено семейство МНП, то можно построить матрицу M = ||m i,j ||n×w, где

w – число МНП в семействе y. Тогда задачу раскраски сводят к нахождению наименьшего числа строк, покрывающих все ее столбцы единицами.

Например, для графа G (рис. 17.1) матрицу M можно записать следующим образом:

    x 1 x 2 x 3 x 4 x 5 x 6 x 7  
M = y1               .
y2              
y3              
y4              
y5              

Проанализировав данную матрицу, можно отметить, что минимальное число строк, покрывающих все столбцы матрицы, равно трем. Это строки y1 (покрываются столбцы x 1, x 5, x 6 и x 7), y5 (покрываются столбцы x 3, x 4), а также либо строка y3 (покрываются столбцы x 2, x 6), либо строка y4 (покрываются столбцы x 2, x 4).

Таким образом, можно выполнить следующую раскраску графа: вершины x 1, x 5, x 6 и x 7 – первый цвет; вершины x 3, x 4 – второй цвет; вершина x 2 – третий цвет.

Рассмотрим алгоритм определения внешне устойчивого подмножества.

Пусть исследуемый объект задан в виде неориентированного графа G = (X, Г x), который можно рассматривать как пару, образованную множеством Х и многозначным отображением Г х множества Х в себя. Х = { x 1, x 2,..., xn } – множество вершин графа, Г хi = { xk, xe,..., xp } определяет множество вершин xk, xe,..., xp, смежных с вершиной xi, другими словами, определяет ребра графа (xi, xk), (xi, xe),..., (xi, xp); .

Подмножество вершин M i Í Х графа G называется внешне устойчивым, если

(" x Ï M i) (G x Ç M i ¹ Æ). (17.11)

Внешне устойчивое подмножество (ВУП) называется минимальным, если удаление из него произвольной вершины делает его внешне неустойчивым. В каждом графе можно выделить семейство М = {M1, M2,..., M i } минимально внешне устойчивых подмножеств (МВУП). Элементы семейства М отличаются друг от друга по виду и количеству входящих в них элементов. Мощность МВУП, содержащего наименьшее число вершин, называется числом внешней устойчивости (b(G)).

Рассмотрим алгоритм получения минимального внешне устойчивого подмножества и наметим путь получения семейства МВУП.

Для задания графов будем использовать структурные числа. Система А, не содержащая одинаковых столбцов ai и одинаковых элементов a (q, i) в каждом столбце, называется структурным числом.

A = { a 1, a 2,..., an }, ai ¹ aj, aq = { a (1, q), a (2, q),..., a (m, q)}; a (i, q) ¹ a(j, q).

Столбцам структурного числа (СЧ) можно поставить в соответствие покрывающие деревья графа, а элементам столбцов СЧ – номера соответствующих деревьев. СЧ А имеет геометрическое изображение в виде графа G = (X, Г x), Х = { x 1, x 2,..., xn }, если существует разложение А на простые сомножители P1, P2,..., P n -1 и произвольный элемент ai Î P i встречается не более чем в двух сомножителях. Если каждый P i записать в виде номеров ребер, смежных вершине xi, то СЧ графа G примет вид А = P1, P2,..., P n -1. Произведение элементов P i позволит получить СЧ в виде матрицы, где каждый столбец соответствует номерам ребер покрывающего дерева.

Граф G будем задавать в виде преобразованного структурного числа (ПСЧ).

A = Q1, Q2,..., Q n; Q i = [ i ][ j 1, j 2,..., jl ] = [ i ][Q’ i ].

Сомножитель Q i соответствует вершине xi графа G; i – индекс xi; Q’ i = j 1, j 2,..., jl – последовательность индексов вершин, смежных xi.

Для графа G (рис. 17.7)

Рис 17.7. Граф G

преобразованное структурное число запишется следующим образом:

А = [1] [2, 3, 4, 5] .
[2] [1, 5, 6]
[3] [1, 4, 7]
[4] [1, 3, 6]
[5] [1, 2, 7]
[6] [2, 4]
[7] [3, 5]

Очевидно, что такая запись идентична той, что получилась бы, если бы мы использовали списочное задание графа. Таким образом, преобразованное структурное число А (ПСЧ) это не что иное как список смежности рассматриваемого графа. При этом, для задания графа достаточно n – 1 строк вида Q i. В связи с вышесказанным в дальнейшем при решении практических задач будем считать равнозначным обозначение A (т.е. преобразованное структурное число) и RL (т.е. список смежности).

Введем понятие расширенной алгебраической производной ПСЧ, которую запишем следующим образом:

– исключена строка Q i, а также элементы i и j 1, j 2,..., jl из Q’ k частей оставшихся строк А.

Указанная операция соответствует удалению из графа G звездного подграфа с вершиной xi, а также ребер, соединяющих вершины смежные xi. Вершины, удаленные после взятия производной, будем записывать так: X’ = { i, j 1, j 2,..., jl }. Причем X’ Í X.

На основе введенной операции взятия расширенной алгебраической производной сформулируем алгоритм построения минимального внешне устойчивого подмножества M i Í M. Основная идея алгоритма заключается в следующем. В ПСЧ определяется строка Q i, у которой |Q’ i | максимальна. Если таких строк несколько, то выбирается любая. Далее определяется расширенная алгебраическая производная и записывается подмножество X’ = { xi, xk, xl,..., xq } (вершины xk, xl,..., xq соответствуют элементам Q’ i). Затем производится сравнение Х с Х’. Если Х’ = Х, то вершина xi образует внешне устойчивое подмножество M1. В противном случае в ПСЧ A’ снова определяется строка Q j, у которой |Q’ j | максимальна. Если таких строк несколько, то выбирается строка Q s, которая имеет максимальное число элементов, не вошедших в подмножество Х’ на предыдущем шаге. Находится и записывается подмножество X’’. Если X’’ = Х, то вершины xi и xj образуют внешне устойчивое подмножество M1 = { xi, xj }. Если нет, то процесс повторяется аналогично, пока на некотором l шаге X( l ) = X. Для построения семейства М необходимо аналогичные операции над ПСЧ выполнять последовательно с каждой строкой с просмотром всех ответвлений.

Запишем алгоритм построения минимального внешне устойчивого подмножества множества вершин G.

1°. Запись по графу G преобразованного структурного числа А.

2°. Выбор в А строки Q i c |Q’ i | = max.

3°. Определение и получение Х’.

4°. Сравнение X’ с Х. Если |X’| = |X|, то М1 = { xi } и переход к 6°. Иначе к 5°.

5°. Выбор в ПСЧ строки j с максимальным Q’ j, j: = i и переход к 3°.

6°. Выделено внешне устойчивое подмножество. Конец работы алгоритма.

Работу алгоритма покажем на примере графа G (рис. 17.7). В ранее записанном ПСЧ А выделим строку Q1, т.к. часть Q’1 содержит наибольшее число элементов. Определим и получим новое ПСЧ

А’ = [2] [6] .
[3] [7]
[4] [6]
[5] [7]
[6] [Æ]
[7] [Æ]

Выделенное подмножество – X’ = { x 1, x 2, x 3, x 4, x 5}. Граф, соответствующий A’, показан на рис. 17.8.

Рис. 17.8. Преобразованный г раф G

Мощность X’ не равна мощности Х. Следовательно, вершину x 1 относим в М1 и продолжаем процесс получения внешне устойчивого подмножества. На втором шаге определяем строки Q2, Q3, Q4, Q5. Так как мощность этих строк одинакова, мы можем выбрать любую, например строку Q2. После этого вычисляем и получаем:

А’’ = [3] [7] .
[4] [Æ]
[5] [7]
[6] [Æ]
[7] [Æ]

Теперь X’’ = { x 1, x 2, x 3, x 4, x 5, x 6}. Величина |X’’| ¹ |X|, следовательно, вершину x 2 относим к М1 и алгоритм продолжает работу. Рассматриваем строки Q3 и Q5. Выбираем любую из них, например Q3, и определяем значение . В результате получим

А’’ = [4] [Æ] .
[5] [Æ]
[6] [Æ]
[7] [Æ]

X’’’ = { x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8} = X. Следовательно, получили внешне устойчивое подмножество M = { x 1, x 2, x 3}.

Теорема 17.2. Подмножество М i, полученное по алгоритму, является минимальным внешне устойчивым подмножеством.

Доказательство. Покажем, что М i есть внешне устойчивое подмножество. Предположим, что М i не является внешне устойчивым, т.е. элементы подмножества вершин М i совместно не смежны оставшимся вершинам графа. Это говорит о том, что на конечном l шаге работы алгоритма X( l ) ¹ X, что противоречит условию алгоритма. Так как алгоритм заканчивает работу, когда X( l ) ¹ X, то М i является внешне устойчивым подмножеством.

Покажем теперь, что М i Ì М является минимальным внешне устойчивым подмножеством. Предположим, что существует М j такое, что М j Ì М i, т.е. существует, по крайней мере, один элемент xb Î X, после удаления которого из М i, подмножество М j будет внешне устойчивым. Другими словами, алгоритм после получения внешне устойчивого подмножества продолжит работу и выделит М i É М j, что противоречит структуре алгоритма. Следовательно, М i есть минимальное внешне устойчивое подмножество.

Для нахождения числа внешней устойчивости необходимо выделить семейство минимальных внешне устойчивых подмножеств и определить в нем наименьшее по мощности подмножество.

Существуют графы, которые содержат некоторое подмножество X’ Í X вершин, причем это подмножество является одновременно внутренним и внешне устойчивым. Подмножества такого типа называются ядрами графа.

Теорема 17.3 Если граф G = (X, U) имеет ядро, то его числа устойчивости удовлетворяет условию

n(G) ³ b(G). (17.12)

Например, в графе G (рис 3.7) подмножество вершин { x 3, x 5, x 6} является ядром, так как оно одновременно и внешне и внутренне устойчиво. Причем h(G)= 3 = b(G).


Дата добавления: 2015-10-26; просмотров: 355 | Нарушение авторских прав


Читайте в этой же книге: Связь между эйлеровыми и гамильтоновыми графами | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Алгоритм Робертса ─ Флореса | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Геометрический метод решения | Расстояния на графах | ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ | ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ | Цикломатическое и хроматическое числа графа | ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ |
<== предыдущая страница | следующая страница ==>
ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ| ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

mybiblioteka.su - 2015-2024 год. (0.013 сек.)