Методические указания к выполнению расчетных работ по теории графов и сетей (1013088), страница 7
Текст из файла (страница 7)
(б) Используя метод Магу, определитьсовокупность минимальных внешне устойчивых множеств вершин орграфа D, изображенного на рис. 5.2, а также число (D).Решение. Согласно методу Магу имеем:5&(Yi i 1 Y ) = (Y Y )&(Yaij 1j132 Y1 Y4 Y5 )&(Y3 Y1 Y4 )&(Y4 Y2 )&(Y5 Y2 ) (опускаем символ & и упрощаем полученную формулу, используя равносильности (5.2),(5.3)) (Y1 Y3 )(Y4 Y2 )(Y5 Y2 ) (Y1 Y3 )(Y2 Y4Y5 ) (приводим полученную формулу к ДНФ, используя дистрибутивность & относительно, и упрощаем ее, используя равносильности (5.1)) Y1Y2 Y1Y4Y5 Y2Y3 Y3Y4Y5.Таким образом, мы получили формулу, находящуюся в ДНФ.
Дальнейшее ее сокращение с использованием равносильностей (5.1) невозможно, а следовательно, искомыми минимальными внешне устойчивыми множествами вершин орграфа D являются:{v1 , v2 }, {v1 , v4 , v5}, {v2 , v3}, {v3 , v4 , v5 }, и при этом ( D) 2.Ядра орграфа. Пусть задан орграф D (V , X ). Множество вершин N V называется ядром орграфа D, если N – одновременно внутренне и внешне устойчивое множество, т.е., если выполняются условия:(N1) v N N D(v) ;(N 2) v V \ N N D(v) .Замечание 5.3. Аналогично определяется ядро и для неориентированного графаG (V , X ), при этом в условиях (N1) , (N 2) D(v) заменяется на G(v).Орграф может не иметь ядра, иметь одно или несколько ядер.
Заметим, что еслиорграф D имеет ядро N , то ( D) | N | ( D).30Пример 5.3. Рассмотрим орграф, изображенный на рис. 5.3. Он не имеет ядер, поскольку любое множество с одной вершиной не является внешне устойчивым, а любоемножество с двумя или тремя вершинами не является внутренне устойчивым.Рис. 5.3Пример 5.4. В продолжение примеров 5.1–2 имеем: {v1 , v3}, {v2 , v4 } – ядра орграфаD, изображенного на рис. 5.1.Теорема 5.1. Для того чтобы множество вершин N V являлось ядром орграфаD (V , X ) (графа G (V , X ) ), необходимо и достаточно, чтобы оно было одновременномаксимальным внутренне устойчивым и минимальным внешне устойчивым.Из теоремы 5.1 следует, что для выделения ядер орграфа D достаточно, например,найти все минимальные внешне устойчивые множества вершин орграфа D, а затем выбрать из них внутренне устойчивые множества.Разбор типового варианта (продолжение).
(в) Определить ядра орграфа D, изображенного на рис. 5.2.Решение. Выберем из минимальных внешне устойчивых множеств вершин орграфа D множества, являющиеся внутренне устойчивыми. Такими множествами являются:{v1 , v4 , v5 }, {v2 , v3 }. В силу теоремы 5.1 – это ядра орграфа D, и других ядер в D нет.D, и других ядер в D нет.Тема 6. Функции на вершинах орграфа.
Порядковая функция. Функция ГрандиРассмотрим орграф D (V , X ), не содержащий контуров, и определим множестваV0 , V1 ,..., Vr :V0 {v V | D(v) },V1 {v V \ V0 | D(v) V0 },V2 {v V \ (V0 V1 ) | D(v) V0 V1},(6.1)…………………………………………r 1r 1k 0k 0Vr {v V \ Vk | D(v ) Vk },rгде r – наименьшее число такое, что V \ Vk . Множества V0 , V1 ,..., Vr называютсяk 0уровнями орграфа D.
СправедливаТеорема 6.1. Уровни орграфа D (V , X ) без контуров являются непустыми31rмножествами, образующими разбиение множества его вершин V (т.е. V Vk иk 0Vi V j при i j ).Справедливо также утверждение, обратное теореме 6.1.Утверждение 6.1. Пусть D (V , X ) – орграф, r 0 , V0 , V1 ,..., Vr – непустые множеrства, удовлетворяющие (6.1), такие, что V Vk . Тогда D – орграф без контуров.k 0Функция O(v), определенная на множестве вершин V орграфа без контуровD (V , X ) и ставящая в соответствие каждой вершине v V номер уровня, которому онапринадлежит, называется порядковой функцией орграфа D.Пример 6.1.
Разобьем орграф D, изображенный на рис. 6.1, на уровни и определимпорядковую функцию O(v). Согласно (6.1) имеемV0 {v V | D(v) } {v4 , v6 },V1 {v V \ V0 | D(v) V0 } {v1 , v5 },V2 {v V \ (V0 V1 ) | D(v) V0 V1} {v3 },V3 {v V \ (V0 V1 V2 ) | D(v) V0 V1 V2 } {v2 },V \ (V0 V1 V2 V3 ) .Определив множества V0 , V1 , V2 , V3 , найдем значения порядковой функции O(v),v V . На рис. 6.1 они указаны при вершинах.Рис. 6.1Рис. 6.2Замечание 6.1.
Для наглядности после разбиения некоторого орграфа D на уровниимеет смысл перерисовать его, последовательно расположив вершины орграфа D на вертикальных прямых; при этом вершины одного уровня располагаются на одной вертикальной прямой (см. на рис. 6.2 новое изображение орграфа D, изображенного на рис. 6.1).Приведем простой алгоритм выделения уровней орграфа без контуров, использующий задание орграфа матрицей смежности.Алгоритм 6.1 (нахождения уровней орграфа D (V , X ) без контуров)Шаг 1. Выпишем матрицу смежности A(D).
Образуем под матрицей A(D) строку 0 , вi -ом месте которой укажем число единиц в i -й строке матрицы A(D). Уровень V0 образуют вершины, которым в строке 0 соответствует число 0. Если V V0 , то задача решена и V0 – единственный уровень орграфа D. В противном случае переходим к шагу 2.32Шаг 2. Образуем под строкой 0 строку 1 , ставя под каждым нулем строки 0 символ , а на любом другом i -м месте – число единиц в i -й строке матрицы A(D), не учитываяединицы в столбцах, находящихся над символами в строке 1 .
Уровень V1 образуютвершины, которым в строке 1 соответствует число 0. Полагаем j 1.Шаг 3. Пусть при некотором j 1 уже построены строки 0 ,..., j , по которым полученымножества V0 ,...,V j . Если строка j состоит из нулей и символов , то задача решена ипри r j V0 ,...,V j – уровни орграфа D. В противном случае переходим к шагу 4.Шаг 4. Образуем под строкой j строку j 1 , ставя под каждым нулем и символом строки j символ , а на любом другом i -м месте – число единиц в i -й строке матрицыA(D), не учитывая единицы в столбцах, находящихся над символами в строке j 1 .Уровень V j 1 образуют вершины, которым в строке j 1 соответствует число 0. Увеличиваем j на 1 и переходим к шагу 3.Следующее утверждение говорит о том, что наряду с нахождением уровней орграфа без контуров алгоритм 6.1 позволяет проверить наличие хотя бы одного контура у произвольного орграфа.Утверждение 6.2.
Для того, чтобы в орграфе D (V , X ) имелся хотя бы один контур, необходимо и достаточно, чтобы в результате применения к D алгоритма 6.1 при некотором j 0 появилась строка j без нулей.Разбор типового варианта. (а) Используя алгоритм 6.1, разбить орграф, изображенный на рис. 6.1 на уровни. Привести новое изображение орграфа в соответствии с замечанием 6.1.Решение. Составим матрицу смежности A(D) орграфа D, а затем укажем под нейстроки 0 , 1 , 2 , 3 , являющиеся результатом работы алгоритма 6.1 (см.
табл. 6.1). Изтабл. 6.1 следует, что уровнями орграфа D являются V0 {v4 , v6 }, V1 {v1 , v5 }, V2 {v3 },V3 {v2 }. Изображение орграфа D, построенное с учетом замечания 6.1, приведено нарис. 6.2.v1v2v3v4v5v6v1000001v2001101v3100110v4000000v5000001v600000001330101012021030Табл. 6.133Функция Гранди. Рассмотрим орграф D (V , X ). Функция g (v), ставящая в соответствие каждой вершине v V целое число g (v) 0, называется функцией Гранди дляорграфа D, если в каждой вершине v V число g (v ) является минимальным из всех целых неотрицательных чисел, не принадлежащих множеству {g (w) | w D(v)}, и g (v) 0при D(v) .Если для орграфа D существует функция Гранди, то говорят, что орграф D допускает (в противном случае – не допускает) функцию Гранди. Не всякий орграф D допускает функцию Гранди (см.
пример 6.3), а если и допускает, то она не обязательно единственная (см. пример 6.4).Из определения функции Гранди следует, что справедливоУтверждение 6.3. Если орграф D (V , X ) допускает функцию Гранди, то найдется вершина v V такая, что g (v) 0.Пример 6.2. На рис. 6.3 приведено изображение орграфа D, допускающего функцию Гранди, около каждой вершины которого указано значение этой функции.Рис. 6.3Пример 6.3. Покажем, что орграф D, изображенный на рис.
5.3, не допускаетфункцию Гранди. Предположим обратное, т.е. орграф D допускает функцию Гранди.Используя утверждение 6.3, получаем, что на некоторой вершине значение функцииГранди равно нулю. Пусть для определенности g (v1 ) 0 (другие случаи рассматриваютсяаналогично). Тогда в силу того, что D(v3 ) {v1}, D(v2 ) {v3 }, D(v1 ) {v2 }, последовательно получаем: g (v3 ) 1, g (v2 ) 0, g (v1 ) 1, а это противоречит равенству g (v1 ) 0.Пример 6.4.
На рис. 6.4 приведены два варианта функции Гранди для одного и того же орграфа D.Рис. 6.4Приведем достаточное условие существования функции Гранди, а также алгоритмее определения.34Теорема 6.2. Пусть D (V , X ) – орграф без контуров. Тогда D допускает и притом единственную функцию Гранди.Эту теорему обосновываетАлгоритм 6.2 (определения функции Гранди на множестве вершин Vорграфа D (V , X ) без контуров)Согласно теореме 6.1 множество вершин V орграфа D можно разбить на уровниV0 , V1 ,..., Vr .
По определению функции Грандиv V0 g (v) 0 ; v V1 g (v) 1.(6.2)Заметим, что значения функции Гранди на каждом уровне Vi , где i 2, однозначнонаходятся по ее значениям на предыдущих уровнях V0 , V1 ,..., Vi 1 (поскольку v Vii 1D(v ) Vk ), а следовательно, исходя из (6.2), ее можно однозначно определить на всехk 0последующих уровнях.Следующая теорема показывает, что по функции Гранди орграфа можно легко определить его ядро.Теорема 6.3. Если орграф D (V , X ) допускает функцию Гранди g (v), то множество вершин N {v V | g (v) 0} является ядром этого орграфа.
В случае, когда орграф Dявляется бесконтурным, это ядро является единственным.Разбор типового варианта (продолжение). (б) Используя алгоритм 6.2, найти значения функции Гранди для орграфа D, изображенного на рис. 6.1, а также его единственное ядро (см. теорему 6.3).Решение. Используя разбиение орграфа D на уровни (см. рис. 6.2), с учетом (6.2)получаем: g (v4 ) g (v6 ) 0, g (v1 ) g (v5 ) 1. Далее по определению функции Гранди находим значение этой функции для вершины v3 V2 , а именно, g (v3 ) 2, а затем для вершины v2 V3 , а именно, g (v2 ) 1 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
