Введение в прикладную комбинаторику, Кофман А. (984071), страница 24
Текст из файла (страница 24)
а=с а=с где и — такое наименьшее целое число, что Гй1,= О. (28.2) Легко показать, что подмножества Иа, Й=О, 1, 2, ..., г, образуют разбиение Е и вполне упорядочены отношением Ха 3 1в)а 4втй ( й'. (28.3) А Функция 0(Х), определен- А' Е ная равенством Ат С Х! ~ й(а Ф О (Х~) = й, (28.4) называется порядковой функ- Ю цией графа без контуров Другими словами, предлагается разбить множество вер- у Е шин графа без контуров на непересекающиеся подмножества, упорядоченные так, что если вершина принадлежит подмножеству с номером й, то сле- 1 дующая за ней вершина входит в подмножество с номером, Рис. 110.
ббльшим /г. Подмножества этого разбиения называются уровнями. П ример. На рис. 111 показаны уровни, на которые разла- гается множество вершин графа на рис. 110. Каждой вершине Х; этого графа соответствует некоторое й(в, т. е, некоторое й~(0, 1, 2, ..., 5). Эта порядковая функция Х; ~ й задается таблицей в(и 0 Е Вершина Урсвснь 4 О 2 О 4 2 Порядковую функцию графа без контуров можно определить различными способами; в качестве начального множества можно взять произвольное множество вершин, содержащее й(в Порядковая функция позволяет перенумеровать вершины так, что вершины уровня й(; имеют номера меньшие, чем вершины уровня Ж,~, (рис, !12). Порядковая функция играет важную роль во многих комбинаторных задачах, 173 Понятие порядковой функции для графов с контурами.
Порядковая функция классов графа. Рассмотрим классы графа (максимальные сильно связные подмножества). Как мы видели в А В С В Е К С Н 1 У К Ь М Л А В С В К Е С Н 1 Г К В М Н ЛО 2 ! 3 2 О 2 2 О ! ! 2 2 3 2 О 4 ! Х ! ! Х О О 2 2 3 ! О Х 4 ! Х 1 О Х Х Х 2 ! 2 О ДЗХ Х 3 ! Х О Х Х Х Х ! ! ! Х Л4 Х Х 3 О Х Х Х Х Х Х О О О Х Л5 Х Х О Х Х Х Х Х Х Х Х Х Х х Рис. 1!4. Н» Н Н» Н» Н» Н» В А о Е! С и К С В / и Е м предыдущем параграфе, эти классы упорядочены и граф классов не имеет контуров, н поэтому можно определить уровни. Например, на рис, 113 показаны уровни для графа классов на рис. 96. 17!5 Е а) ГА = (Е!, ГВ = (А), ГС =(А, В), ГВ = (С, 6), ГЕ=Я, ГЕ = (В, 6, Н, )), Г6=(В, Н), ГН = (/, У), Г1 = (У), Гз' = (г), ГК = (А, С, Е), б) Хг Ха Хз Х4 Ха Ха Хг Ха х, Ха Хз Х4 Ха Хт ') Способ предложен Демукроном (М. !Зешонсгоп). !76 Способ ') нахождения уровней графа без контуров.
Для графа на рис. 110 выпишем его булеву матрицу (рис. 1!4). Образуем строку Ло, выписывая для каждой вершины количество предшествующих ей вершин. В качестве уровня Мо берем Е и Н (им не предшествует никакая вершина). Затем выписываем строку Л,: на местах Е и Н ставим Х, а на остальных — количество вершин, предшествующих данной, исключая Е и Н. Вершины, которым соответствуют нули в строке Лг, составляют уровень й)г. Далее выписываем тем же способом Лм Лж ... и соответствующие уровни г)я, г)з, ... до тех пор, пока это возможно. Тем самым вершины графа распределяются по уровням, как на рис.
111. Если граф содержит контур, то обязательно появится строка Лг без нулей. Отсюда следует, что описанный способ дает возможность установить наличие контуров в графе. УПРАЖНЕНИЯ 28А. Указать порядковую функцию для следующих графов без контуров при условии, что уровень Ма образует вершины, для которых Г Хг=о; А 28Б. То же, что и в упражнении 28А, только М, образуют вершины, для которых ГХ! = Я.
288. Рассмотрим граф а) нз упражнения 28А. Сушествуют ли порядковые функции для графов, получаюшихся из этого графа добавлением дуг: 1) (Р, К), (У, О), (Н, Р); 2) (К, Р), (У, О), (Е, 1); 3) (Н, Р), (Р, У)2 28Г. Определить порядковую функцию Ма = (Х! ) Г Х! = Я) графа О=(Е, (1); Е =(А, В, С, О, Е, Р, О, Н, 1, У, К, 1„М, Н, О, Р, О, )1), 11 = ((А, Н), (А, 1), (В, О), (В, Р), (С, А), (С, Р),(0, К), (Е, Н),(Е О)' (Р, В), (Р, С), (Р, Е), (Р, Н), (О, У.), (Н, 1), (1, У), (К, У), (1., 1), (Е, К) (ЛУ, О), (М, Е), (М, Е), (Н, Е), (Н, М), (О, О), (О, М), (Р, О), (Р, О), (О Н).
(Е К)). 9 29. Функция Гранди Рассмотрим граф сг =(Е, Г) и функцию д, сопоставляющую каждой вершине Хс ~ Е целое число д(Х;))~ О, Будем говорить, что д(Х) есть функция Гранды для графа сх, если в каждой вершине Х; значение д(Х;) представляет собой наименьшее из тех целых неотрицательных чисел, которые не принадлежат множеству (д(Х,) ~ХУ ~ ГХ,), (29.1) и д(Х!)=О, если ГХс= Я. (29.2) Итак, для произвольной вершины Хс имеем д(Х!) = О, если ГХ, = Я, и если ГХ; Ф Я, то д(Хс) равно наименьшему неотрицательному целому числу, не сопоставленному никакой из вершин в ГХь Построим функцию д(Х) для графа на рис. 115 следующим образом: ш (н д(х ))х гх д(В) =О, д(0) = 1, д(Г) =1 д(О) =О д(В) =О д(В) =О, д(К) =О д(а) =о д(в) =о д(А) =2, д(0) =1, д(К) =О д(А) =2 д(ЕО= ! д(Н) =1 17? х! А В С 0 Е Р О Н 1 У К ГХ1 (В, О, Р) Я (О) (В) (В, К) (О) Я (В) (А,0, К) (А) (С, Н) д (х,) 2 О 1 ! 1 ! О 1 3 О О Ог Оо о о ~г) о Рис.
116. Рис. !18. Легко убедиться, сравнивая в таблице столбцы (3) и (4), что д(Х) — функция Грапди. Не всякий граф обладает функцией Гранди. Например, граф на рис. 116 не обладает такой функцией. Функция Гранди не всегда определяется однозначно (рис. 117). Для графа без контуров каждой порядковой функции (она всегда существует) однозначно сопоставляется функция Гранди, если на щть с того, что приписать нуль вершинам, из которых не исходит никакая дуга.
Рассмогриьб, например, граф на рис. 118. Порядковая функция этого графа, изображенная нн $ $ $ $ $ $ $ $ г $ $ 1л $ 1'б )1Т ~б ~5 Иб Иб 112 111 110 Рнс. 119. рис. 119, получается «удалением потомков». Вершинам уровня й)о приписывается О, вершинам уровня 1$1$ приписывается 1, вершинам уровня 1$)з приписывается 2, так как следующим за сг вершинам Г и М приписаны значения О и 1.
Вершине В уровня й1з, предшествующей вершинам 6 и М, следует приписать значение 1 и т. д. УПРАЖНЕНИЯ 29А. Указать функции Гранда для графов нз упражнения 2ВА. 29Б. Указать функпию Гранди для графа пз упражнения 2ВГ, 29В. Найти функцию Гранда для каждого нз следуюгцих графов: Можно ли указать функцию Грандн для графов, которые получаются изменениезг направления всех дуг зтих графов? 179 $30. Внутренняя устойчивость. Внешняя устойчивость Внутренне устойчивое подмножество. Пусть задан граф О = (Е, Г); подмножество 8 с Е называется внутренне устойчивым, если 3() ГВ = О.
(30.!) Другими словами, никакие две вершины 8 не смежны. Если 8'с: 8, то $' — также внутренне устойчивое подмножество. П р имер. Рассмотрим граф на рис. 120. Подмножества 8! — — (А, В, 6'„$в=(В, 6), 8в=(А, С, О, 6) (30.2) внутренне устойчивые. Проверим это, например, для 8,: ГА=(В, Е, Е), Г.0=(Е), ГО=(Н), ГЗ! =ГА() ГВ() ГО= (В, Е, Е, Н), (30.3) В! ПГБг=(А, О, 6) () (В, Е, Е, Н') = О.
Максимальное внутренне устойчивое подмножество. Это— внутренне устойчивое подмножество, не являющееся собственным подмножеством никакого другого внутренне устойчивого подмножества. Например (рис. 121 и 122), подмножества (А, С, В, 6) и (С, Е, Н) максимальные внутренне устойчивые. Очевидно, что граф может обладать несколькими максимальными внутренне устойчивыми подмножествами. Число внутренней устойчивости. А Это число вершин наибольшего из внутренне устойчивых подмножеств. Оно обозначается а(6) = гпах(8г 1, (30.4) агах где Х вЂ” семейство максимальных Ю внутренне устойчивых подмножеств Рис.
120. графа О. Например, для графа на рис. 120 сг(6) = 4. Отыскание семейства максимальных внутренне устойчивых подмножеств (метод Магу' )). Этот метод использует свойства булевых уравнений'). Будем рассматривать графы без петель, так как вершина, имеющая петлю, не может принадлежать внутренне устойчивому подмножеству. ') М а г у (К. М а я Ь оп 1), Арр11санопв г(е РА!яеЬге де Воо!е а 1а ТЬеопе г(ев Огврьев, Саьгегв дп Сеп!ге г)'Е(пг(ев г(е йесьегсье Орьга!!оппе!1е, Вгихе1!ев 6, № 1 — 2 (1963), 21.
') См. П а п е н, К о ф м а н и Ф о р (М. О. Р а р 1 п, А. К а и 1 гп а и п, к. Р а и ге), Соига г(е са!сп! Ьоо!егеп аррпяие, Ег(. А!ып Мике!, Рапи, 196З. гап Пусть 8 — некоторое внутренне устойчивое подмножество. Свяжем с любой вершиной Х, графа булеву переменную х; и положим: если Х~ бй 8, то х, =1 или х; =О, (30.5) Для любой пары вершин Х; и Х; (с учетом (30.1)) справедливо утверждение (1~1; Хе ен ГХ или ") Х)ен ГХ;) =)ь(Х~ Ф 8 или Х Ф 8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
