Глава 3. Основы теории графов

 

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

Первая работа по теории графов была опубликована математиком Л. Эйлером в 1736г. в Трудах Академии наук Санкт-Петербурга в виде задачи о Кенигсбергских мостах.

 

 

Суть задачи сводилась к следующему: мог ли житель Кенигсберга, выйдя из дома, находящегося на части суши (например, A, B, С или D), пройти по семи мостам города через реку Прегель в точности по одному разу и вернуться домой? Ответ на этот вопрос был отрицательным.

Для пояснения задачи представлена модель части города, прилегающей к реке Прегель (см. рис. 3.1), где каждый участок суши замещен точкой на плоскости, а мосты – линиями, связывающими участки суши.

Граф и его характеристики

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

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

Граф может быть задан в двух формах:

а) G=<X, r>,

где r={r_i=(x_i, x_j)| x_i, x_jÎX}Í(XÄX) есть отношения между вершинами графа,

б) G=<X; h>,

где h(x_i)={x_j| x_jÎX} есть множество вершин графа, смежных вершине x_i.

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

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

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

Граф называют неориентированным, если (x_i, x_j)=(x_j, x_i). Отрезок линии (x_i; x_j), соединяющий две вершины неориентированного графа, называют ребром.

Граф G=<X; r> называют ориентированным, если

(x_i, x_j)¹(x_j, x_i), а направленный отрезок линии (x_i; x_j), соединяющий две вершины, называют дугой.

На рис. 3.2. приведены неориентированный и ориентированный графы.

Любая программа или алгоритм вычислительного процесса, электронная схема или последовательность операций производственного процесса могут быть представлены ориентированным графом, а любая схема транспортной или электрической сети - неориентированным.Поскольку при описании графа используют элементы множеств вершин и отрезков линий, то для определения отношения принадлежности вершины графа отрезку линии и, наоборот, отрезка линии - вершине вводится понятие “инциденция”. Говорят, что вершина x_i инцидентна ребру или дуге (x_i, x_j), если она является концевой вершиной данного отрезка линии, а ребро или дуга (x_i, x_j) инцидентна вершине x_i, если отрезок линии ограничен концевой вершиной x_i. Число вершин, инцидентных ребру или дуге, всегда равно 2, т.к. они являются концевыми вершинами отрезка линии, а число рёбер или дуг, инцидентных вершине x_i, может быть произвольным. Число ребер, инцидентных вершине x_i, называют степенью или валентностью вершины и обозначают

s_i= .

Число дуг, исходящих из вершины x_i, называют полустепенью вершины графа и обозначают s_i⁺= .

Вершину x_i, инцидентную исходящей дуге (x_i, x_j), называют истоком (символ ”⁺” отмечает вершину-исток).

Число дуг, заходящих в вершину x_i, также называют полустепенью вершины графа и обозначают s_i^-= .

Вершину x_i, инцидентную заходящей дуге (x_j, x_i)^-, называют сто ком (символ ”^-” отмечает вершину-сток).

Две вершины графа называются смежными, если они различны и между ними существует ребро или дуга.

Вершина x_i, несмежная ни с одной вершиной графа, называется изолированной. На рис. 3.2. такой вершиной является x₂ .

Два ребра называются смежными, если они различны и имеют общую вершину.

Граф называют полным, если любые две его вершины смежны между собой (см. рис. 3.3a) и пустым, если любые две его вершины не смежны (см. рис.3.3b).

Полный подграф некоторого графа называют кликой этого графа. В матрице смежности этого графа клика формирует единичный блок.

