Дискретная математика. Раздел : теория графов : выпуск 2

№452 

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ «МСДВРАПИИ 

м о с к о в с к и й ГОСУДАРСТВЕННЫЙ ИНСТИТУТ СТАЛИ и СПЛАВОВ 
{ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ 

Кафедра автоматизированных систем управления 

Рытнкова Ю.В., Булхов Н.Н., Прокопчук Ю.Ю. 

Одобрено методическим 
советом института 

Дискретная MaTeMaivKa 

Раздел: Теория графов (выпуск 2) 

(Переиздание) 

Лабораторный практикум 
для студентов специальности 0719 и 2202 

НТБ 
МИСИС 

СЧЗ 
ГЛ.КОРПУС 

Москва 2000 г. 

Аннотация 

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

© Московский государственный 
институт стали и сплавов 
(МИСиС) 2000 

Рьпнкова Ю В., Будхов Н.Н.. Прокоптук Ю Ю. 

ЛАБОРАТОРНАЯ РАБОТА 2 
Преобразование матриц, характеризующих 
графы. Выявление информации о графе, 
заданном одним из матричных способов 

(4 часа) 

1. Цель работы 

Ознакомиться с ма1ричными способами задания графа и 
на этой основе научиться выявлять о нем определенную информацию. 

2. Теоретическое введение 

2.1. Для любых двух элементов L к V совокупности графов А можно поставить вопрос о степени их сходства в том или 
ином смысле. Формула «граф L похож на граф Z,'* выражает 
хотя и осмысленное, но все же пока не формальное отношение 
на А, которое допускает различные уточнения. Два из них: равенство и изоморфность графов мы и рассмотрим здесь. 

2.2. Не вызывает затруднений формулирование точного 
определения наибольшей степени сходства графов - их тождественности, или равенства, обозначаемой знаком =, поскольку графы представляют собой тройки, а равенство последних эквивалентно по определению совпадению их соответствующих компонент. Поэтому говорят, что граф L = {X,U,P) 
находится в шь 

ношении равенства с графом L =\Х ,U ,Pj, 
или, короче, jac 

вен ему, и обозначают этот факт так: L~L\ 
если: 

1) Х = Х; 
2)f/ = (/'; 
3) (Vx.^eX, 
и^щ\р{х,и,у)<;>р\х,и,у\. 

Лабораторный практикум 

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

Пример 1. Графы Z-i^ и Zjg, диаграммы которых приведены на рисунках 1а) и 16) соответственно, равны. 

IV HI / 
4 \ IV IVI 
£ 
У1 
d 
U 

а) 
б) 
в) 

Рис 1. 

2.3. Очевидно, что графы Z-jg и Lj^, изображенные на 
рис. 1в) и 1г) соответственно, не равны, а также каждый из них 
не совпадает ни с одним из предыдущих. Так, графы L^^ и Lj^ 
различны, поскольку не выполняются условия 1) и 2). С другой 
стороны, несомненно и их сходство, состоящее в том, что существуют переобозначения вершин и ребер графа Lj^ метками из 

множеств Xi^-\a,fi,y,S] 
вершин и Ui^ = {a,b,c,d} 
ребер 
графа Lj^ соответственно, которые «превращают» его в граф Z.^^ . 
Таким переобозначением для вершин может быть, в частности, 
следующее: 

Таблица 1 

^к 

^\г 

I 
а 

II 
Р 

III 

У 

IV 
д 

PbiiHKota Ю В, Б>лхов Н И , Прокопчук Ю Ю 

Соответствующее переобозначение ребер должно быть таким: 

Таблица 2 

Uia 
ихг 

1 
а 

2 
b 

3 
с 

4 
d 

Сравнивая графы Z-j^ и Lig, видим, что хотя множества 
их вершин и ребер совпадают, но условие 3) равенства графов не 
выполнено. Например, ребро 1 графа L\a инцидентно его вершинам I и III, а ребро 1 графа Z-j^ - вершинам I и IV. Но граф 
Zj^ легко «превратить» в граф Z-jg такими переобозначениями 
вершин и ребер: 

