Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 [ 11 ] 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

4. Базы

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

i?(5)= (0 (2.3)

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

R{B) = X и У8с1Б(Б(8)фХ). (2.4)

Второе условие {R {S) ф X У8<пБ) в соотношении (2.4) эквивалентно утверждению: xj $ R (xi) для любых двух различных Xi, Xj 6 Б, т. е. вершина из Б не достижима из любой другой вершины В. Эта эквивалентность может быть обоснована следующим образом. Поскольку для любых двух множеств Н и Н'Н мы имеем, что R (Я') Е R (Я), то условие R (S) ф X У8 cz Б эквивалентно соотношению R (Б - {xj}) ф X для всех Xj 6 Б; другими словами, R (xj) ф R {В - {Xj}). Последнее условие может быть выполнено тогда и только тогда, когда Xj R {Б - - {xj}), т. е. тогда и только тогда, когда Xj R (х;) для любых Xi, Xj 6 в.

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

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

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

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

(а) в множестве Б нет двух вершин, которые принадлежат ОДНОЙ и ТОЙ же СК графа G,

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

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

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

1) Или вершинная база.- Прим. ред.



38 ГЛ. 2. достиншмость и связность

захода которых равны 0. Следовательно, базы графа G можно строить так: из каждой СК графа G, соответствующей вершине базы В* конденсации G* надо взять по одной вершине, т. е. если В* = {Si, S, . . ., Sm}, где т - число вершин-множеств Sf в базе В* графа G*, то базой В является произвольное множество {Xi, xi, . . ., XiJ, где xi. 6 Sj.

4.1. Пример

Для графа G, приведенного на рис. 2.2, конденсация G* показана на рис. 2.3. Базой графа G* является множество {х*, х%), поскольку хХжх* - единственные вершины в G* с полустепенями захода, равными 0. Базами графа G являются {х^, х^, {х^, arJ и {жз, ж^з}.

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

Антибаза В есть множество вершин графа G = {X, Г), таких,

что

<?(5)= \] Q{Xi) = X

yS B,Q{S)X,

(2.5)

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

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

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

) Условие, двойственное условию (i), формулируется, например, так: из любой вершины графа G достижима хотя бы одна вершина множества В.- Прим. ред.



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

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

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

H = B{G)[jB{G), (2.6)

где В (G) и в {G) - одна из баз графа G и одна из антибаз графа G\ выбранные так, чтобы \Н \-число людей в Н-было минимальным.

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

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

R (Bp) = X, (? (Bp) = Bp (2.7а)

и

В{8)ФХ V5ci Bp. (2.76)

Вторая часть условия (2.7а) выражает тот факт, что только лица из Bp могут иметь власть над другими лицами, также принадлежащими Bp, и может быть заменено эквивалентным условием R {X -Бр) П Bp = 0. Это условие означает, что если вершина из СК графа G входит в Bp, то и каждая вершина из той же самой СК должна входить в Bp. Поскольку база в G* есть множество таких вершин, полустепени захода которых равны О, т. е. ни одна из этих вершин не достижима ни из какой другой вершины графа, то сильная база в G есть объединение множеств вершин базы гра-

) В оригинале power-basis .- Прим. ред.



1 2 3 4 5 6 7 8 9 10 [ 11 ] 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95