Граф называют дополнительным для графа G=<X; r>, если он опирается на множество вершин исходного графа и дополнение отношения r, т. е. ùG=<X;`r> (см. рис. 3.4).

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

 

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

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

В графе типа дерево (см. рис. 3.5) всегда выделяют корневую вершину - J, узлы - прописные буквы латини- цы { A, B, C,..} и крону - строчные буквы латиницы { a, b, c,..}. Число дуг дерева всегда равно (n-1), где n - число вершин графа.

Вершинной связностью. графа G=<X; r> называют наи- меньшее число вершин, удаление которых приводит к несвязному графу. Например, если на рис. 3.5 удалить вершину J, то будет сформировано три дерева. Множество несвязных деревьев называют “лес”.

Реберной связностью графа G=<X; r> называют наимень- шее число ребер, удаление которых приводит к несвязному графу.

 

Если множество вершин графа G=<X; r> разбить на два подмножества X’ и X\X’ при условии, что X’È(X\X’)=X и X’Ç(X\X’)=Æ, то множество рёбер или дуг, одни из концевых вершин которых принадлежат множеству X’, а другие - множеству (X\X’), называют разрезом. Поиск разрезов сводится выделению множества рёбер, соединяющих эти подмножества.

Пусть на рис. 3.6 дан граф G=<X; r>, где X={x₁, x₂,..x₈}, а

r={r₁, r₂,..r₁₁}. По условиям задачи выделено подмножество

X’={x₁, x₂, x₆, x₈}. Тогда X\X’={x₃, x₄, x₅, x₇}.

Разрезом является множество ребер {r₂, r₁₁, r₇ }, которые выделены на рисунке полужирными линиями. Удаление разреза преобразует связный граф в несвязный. Так на рис. 3.7 изображены два связных подграфа графа, представленного на рис. 3.6, в результате удаления ребер разреза.

Последовательность смежных рёбер или дуг, соединяющих вершины xi и xj, называют маршрутом и обозначают m(i, j)=((x_i, x_k);…... (x_l, x_j)). Например, для неориентированного графа (см. рис. 3.2) между вершинами x₀ и x₅ существует шесть маршрутов, т.е. m₀₅={(r₀₄, r₄₅); (r₀₁, r₁₄, r₄₅); (r₀₁, r_1,5); (r₀₄, r₄₁, r₁₅); (r₀₄, r₄₁, r₁₃, r₃₅); (r₀₁, r₁₃, r₃₅)}.

Последовательность смежных вершин, соединяющая вершины x_i и x_j , называют переходом и обозначают n(i, j)=(x_i,..x_j). Например, для неориентированного графа (см. рис. 3.2) между вершинами x₀ и x₅ существует шесть переходов, т.е. n(0, 5)={(x₀, x₄, x₅); (x₀, x₁, x₄, x₅); (x₀, x₁, x₅); (x₀, x₄, x₁, x₅); (x₀, x₄, x₁, x₃, x₅); (x₀, x₁, x₃, x₅)}.

Маршрут неориентированного графа, связывающий вершины x_i и x_j, называют цепью, а ориентированного - путём.

Маршрут называют открытым, если его концевые вершины различны, и замкнутым, если его концевые вершины совпадают.

Замкнутый маршрут неориентированного графа называют циклом, а ориентированного - контуром.

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

Замкнутый маршрут, который содержит только одно ребро или дугу, называют петлёй. На рис. 3.2 петля указана для x₄.

Маршрут называют эйлеровым, если он замкнут и проходит через каждое ребро графа только по одному разу. На рис. 3.8a) эйлеровым маршрутом является m(0, 0)=(r₀₄, r₁₄, r₁₅, r₃₅, r₁₃, r₀₁)}.

Граф G=<X; r> является эйлеровым тогда и только тогда, когда он связан и степень каждой вершины s_i есть четное число.

Маршрут называют гамильтоновым, если он замкнут и проходит через каждую вершину графа только по одному разу.

Таким на рис. 3.8b) является маршрут m(0, 0)=(r₀₄, r₄₅, r₃₅, r₁₃, r₀₁)}.

Длина маршрута равна числу смежных рёбер, соединяющих вершины x_i и x_j , т.е. l(i, j)=Sr_k,l, где k¹l и i£k,l£j.

Длину минимального маршрута, соединяющего вершины x_i и x_j называют расстоянием. Например, расстояние между вершинами x₀ и x₅ графа на рис.3.8b) равно 2.

Если ребро или дуга обладают дополнительной характеристикой – протяжённостью – l(k, t), то длина маршрута равна сумме длин рёбер или дуг, его составляющих, т.е. l(i, j)=Sl(k, t), где k¹t и i£k,t£j.

Если ребро или дуга обладают дополнительной характеристикой - пропускной способностью – C(k, t), то пропускная способность маршрута равна минимальной пропускной способности ребра или дуги маршрута.

Существует несколько типов графов, сформированных на подмножествах вершин или ребер заданного графа.

Граф G’=<X’; r’> называют подграфом графа G=<X; r>, если он опирается на подмножество вершин исходного графа, т.е. X’ÍX, и инцидентных им рёбер.

 

На рис. 3.9 приведен граф а) и его подграф b). Подграф задан подмножеством вершин X¢={x₁, x₂, x₃, x₅}ÍX вместе с инцидентными им ребрами r’= {r₁, r₂, r₃, r₄, r₇, r₈}Í.r.

Граф G’=<X’; r’> называют частичным для графа G=<X; r>, если он использует подмножество рёбер исходного графа, т.е. r’Ír, и инцидентные им вершины.

На рис. 3.9. приведен граф а) и частичный граф с). Частичный граф задан подмножеством рёбер r’={r₁, r₇, r₈}Ír вместе инцидентными им вершинами X’={x₁, x₂, x₃, x₅}ÍX.

Граф G’=<X; r’> называют суграфом для графа G=<X; r>, если он использует подмножество рёбер исходного графа, т.е. r’Í r, и все вершины исходного графа.

На рис. 3.9. приведен граф а) и его суграф d). Суграф задан подмножеством рёбер графа r’={r₁, r₇, r₈, r₉}Ír и множеством вершин исходного графа X={x₁, x₂, x₃, x₄, x₅}ÍX.

Суграф G’=<X’; r’>, формируемый без циклов, петель и кратных рёбер, называют остовом графа G=<X; r>.

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

На рис. 3.10 приведены для сравнения планарный и непланарный графы. У непланарного графа ребро (x₁, x₃) при любой трассировке будет пересекать ребро (x₂, x₄) или (x₀, x₂), а ребро (x₂, x₄) – пересекать ребро (x₁, x₃) или (x₀, x₃).

 

 

Граф G=<X;r> называют двудольным, если его множество вершин может быть разбито на два непересекающихся подмножества X’ и X\X’ так, что каждое ребро графа G соединяет две вершины из разных подмножеств. Граф является двудольным тогда и только тогда, когда все его циклы имеют четную длину.

Граф G=<X;r> называют взвешенным, если его рёбра или вершины имеют дополнительные характеристики.

На рис. 3.11а). приведен реберно-взвешенный граф. Дополнительными характеристиками каждого ребра могут быть объем передаваемой информации или стоимость ее передачи, протяжённость или пропускная способность ребра. Каждому ребру графа приписана условная характеристика – вес.

На рис. 3.11b). приведен вершинно-взвешенный граф. Дополнительными характеристиками каждой вершины могут быть время исполнения команды или оператора программы, вероятность наступления события или надёжность эксплуатации узла и т.п. Каждой вершине графа приписана условная характеристика – вес.

 

Описание графа

Граф может быть задан списком или матричными структурами.

Списки. При описании графа списками используют модели G=<X; r> и G=<X; h>.

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

В таблице 3.1 приведены характеристики графа, описанного рис.3.11а) по модели G=<X; r>.

Таблица 3.1.
ri	r1	r2	r3	r4	r5	r6	r7
(xi, xj)	(x1,x2)	(x5,x6)	(x2,x5)	(x2,x3)	(x1,x4)	(x3,x4)	(x3,x6)
l(ri)

 

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

В таблице 3.2.приведены характеристики графа, описанного рис.3.11b) по модели G=<X; h>.

Таблица 3.2
xi	x1	x2	x3	x4	x5	x6
h(xi)	x2, x3, x4	x1, x3, x5	x1, x4, x6	x1, x3	x2, x6	x3, x5
p(xi)	0,9	0,8	0,8	0,6	0,8	0,9

 

При описании графа матрицами используют, прежде всего, матрицы инциденции и матрицы смежности

Матрица инциденции. Поскольку инциденцияесть отношение принадлежности элемента одного множества другому, то для графа G=<X, r> матрица инциденции ||q|| фиксирует эту принадлежность элемента множества r элементу множества X на множестве {0, 1}. Строки матрицы есть элементы множества r, а столбцы – элементы множества X. Элементы матрицы инциденции неориентированного графа определяются по формуле:

 

1, если r_i=(x_i, x_j) инцидентно x_j,

q(i. j) =

0, в противном случае.

В каждой строке матрицы количество единиц равно двум, а в каждом столбце - степени вершины - s_i .

В таблице 3.3. приведена матрица инциденции для неориентированного графа, представленного на рис. 3.2.

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

Таблица 3.3.
q	x0	x1	x2	x3	x4	x5
r01
r04
r13
r14
r15
r35
r44					1
r45
s

Элементы матрицы инциденции для ориентированного графа определяют по другой формуле:

+1, если r_i,j исходит из вершины x_i;

q(i. j)= 0, если r_i,j не инцидентна вершинам x_i и x_j;

-1, если дуга r_i,j заходит в вершину x_j.

 

В таблице 3.4 приведена матрица инциденции для ориентированного графа, представленного на рис. 3.2.

 

Таблица 3.4.
q	x0	x1	x2	x3	x4	x5
r01	+1	-1
r04	+1				-1
r13		+1		-1
r14		+1			-1
r15		+1				-1
r35				+1		-1
r44
r45					+1	-1
s+
s-

В каждой строке сумма “+1” и “-1” равна нулю, т. к. “+1” представляет вершину – исток, а “-1” вершину – сток.

При задании ориентированного графа с петлями рекомендуется расщеплять вершину с петлей на две вершины: вершину-исток и вершину-сток,

В каждом столбце матрицы число “+1” равно полустепени исхода вершины x_i, т.е. s_i ⁺, а число “-1” равно полустепени захода вершины x_i , т.е. s_i ^-.

М атрица смежности. Поскольку смежность есть отношение между элементами одного множества, то матрица смежности ||r_i,j|| есть квадратная матрица, число строк и столбцов которой равно мощности множества |X|=n.

Элементы матрицы смежности определяются соотношением

 

1, если x_i смежна x_j;

r(i, j) =

0, в противном случае.

В таблице 3.5 представлена матрица смежности для неориентированного графа (см. рис. 3.2а).

Петля у вершины x₄ формирует “1” на диагонали матрицы (x_i, x_j). В таблице можно выделить дополнительную строку или столбец для хранения информации о степени каждой вершины графа.

 

.

Таблица 3.5
r	x0	x1	x2	x3	x4	x5	si
x0
x1
x2
x3
x4
x5
si

 

В таблице 3.6 представлена матрица смежности для ориентированного графа (см. рис. 3.2b), но при условии, что строки заданы вершинами-истоками, а столбцы - вершинами-стоками.

.

Таблица 3.6
r	x0	x1	x2	x3	x4	x5	si+
x0
x1
x2
x3
x4
x5
si-

Поэтому итоговый столбец таблицы - s_i⁺ показывает полустепени вершин-истоков, а итоговая строка - s_I^- - полустепени вершин-стоков.

По матрицам смежности можно сделать следующие выводы:

· каждый ненулевой элемент главной диагонали соответствует петле на графе;

· матрица смежности для неориентированного графа симметрична относительно главной диагонали;

· матрица смежности для ориентированного графа несимметрична относительно главной диагонали;

· столбец ориентированного графа, все элементы которого имеют значение “0”, соответствует вершине-истоку всего графа (см. таблицу 3.6);

· строка ориентированного графа, все элементы которой имеют значение “0”, соответствует вершине-стоку всего графа (см. таблицу 3.6).

Матрица весов. Матрица весов вершинно-взвешенного графа есть матрица-столбец, число строк которой равно числу вершин n, а позициями – значение веса вершины:

.

Матрица весов реберно-взвешенного графа есть квадратная матрица, число строк и столбцов которой равно числу вершин графа. Позиции матрицы весов (x_i, x_j) при i¹j определяются соотношением:

0, если i=j;

L(i, j) = l_i,j, если вершина x_i смежна вершине x_j и вес ребра l_i,j;

¥, если вершина xi несмежна вершине xj.

В таблице 3.7 дана матрица весов для графа на рис. 3.11а).

Таблица 3.7
	L	x1	x2	x3	x4	x5	x6
x1			µ		µ	µ
x2				µ		µ
x3	µ				µ
x4		µ			µ	µ
x5	µ		µ	µ
x6	µ	µ		µ

Матрица достижимости. Поскольку h(x_i) есть множество вершин, которые смежны вершине x_i, или “окрестность” вершины x_i, или достижимы из x_i за “один шаг”, то отображение h(h(x_i))=h²(x_i) есть вершины графа, достижимые из x_i за “два шага” через вершины, сформированные на “первом шаге”. Отображение h(h(h(x_i)))=h³(x_i) есть вершины, достижимые из вершины x_i за ”три шага” через вершины, сформированные на втором шаге. Так как любая вершина связного графа должна быть достижима за p£n “шагов”, то множество вершин достижимых из вершины x_i за это число “шагов” может быть представлено в виде:

q^p(x_i)=IÈh(x_i)È h²(x_i) È..Èh^p(x_i),

где I –диагональ матрицы.

Для построения матрицы достижимости удобно использовать матрицу смежности, т.е.

||q^p||=IÈ||r||È||r²||È||r³||È..È||r^p.

Для возведения в степень матрицы смежности используют правило умножения булевых матриц:

r_i,j²=_k=1 Ú ⁿ (r_i,k × r_k,j),

r_i,j³=_k=1 Ú ⁿ (r_i,k × r_k,j²) и так далее.

Пример: в таблице r дана матрица смежности неориентированного графа. Определить достижимость каждой вершины графа.

Окрестностью вершины x₁ является {x₂, x₄}, x₂ – {x₁, x₃}, x₃ – {x₂, x₄}, x₄ – {x₁, x₃}.

r	x1	x2	x3	x4		q	x1	x2	x3	x4
x1						x1
x2						x2
x3						x3
x4						x4
r2	x1	x2	x3	x4		q2	x1	x2	x3	x4
1						x1
x2						x2
x3						x3
x4						x4

Ответ: любая вершина графа достижима не более, чем за “два шага”.

 

Пример: дана матрица смежности ориентированного графа. Определить достижимость каждой вершины графа.

 

r	x1	x2	x3	x4		q	x1	x2	x3	x4
x1						x1
x2						x2
x3						x3
x4						x4

 

r2	x1	x2	x3	x4		q2	x1	x2	x3	x4
1						x1
x2						x2
x3						x3
x4						x4

 

r3	x1	x2	x3	x4		q3	x1	x2	x3	x4
x1						x1
x2						x2
x3						x3
x4						x4

Ответ: любая вершина графа достижима не более, чем за “три шага”.

Матрица разрезов. Если можно построить множество разрезов в виде совместимых кортежей, то можно оформить матрицу разрезов b, строками которой являются индексированные разрезы b_i, а столбцами – ребра графа r_j, одни из концевых вершин которых принадлежат множеству X’, а другие - множеству (X\X’),. Элементы матрицы разрезов вычисляют по формуле:

 

1, если j-е ребро участвует в i-м разрезе,

b(i, j)=

0, в противном случае.

Например, если x1ÎX’, а x4ÎX\X’ (см. рис. 3.6), то можно оформить не менее 18 разрезов, разъединяющих эти вершины. Ниже в таблице 3.8 приведена матрица только для пяти разрезов.

Таблица 3.8
b	r1	r2	r3	r4	r5	r6	r7	r8	r9	r10	r11
b1
b2
b3
b4
b5

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

Элементы матрицы циклов вычисляют по формуле:

 

1, если j-е ребро участвует в i-м разрезе,

c(i, j)=

0, в противном случае.

Для графа, приведенного на рис. 3.10а) можно оформить не менее 18 циклов. Ниже в таблице 3.9 приведена матрица только для шести циклов этого графа.

Таблица 3.9

с	r1	r2	r3	r4	r5	r6	r7	r8	r9
c1
c2
c3
c4
c5
с6

Числа графа

Функции, заданные на множестве графов {G=<X; r>} и принимающие значения на множестве целых чисел, называют числовыми характеристиками или просто числами. Наиболее очевидными и простыми числами являются: число вершин - n, число рёбер - m, степени вершин - s_i(или s_i⁺/s_i^-). Остальные числа графа требуют вычисления их значений.

Число компонент связности графа G=<X; r>. Граф называют связным, если любая пара его вершин связана цепью или путем.

Если множество вершин графа разбить на попарно непересекающиеся, непустые подмножества X={X₁’, X₂’,...X_k’}, т. е X_i’ÇX_j’=Æ для i¹j и X_i¹Æ, то формируемые с помощью инцидентных X’_i ребер r’_iÍr подграфы G₁=<X₁’;r₁’>, G₂=<X₂’;r₂’>,…, G_k=<X_k’;r_k’> являются связными, а между собой – несвязными, т. е. G_iÇG_j=Æ. Связный подграф G_i называют компонентой связности, а их количество - числом компонент связности k(G).

Для поиска числа компонент связности k(G) используют механизм вычисления матриц достижимости (см. 3.3).

На рис. 3.12. представлен граф и его три компоненты:

G=<X; r>, где X={x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉, x₁₀, x₁₁},

G₁=<X₁; r₁>, где X₁={x₁, x₂, x₃, x₄}, G₂=<X₂; r₂>, где X₂={x₅, x₆, x₇, x₈}, G₃=<X₃; r₃>, где X₃={x₉, x₁₀, x₁₁}.

Цикломатическое число графа G=<X; r>. Для исследования циклов в графе используют цикломатическую матрицу С(G), столбцы которой есть ребра графа, а строки c(I, j)– возможные циклы.

1, если j-е ребро входит в i-й цикл,

с(i, j) =

0, в противном случае.

Например, для графа, приведенного на рис. 3.13, ниже представлена цикломатическая матрица, описывающая все циклы. Таких циклов - семь.

Наименьшее число рёбер, удаление которых приводит к графу без циклов и петель, называют цикломатическим числом и обозначают l(G). Цикломатическое число можно определить по формуле l(G)=m-n+k(G), где m - число рёбер, n - число вершин, k(G) - число компонент связности графа. Для графа G, приведенного на рис. 3.13, имеем n=7, m=9, k(G)=1. Следовательно, l(G)=9-7+1=3.

Связный граф, не содержащий ни одного цикла, называют деревом.

 

Ниже приведена матрица для семи циклов графа, приведенного на рис. 3.13.

 

С(G)	r1	r2	r3	r4	r5	r6	r7	r8	r9
c1
c2
c3
c4
c5	⇐ Предыдущая567891011121314Следующая ⇒ Поделиться: Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...