Таблица 3 

^\а 
^\в 

Ula 
Uie 

I 
I 

I 
1 

II 
II 

2 
2 

III 
IV 

3 
3 

IV 
III 

Таблица 

4 
4 

Наличие такого рода связей между графами формализуется 
при помощи понятия изоморфности. А именно, говорят, что граф 
L = {X,U,P) 
находится в отношении изоморфности. или, коро
графу 
L -iX 
,и ,Р ) , и обозначают этот факт 

так: L~ L', если существуют биекции h^.X-^^X 
н h2'U —^U , 

Лабораторный практикум 

удовлетворяющие условию: 

(Ух,уеХ, 
uGU)[P{x,u,y)<^p\hiix),h2iu)My))\- 
(D 

Пара биекций \h^,h^i, для которых верно соотношение 

(1), называется изоморфизмом. С логической точки зрения изоморфность графов - более слабая степень их сходства, чем равенство, поскольку из равенства графов следует их изоморфность, 
но обратное вообще говоря неверно. 

2.4. Как сказано в описании лабораторной работы №1, 
конечный граф задается множествами X п U, а также инцидентором Р, который, будучи трехместным предикатом, описывается 
трехмерной таблицей истинности. Понятие изоморфности позволяет перейти к заданию графов двумерными таблицами, т.е. матрицами - см. Приложение 2, стр. 25. Их использование намного 
упрощает исследование свойств графов, в частности, определение 
тех или иных характеристик последних. Но при таком переходе 
часть информахши о графе может потеряться. Поэтому не все 
рассматриваемые ниже матрицы позволяют восстановить граф не 
только с точностью до равенства, но и даже до изоморфности. Об 
этом более подробно будет сказано дальше. Подчеркнем, что чаще всего нас будут интересовать свойства графов, которые совпадают у всех изоморфных графов, т.е. инвариантные относительно 
любого изоморфизма между ними. Рассмотрим несколько наиболее часто используемых способов матричного задания графов. 

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

Обозначим через К свободное полукольцо с нулем, порожденное четырьмя образующими: 
^, 
rf, 
^ 
w. в. 
Пусть 

Jf=|xj,X2, 
, x „ | - множество вершин графа L = {X,U,P), 
а 

f/= |«I,W2,- . " т | " множество его ребер, которое здесь предполагается непустым. Матрицей инииденпий этого графа называется прямоугольная таблица А ~ {ау ), i -\,п, 
j -\,т, 
элементы 

Рытикова Ю.В., Булхов H.H., Прокопчук Ю.Ю. 

которой Принадлежат полукольцу К и определяются по графу L 
следующим образом: 

ujj - ^, если Uj - дуга, исходящая из вершины х^; 

ajj = TJ, если Uj - дуга, заходящая в вершину Xj; 

Oij = (, если Uj - петля при вершине jc,; 

а,у = в, если tij - звено, инцидентное вершине х,; 

Лу = О, если ребро м • и вершина Xj неинцвдентны. 

Пример 2. Для графа Li, изображенного на рис. 2, 

Рис.2 

матрица инциденции такова: 

/1? = 

V0 0
0
0
0
0
0
0 
о; 

(2) 

Лабораторный прашикум 

Матрица инциденций графа L = \X,U,P) 
задает весь 

класс графов, изоморфных L . Но если ее строки и столбцы пометить взаимно однозначным образом метками элементов из Jf и 
и соответственно, то такая «пополненная» матрица инциденций 
будет задавать единственный граф. Так, матрица инциденций (2) 
графа Z-2 у пополненная слева столбцом меток из Х2 и сверху 
строкой меток из U2, имеет вид: 

^ 2 \ 

а 

b 

с 

d 

1 

С 
0 

0 

0 

2 

^ 
0 

0 

0 

3 

4 
п 
0 

0 

4 

е 
е 
0 

0 

5 

4 
0 

V 

0 

6 

в 
0 
в 
0 

7 

0 

7 

4 
0 

8 

0 

V 

4 
0 

9 

0 

4 
п 
0 

df 

и задает только этот граф. 

2.6. Квадратная матрица В = А- А"'*' порядка и = |А'|, где 

А"'^ - транспонированная матрица А, называется матрицей соседства вершин. Для храфа £2 " ^^- Р"*^- 2 - матрица Bi соседства вершин выглядит так: 

В, = 
14 ^е^ 

ч 
о 

4V+0' 

24л+ п4 
о 

41^9'
4n + 2v4 

24^ + 2;;2 + е^ 

О 

О 

О 

О 

о; 

Из определения матрицы Л = 1/>,у1, i,j-\,n, 
следует, что 

ее элементы имеют внд: 

Рытикова Ю.В., Булхов Н.Н., Прокопчук Ю.Ю. 

ЬЦ =1 S^Xi) 
\f 
+1 S-{Xi) 
\v^ +1 S{Xi) \в^ +! S\xi) 
|C^ 

