Материал: Формальное представление электрических принципиальных схем для решения задач автоматизированного проектирования электронной аппаратуры (120

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Рис. 5.4. Связный граф с несколькими компонентами связности

X1 = {x1,x2,x3,x4}; X2 = {x5,x6,x7,x8}; X3 = {x9,x10,x11}; X4 = {x12}.

При этом справедлива следующая запись:

4

X = Xi, ∩Xi = ,

i=1 i

где i = 1,2,3,4; X — множество вершин графа G.

Можно также сказать, что компонента связности — это связная часть несвязного графа.

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

Частичный граф — это такой граф, у которого по отношению к исходному графу удалены некоторые ребра. Таким образом, граф G будет частичным графом G, если

G = (X,U),G = (X,U ),U U.

Подграф — это такой граф, у которого по отношению к исходному графу удалены некоторые вершины и ребра, им инцидентные. Так, G будет подграфом графа G, если

G = (X,U),G = (X ,U ),X X,U U.

Компоненты связности несвязного графа есть подграфы общего графа.

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

Особый интерес представляют графы-деревья.

21

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

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

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

γ(G) = m − n + k,

где m — число ребер графа; n — число вершин графа; k — число компонент связности (для связного графа k = 1).

Связный граф и образованный из него исключением двух ребер граф-дерево изображены на рис. 5.7.

Графы-деревья обладают следующими свойствами:

1) в дереве две любые вершины связаны единственной цепью;

Рис. 5.7. Виды графов:

a – связный граф; б – граф-дерево

22

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

2)любое дерево имеет хотя бы две концевые вершины и хотя бы одно концевое ребро.

Вершина xi графа G называют концевой, если ρ(xi) = 1, т. е. существует единственное ребро u(xi,xj) с концом в xi. Такое ребро называется концевым;

3)число tn различных деревьев, которые можно построить на n заданных вершинах, рассчитывают по формуле

tn = nn−2;

4) для любого графа-дерева выполняется условие

n − m = 1,

где n — число вершин; m — число ребер; 5) графы-деревья всегда плоские.

Граф называется плоским, если его можно изобразить на плоскости так, чтобы все пересечения ребер происходили только в вершинах. Граф на рис. 5.8 плоский, на рис. 5.9 неплоский.

Применяются место несколько способов представления графа:

1)геометрический;

2)аналитический:

а) в виде отображений и соответствий; б) в виде трехместного предиката или инцидентора; 3) матричный.

Геометрическое представление графа наглядно, но не всегда удобно. Например, при решении задач на ЭВМ вся исходная информация должна быть переведена в математическую форму. Рассмотрим аналитические способы задания графов.

23

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Способ а. Если задано множество вершин X и отображений Γ, то в этом отображении каждой вершине xi X соответствует множество вершин графа, связанных с вершиной xi ребрами.

Отсюда определим граф G = (X, Γ), где Γ = {Γx1 , Γx2 ,..., Γxn}. Для графа, показанного на рис. 5.1, а справедливы следующие

соотношения:

X = {x1,x2,x3,x4,x5}; Γx1 = {x2,x3,x4,x5}; Γx2 = {x1,x4,x5}; Γx3 = {x1,x5};

Γx4 = {x1,x2,x5}; Γx5 = {x1,x2,x3,x4}.

Cпособ б. Граф можно задать также с помощью двух множеств — множества вершин X, множества ребер U и предиката или инцидентора uk, указывающего, какую пару вершин xi;xj X соединяет то или иное ребро uk:

G = {X,U,F},

где X = {x1,x2,...,xn} — множество вершин; U = {u1,u2,..., um} — множество ребер; F = {xi,uk,xj} — предикат графа;

i = 1,n; j = 1,n; k = 1,m.

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

Матрица смежности вершин A — это квадратная матрица размером n×n, где n — число вершин графа. Матрица смежности вершин

A = ||aij||n×n,

где aij — элемент матрицы A, лежащий на пересечении i-й строки и j-го столбца, i,j = 1,n, причем

1, если xi R xj;

0, если xi R xj,

где R — бинарное отношение.

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

24

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Матрица смежности ребер W — это квадратная матрица размером m × m, где m — число ребер графа. Матрица смежности ребер

W = ||uij||m×m,

где uij — элемент матрицы W, лежащий на пересечении i-й строки и j-го столбца, i,j = 1,m, причем

Матрица инцидентности S — это прямоугольная матрица размером m×n, где n — число вершин графа; m — число ребер графа. Матрица инцидентности

S = ||sij||n×m,

где sij — элемент матрицы S, лежащий на пересечении i-й строки и j-го столбца, i = 1,n; j = 1,m, причем