4. Базы

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

то В является базой тогда и только тогда, когда

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

Итак, базой является такое множество В вершин графа которое удовлетворяет следующим двум условиям:

(i) каждая вершина графа достижима хотя бы из одной вершины множества В и

(ii) в В нет вершины, которая достижима из другой вершины множества В.

Из этих двух условий мгновенно получаются следующие утверждения:

(а) в множестве В нет двух вершин, которые принадлежат одной и той же графа G,

(б) в любом графе без циклов существует единственная база; она состоит из всех таких вершин графа, полустепени захода которых равны 0.

Доказательства этих двух утверждений простые и непосредственно следуют из определений. (См. задачи 2.3 и 2.4.)

Таким образом, в силу утверждений (а) и (б) база В конденсации графа состоит из таких вершин графа полустепени

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

4.1. Пример

Для графа приведенного на рис. 2.2, конденсация показана на рис. 2.3. Базой графа является множество поскольку единственные вершины в с полустепенями захода, равными 0. Базами графа являются и (яд,

Понятие, двойственное понятию базы, можно дать следующим образом на языке контрадостижимых множеств

Антибаза В есть множество вершин графа таких, что

т. e. есть такое минимально возможное множество вершин, что какова бы ни была вершина графа из нее достижима некоторая вершина в В. Свойства антибаз аналогичны свойствам баз, надо только «прямые» понятия заменить на двойственные. Например, соотношения (2.5) эквивалентны двум условиям, подобным приведенным выше, необходимо лишь заменить В на В и сделать другие «двойственные» преобразованиях).

Таким образом, антибаза конденсации есть множество вершин в полустепени исхода которых равны 0, и антибазы самого графа строятся из антибазы графа путем выбора по одной вершине в каждой вершине-множестве антибазы В — подобно тому, как это делалось раньше для баз.

В примере с графом изображенным на рис. 2.2, конденсация (рис. 2.3) содержит только одну вершину с полустепенью исхода, равной 0. Таким образом, антибаза графа есть а антибазами графа являются множества

4.2. Применение к исследованию структуры организаций

Если граф представляет структуру руководства или влияний некоторой организации, то члены каждой сильной компоненты графа имеют равную власть или равное влияние друг на друга, как это может быть, например, для случая комитета. Базу графа можно интерпретировать как «коалицию», включающую наименьшее число лиц, обладающих властью над каждым членом организации [2, 3].

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

где и одна из баз графа и одна из антибаз графа выбранные так, чтобы -число людей в -было минимальным.

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

Следовательно, можно определить сильную базу как такое множество вершин что

и

Вторая часть условия (2.7а) выражает тот факт, что только лица из могут иметь власть над другими лицами, также принадлежащими может быть заменено эквивалентным условием Это условие означает, что если вершина из графа входит в то и каждая вершина из той же самой должна входить в Поскольку база в есть множество таких вершин, полустепени захода которых равны 0, т. е. ни одна из этих вершин не достижима ни из какой другой вершины графа, то сильная база в есть объединение множеств вершин базы

графа

Для графа, приведенного в примере 4.1 (рис. 2.2 и 2.3), сильная база есть Можно отметить, что, если этот граф представляет организацию, то можно рассматривать как руководителя, обладающего властью над всеми множествами лиц в то время как можно рассматривать как комитет, имеющий власть над двумя множествами лиц