Однородные графы. Мера неоднородности

Граф G называется однородным k-связным, если, его вершинная связность æ(G) = k и все степени вершин d_i = k. Такие графы обладают наибольшей связностью, а следовательно и живучестью при прочих равных условиях.

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

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

Поскольку свойства связности для сетей связи является определяющим то представляет интерес, в какой мере связность у различных структур при заданных m и n отличается от оптимальной, получаемой по рассмотренным алгоритмам, реализующим максимальную однородность графов.

Для определения степени неоднородности графа введем меру, аналогичную дисперсии при рассмотрении случайных величин:

(1)

Где: .

Рис.5. Пример неоднородного (G₁) и однородного(G₂) 3^-х-связного графов.

Например, для графовG₁ и G₂ на рис.2.5 с m=9 и n=6 у графа G₁dcp = 3; D = 1,67; связность λ=1; для графа у графа G₂d_i = dcp = 3; D = 0; λ=3.

Для типовых и преобразованных по алгоритму синтеза оптимальных структур сравнительные данные приведены в таблице. В числителе для типовых, в знаменателе – для преобразованных с таким же числом вершин n и ребер m.

Таблица 1.

	Тип структуры	Количество вершин n	Количество ребер m	dср	D	λ(G)	Количество остовных деревьев Т	Количество независимых остовных деревьев Тн
	Древовидная
	Радиально-узловая
	Алмазная
	Решетка
	Сотовая

В таблице в качестве показателей связности использовались: реберная связность λ(G), количество независимых остовных деревьев Т_н, количество остовных деревьев Т.

Количество независимых остовных деревьев определяется как Т_н=m/(n-1) и изменяется от 1 до n/2, количество остовных деревьев изменяется от 1 до достаточно широких пределов и определяется по известной методике, реберная связность изменяется в пределах от 1 до n-1 для полносвязного графа.

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

Задача генерирования графов с различной степенью неоднородности заключается в разбиении числа 2m на суммы из n членов, каждый из которых равен степени i-ой вершины d_i(i=1,2…n) при этом d_imax ≤n-1, поскольку граф простой, а d_imin ≥1, поскольку граф связен.

Как отмечалось ранее последовательность П={d₁, d₂,..,d_n } во- первых должна быть графической, во- вторых упорядочена так, чтобы

n-1≥d₁≥d₂…..≥d_n≥1 (1)

Возьмем в качестве примера граф, у которого число вершин n=12, число ребер m=36.

Наибольшим разнообразием обладает множество, в котором наибольшее число членов отличаются друг от друга. В нашем примере n членов могут принимать значение от 1 до n-1, стало быть два члена одинаковы и находятся в средине вариационного ряда (1)

Наименьшим разнообразием обладает последовательность, у которой все степени равны друг другу:

d_iср=d_cр=2m/n=const (2)

Уменьшение разнообразия неоднородности производится так, чтобы уменьшалось отличие степеней от среднего значения.

Наибольшим отличием обладают крайние члены вариационного ряда (1). Поэтому суть алгоритма заключается в добавлении единицы к минимальной степени и вычитание единицы из максимальной до тех пор, пока не будет достигнуто равенство d_imin= d_imax= d_cр.

Перечень последовательностей П_i для n=12 и m=36 приведен в таблице. Каждая из последовательностей проверяется на графичность, после чего по этой последовательности строится граф по одному из приведенных ранее алгоритмов ℓ-процедуры.

Таблица 2.

№ Пi	Степени вершин	Характеристики Степени Неоднородности	Верхняя граница количества вариантов ф(2.8)	Количество вариантов с учетом особенностей алгоритма
Di	количество остовов		N
													9,17
													7,7
													6,5
													5,3
													4,5
													3,67
													2,83
													2,33
													1,83
												4	1,33
													0,833
													0,666
													0,5
													0,33
													0,166

Пошаговое выполнение ℓ-процедуры с максимальным ведущим элементам для последовательности П₍₁₎= 11, 10, 9, 8, 7, 6, 6, 5, 4, 3, 2, 1 приведено в таблице 2, а примеры построения по такой же процедуре графов для последовательностей П_i для i=1,7,8 и 16 приведены на рис.6.

I zUvOT8nMS7dVCg1x07VQUiguScxLSczJz0u1VapMLVayt+PlAgAAAP//AwBQSwMEFAAGAAgAAAAh AGimpLjDAAAA3AAAAA8AAABkcnMvZG93bnJldi54bWxET0trAjEQvhf8D2GEXkSzeqi6GkVLFXso xdd92Iy7q5tJ2ERd/30jCL3Nx/ec6bwxlbhR7UvLCvq9BARxZnXJuYLDftUdgfABWWNlmRQ8yMN8 1nqbYqrtnbd024VcxBD2KSooQnCplD4ryKDvWUccuZOtDYYI61zqGu8x3FRykCQf0mDJsaFAR58F ZZfd1Sj4TvbX9fh3/HVe//jV8ez6HbeslHpvN4sJiEBN+Be/3Bsd5w8H8HwmXiBnfwAAAP//AwBQ SwECLQAUAAYACAAAACEABKs5XgABAADmAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQAIwxik1AAAAJMBAAALAAAAAAAAAAAAAAAAADEBAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQAzLwWeQQAAADkAAAASAAAAAAAAAAAAAAAAAC4CAABkcnMv cGljdHVyZXhtbC54bWxQSwECLQAUAAYACAAAACEAaKakuMMAAADcAAAADwAAAAAAAAAAAAAAAACf AgAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA9wAAAI8DAAAAAA== ">

i=1 i=16

i=7 i=8

Рис.6. Графы последовательностей П_i i=1,7,8 и 16

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

Для каждой из конкретных реализаций графы по последовательностям П_ii=1,16 вычислены такие показатели связности как число остовных деревьев и мера неоднородности.

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