bij =i 5^(x,-,xy) \4T] + \ S-{Xi,xj) 
1/7^ + 1 S{Xi,xj) 
\e^. 

Здесь I ^•^(x,) j , I 5"(Xj) |, ..., I S{Xi,Xj) 
\ - натуральные формы от вершин и пар вершин графа, описанные в 
теоретической части лабораторной работы №1. Матрица В графа 
L = \Х, f/, Р) также задает весь класс графов, изоморфных L . 
Но, даже будучи «пополненной» обозначениями элементов из X, 
она не несет в себе информации о метках ребер. Таким образом, в 
«пополненной» матрице В нет сведений об индивидуализации 
ребер графа, хотя и сохраняется их тип. Для графа Li из примера 
2 - см.рис.2 - «пополненная» матрица Bj выглядит так: 
X 

а 

b 
с 

d 

а 

2 ^ ' + 2 ^ ' + 2 ^ ' 

п^+в^ 

Tj^+e' 

0 

b 

4rj+e' 

^' + 3TJ^ + е" 

2^^7 + 7^ 

0 

с 

4п+е' 

^n + lrj^ 

24' +2TJ^ +а^ 

0 

d 

0 

0 

0 

0 

Такую же матрицу соседства вершин имеют графы L^^ и 
/-36, 
приведенные 
на рис. За) и 36), у которых хотя 

Х2 = ^За = ^36 , НО f/2 ^ и2а , f-h ^ U^Q И U^^ * ^Ъб • 

Лабораторный практикум 

Рис. 3. 

2.7. Замена матрицы В более употребительной матрицей 

S (х,-) \^ , Гу - b,j , 

i ^ J , того же порядка, что и матрица 5 , ни к какой дальнейшей 
потере информации о графе не приводит - см. вопрос 13 на 
стр.19' . 

Но в матрице R так же, как и в матрице В, отсутствуют 
данные о метках ребер, поэтому даже «пополненная» матрица R 
задает не единственный граф, а весь класс изоморфных графов, 
имеющих одинаковое множество вершин. Для фафа 
Li 
см.рис.2, - а также для фафов L30 и Z-зб - см. рис. За) и 36), матрица i?2 и «пополненная» матрица /?2 выглядят соответственно так: 

Л, = 

24-^ 

о 

О 

о 

О 

О 

о 

о 

о 

о; 

' Несмотря на то, что в научной литературе за матрицей R укрепилось название 
«матрица смежности вершин», было бы более точно называть ее «матрицей исходов и заходов», поскольку она содержит не только информацию о смежности или 
несмежности всех пар вершин гра4», но и о числе и типах всех ребер, иниидентных любой паре вершин. 

10