База и ядро

Пусть G — ориентированный граф, а В — такое под­множество его вершин, что любая вершина из VG\B до­стижима из какой-либо вершины, принадлежащей В. Если, к тому же, множество В минимально относительно включения среди всех подмножеств вершин с описанным свойством, то оно называется базой орграфа С.

Очевидно, что в любом орграфе существует база и что никакие две вершины базы не соединены маршрутом.

Поскольку вершины с нулевыми полуступенями за­хода не достижимы ни из каких вершин, то все они при­надлежат базе. В бесконтурном орграфе база состоит только из таких вершин.

Для поиска базы в орграфе G, содержащем контуры, рассмотрим его конденсацию G*, не имеющую контуров согласно утверждению 63.3. Сильные компоненты оргра­фа G, в которые не входят дуги из других сильных компо­нент, соответствуют в орграфе G* вершинам с нулевыми полустепенями захода. Назовем такие сильные компонен­ты базовыми. Все вершины каждой сильной компоненты взаимно достижимы и любая вершина небазовой компо­ненты достижима из любой вершины некоторой базовой компоненты. Таким образом, доказана

Теорема 67.1. Подмножество вершин В орграфа является базой тогда и только тогда, когда В состоит из вершин, принадлежащих базовым компонентам, причем в каждую базовую компоненту входит ровно одна вер­шина из В.

Понятие ядра для ориентированных графов вводится так же, как и для неориентированных.

Множество S вершин орграфа G называется домини­рующим, если для любой вершины w VG\S существует такая вершина v S, что (v, w) AG. Напомним, что множество S называется независимым, если никакие две

вершины из S не смежны. Множество вершин S, являю­щееся одновременно и независимым, и доминирующим, называется ядром орграфа.

Орграф, изображенный на рис. 67.1, имеет два ядра:

Не в каждом орграфе есть ядро, в чем нетрудно убе­диться, рассмотрев орграф, изображенный на рис. 67.2.

Рассмотрим одно достаточное условие существова­ния ядра.

Теорема 67.2. Каждый орграф, не имеющий кон­туров нечетной длины, обладает ядром.

> Пусть G — орграф, в котором нет контуров нечет­ной длины. Для любого подмножества вершин W<=VG положим

Определим рекуррентно

две системы подмножеств В₀, В₁,В₂,... и V₀, V₁, V₂,... множества VG. В качестве В_о возьмем любую из баз орграфа G и положим

Пусть уже определены В_i-1 и V_i. В качестве В_i возьмем какую-либо базу подграфа Gi = G—V_i, удовлетворяю­щую условию

и положим

Покажем, что нужная база действительно существует. Пусть В — база в G_i содержащая вершину v Г(Г(B_i-1)\V_i-1). Поскольку В_i-1 — база в G_i-1, то вер­шина v достижима из какой-либо вершины w B_i-1, и в графе G_i-1 существует (w, и)-путь L (рис. 67.3).

Этот путь содержит по меньшей мере по одной вершине из Г(B_i-1) и из Г(Г(B_i-1)\V_i-1). Пусть и — последняя вер­шина пути L, принадлежащая можеству Г(Г(B_i-1)\V_i-1). Тогда все вершины, достижимые из вершины v, достижи­мы и из и, т. е. В' =(B\v)U и — также база. Будем про­водить такие замены вершин до тех пор, пока не полу­чим нужную базу Bi. Поскольку

и множество VG конечно, то для некоторого индекса m верно равенство V_m = VG. Положим

и покажем, что S — ядро орграфа G. Из построения мно­жества S вытекает, что оно доминирующее, ибо если v S, то v Г(B_k)\V_k для некоторого индекса k.

Осталось показать, что множество S независимо. Пусть, напротив, в S есть две смежные вершины и и v, и В_р, v B_р. Так как в базе смежных вершин нет, то р <> q. Будем считать, что р < q. Из правила построения множеств Bj следует, что (и, v) AG, (v, u) AG. По этой же причине существует путь

(рис. 67.4), где

из минимальности базы В_р следует равенство и — х_р. Но когда путь L оказывается контуром нечетной длины, что противоречит условию теоремы.

Тем самым доказана независимость множества S.

Итак, множество S является независимым и доминирующим одновременно, т. е. S — ядро. <