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

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

Пересечение нескольких множеств можно записать так:

k

∩ Xi = B, где i = 1,2,...,k.

i=1

Разностью множеств A и B называют множество F, любой элемент которого принадлежит множеству A и не принадлежит множеству B. Разность множеств F обозначают F = A\B, где \ — знак разности множеств. Например, если A = {a,b,c}, B = {b,d}, то D = A\B = {a,c}.

Введем понятия квантора существования и квантора общности. Знак называют квантором существования (читается «существует»). Знак называют квантором общности (читается «для любого»). Запись ( xi X) B(xi) означает, что для любого элемента xi из множества X истинно высказывание B(xi) об элементе xi. Весьма существенным является понятие разбиения множества. Систему M{Ai} множеств Ai,i I, называют разбиением множества X, если оно удовлетворяет трем условиям:

1)Ai = ,i I — ни одно множество, являющееся элементом системы M, не пусто;

2)Ai ∩ Aj = , i =j — пересечение любых двух неравных множеств, принадлежащих M, является пустым;

k

3) oбъединение всех Ai составляет множество X: Ai = X.

i=1

Например, пусть X = {a,b,c,d,e,f,k}, тогда система множеств

M = {A1,A2}, где A1 = {a,c,f} и A2 = {b,d,e,k}, являются одним из возможных разбиений множеств. Легко заметить, что

можно получить большее число различных вариантов множеств. Чтобы определить отношение между элементами внутри од-

ного множества, рассматривают бинарные (попарные) структуры элементов.

Наличие бинарного отношения между элементами xi и xj записывают следующим образом: xiRxj; причем xi X, xj X.

Каждое отношение R имеет дополнительное отношение R

(или отрицание), так, что xiRxj тогда и только тогда, когда не выполняется условие xiRxj.

Наличие бинарных отношений между некоторыми или всеми элементами одного множества удобно представить графом.

16

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

5.2. Основные понятия и определения теории графов

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

Таким образом, граф можно описать выражением

G = (X,U),

где X = {x1,x2,...,xn}— множество вершин; U = {u1,u2,...,un}

— множество ветвей.

Запись uij означает, что ветвь графа образована парой вершин

xi и xj: uij = (xi,xj), xi X,xj X.

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

Произвольный граф

G = (X,U),

где X ={x1,x2,x3,x4,x5}; U ={(x1,x2),(x1,x3),(x1,x4),(x1,x5),

(x2,x4),(x2,x5),(x3,x5),(x4,x5)}, показан на рис. 5.1, а.

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

Ненаправленные отношения между элементами одного мно-

жества называются ребрами и обозначаются . Граф, все ветви

U

которого представляют собой ребра, называется ненаправленным, или неориентированным (см. рис. 5.1, а).

Направленные отношения между элементами называются ду-

гами и обозначаются . В этом случае говорят о направленном,

U

или ориентированном, графе (рис. 5.1, б).

Если в графе содержатся и дуги, и ребра, то граф называется смешанным (рис. 5.1, в).

17

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

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

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

Две вершины графа называются смежными, если существует ребро uij U, соединяющее эти вершины. Говорят, что ребро uij инцидентно вершинам xi и xj, если оно связывает эти вершины. В свою очередь, вершины xi и xj инцидентны ребру uij. Два ребра называются смежными, если существует вершина, инцидентная обоим ребрам.

Количество ребер (или дуг), инцидентных одной вершине, определяет ее локальную степень. Например, в графе, показанном на рис. 5.1, а, локальная степень вершины x1

ρ(x1) = 4,

а локальная степень вершины x2

ρ(x2) = 3,

и т. д.

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

G0 = (X,U), где X = {x1,x2,...,xn}, U = .

Часто приходится встречаться с понятием полного графа. Полный граф — это тот граф, любая вершина которого имеет отношения со всеми остальными:

Gп = (X,U), где X = {x1,x2,...,xn},

18

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

Если в графе любые две вершины соединены более чем одним ребром, то такой граф называется мультиграфом; ребра, соединяющие одну и ту же пару вершин, — кратными ребрами, а наибольшее число кратных ребер, соединяющих какую-либо пару вершин — мультичислом. Мультиграф G = (X,U), мультичисло которого m = 5, представлен на рис. 5.2, а. Обычно мультиграф изображают в виде скелетного графа, у которого над соответствующими связями указана кратность (рис. 5.2, б).

ние множества его вершин на p непересекающихся подмножеств

p

X1,X2,...,Xp; X = Xi; Xi∩Xj = ; i =j; i,j {1,2,...,p},

j=1

при котором каждое подмножество Xi не содержит смежных вершин, т. е. XiB(xi Rxj). Если каждому подмножеству Xi поставить в соответствие определенную «краску», то вершины этого подмножества можно окрасить в один цвет, вершины другого — в другой цвет и т. д. Иными словами, любая пара смежных вершин окрашивается в разные цвета.

Наименьшее число подмножеств, на которое можно разбить множество вершин графа при раскраске, называется хроматическим числом ξ(G) графа G. Например, множество вершин графа (рис. 5.3) можно разбить не менее чем на три непересекающихся подмножества:

X1 = {x1,x3,x6}, X2 = {x2,x4}, X3 = {x5}.

19

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

Следовательно, хроматическое число рассматриваемого графа ξ(G) = = 3 и граф можно раскрасить тремя красками.

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

Последовательность ребер U1U, заданных парами вершин вида

(x0,x1),(x1,x2),...,(xi−1,xi), в которой любые два соседних ребра смежные, называется маршрутом.

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

Для ориентированных графов справедливы понятия как ориентированных цепей и циклов, так и неориентированных. В первом случае при рассмотрении цепи или цикла дуги проходят только в направлении их ориентации, во втором ориентация во внимание не принимается. Ориентированную цепь иногда называют путем, а ориентированный цикл — контуром. Две вершины xi,xj X, где i =j, графа G = (X,U) называются связными, если их можно соединить маршрутом. Граф G = (X,U) называется связным, если любые две его вершины связаны маршрутом (см. рис. 5.1, а). Взяв какую-либо вершину xi X графа G = (X,U) и построив подмножество X X, состоящее из всех вершин, которые можно соединить с xi произвольным маршрутом, причем xi включается в X , можно получить подграф G = (X ,U ), образованный на множестве вершин X , который называется компонентой связности графа G. Заметим,что связный граф состоит из единственной компоненты связности. Если граф имеет несколько компонент связности, то он не связан, поскольку вершины из разных компонент связности нельзя соединить маршрутом. Так, для графа, показанного на рис. 5.4, можно назвать четыре компоненты связности:

20