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

М715 

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ СТАЛИ и СПЛАВОВ 
^ГКХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ) 

- 
^^*Федра автоматизированных систем управления 

Конвиссар Е,П., Рытикова Ю.В., Прокопчук Ю,Ю. 

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

Дискретная математика 

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

Лабораторный щтжтшкрл 

для стуцснтов специальности 07.19 и 22.02 

Москва 1998 

АННОТАЦИЯ 

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

® 
Московский 
государственный 

институт 
стали 
и 
сплавов 
(МИСиС), 1998. 

Кон»исс«р Е П, Рытнко»» Ю В. Прокопчук Ю Ю. 

СОДЕРЖАНИЕ 

I. Цель работы 
4 

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

П1. Вопросы и упражнения 
10 

IV. Литература 
13 

V. Пример постановки и решения задачи 
14 

VI. Варианты задач 
,, 
15 

Приложение I. Разбор решений некоторых 

упражнений 
21 

Приложение II. Блок-схема алгоритма 
25 

Приложение III. Программа построения 

множества всех ребер между 
двумя фиксированными 
вершинами графа общего вида, 
зманного таблицей соответствий 
26 

Л«бор«торны11 прмпчкум 

ЛАБОРАТОРНАЯ РАБОТА 1 

Построение характеристик графа, заданного 
инцидентором 

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

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

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

I. Понятие "граф" способствует изучению математических 
аспектов (6, с. 9-10) таких ситуаций, когда имеются две совокупности объектов, причем объекты второй совокупности ифают 
роль связок, соединяюишх координаты пар объектов первой. Более определенно речь может идти об электроприборах и соединяющих их проводниках; людях и родственных связях между ними; множествах и заданных на них бинарных отношениях, например, об отношении естественного порядка на числовом множестве. Для проекций одной и той же пары объектов первой совокупности допускается наличие связей различных видов: односторонних, двухсторонних или соединяющих объект с самим собой. При этом ограничений на число связей каждого вида не наклады: ается. 

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

df 
L = <X,U,P>, 
(1) 

Конвиссар Е П , Рьгтихов» Ю.В.. Прокопчук Ю.Ю. 

если представлены два множества: X вершин L и U ребер 
L, 
причем Л ' * 0 , а XOU = 0, и предикат Р, удовлетворяющий 
условиям: 

1) Р определен на всех тройках 

< х,и,у> еХ •>< и X X; 

2) C^ueU)Qx,y€X){P(x,u,y)A(yx,y' 
еХ)[Р(х,и,у')^ 

=>(х=х' лу = у) \/(х=у' лу= х')]). 

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

Граф (1) называется конечным, если X и U -~ конечные 
множества, и бесконечным — в противном случае. 

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

(Зх,у е Х)[х* 
у л Р(х,и,у)л^Р(у,и,х)]; 
(2) 

(ЗхеХ)[Р(х,и,х)] 
; 
(3) 

(Зх,у 6 Х)[х^улР(х,и,у)лР(у,и,х)]. 
(4) 

Ребра, для которых выполняется соотношение (2), называют дугами, (3) — петлями, (4) — звеньями. Соотношение (2) означает, что 
ребро и есть дуга, исходящая из вершины X и заходящая в 
вершину у; соотношение (3) — ребро и есть петля при вершине 
X; а соотношение (4) — ребро и есть звено, соединяющее вершины X и >». Множества дуг, петель и звеньев обозначают знакосо
~ 
о 
~ 
четаниями U, U н U соответственно. 

Пример 1. Проиллюстрируем введенные понятия и обозначения. На рис. 1 изображена диаграмма графа 
L{=<X\,U\,I\>, 
для которого Х\= {a,b,c,d} 
и U\-{\,2,...,9). 
Предикат 
Pj 
равен 1 на И тройках: <a,l,fl>, <а,1,а>, 
<а,Ъ,Ь>, 
<а,4,Ь>, 
<Ь,4,а>, <а,5,с>, <а,6,с>, <с,6,а>, <с,1,Ь>, <c.S,b>, 

Л»6ор«торный прмпикум 

<b,9,c>, 
и о — на остальных 
133. Легко понять, 
что 

(7, ={3,5.7.8.9}, f/i = {U},(/i = {4.6}. 

Рис. J. 

2. Познакомимся с некоторыми понятиями и терминами 
теории графов. Ребро и- и вершина х графа (1) называют инцидентными, если и либо исходит из х, либо заходит в х, либо 
является петлей при X, либо является звеном, соединяющим х с 
какой-либо другой вершиной. В графе L\ инцидентны вершина 
а и дуга 3, вершина а и петля 1, вершина b и звено 4 и тл. 

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

Ребра U и V графа (1) называют смезкными, если существует вершина, инцидентная им обоим. В графе L\ смежны ребра 
1и2, 1 и З , З и 7 и тл. 

Множество, состоящее только из всех дуг фафа (1), исходящих из его вершины х (заходящих в х; звеньев, инцидентных 
X \ петель при х; ребер, инцидентных х), обозначают через 

Кон«исс«р Е.П., Рытаком Ю В., Прокопчуж Ю Ю 

S*{x) 
(соответхггвенно, 
S~(x); 
S(x); 
5°(х);5{х)). 
Если 

фаф (1) - конечный, то число р*(*)| (р'(л^)|. p(*)i) называют 
нолустепенью исхода из X (соответственно, полустепенью захода в 
дс; степенью X). Ясно, что 

5(х) = ^•'(х) U S'ix) и S(x) U S^(x). 
(5) 

Отсюда, используя определения типов ребер, получаем: 

|5(х)1=|5*(х)| +|5-(х)| +1?(х)| +[s^(x)|. 
(6) 

Если 
5(х) = 0 , 
вершину 
х 
называют 
голой, а когда 

S{x) \ ^(х) - одноэлементное множество — висячей. 

Пример 2. Для вершины а графа Lj - см. рис.1 - имеем: 

5^а)=(3,5}, | 5 » | = 2; 5-(а) = 0 . |5-(а)| = 0; 5(о)={4.б}, 

|5(а)| = 2; 
Г(а) = {ц}. 
|5^(а)| = 2; 
5(a) ={ 1.2Д4,5,б}. 

\S{a)\ = 6. Вершина d — голая, а висячих вершин в Lj нет. 

Множество, состоящее только из всех дуг графа (1), исходящих из вершины X и заходящих в вершину у (дут, исходящих 
из у и заходящих в X; звеньев, инцидентных хну; 
ребер, инцидентных X и у), обозначают через S'*'{x,y) (соответственно, 
S'{x,y), 
S{x,y), Six,у)). Очевидно, что 

5\х,у)='5-{у,х); 
5-(х.>') = 5*СК,х); S{x,y)'S(y,x). 
(7) 

лабораторный прчтилм 

Отсюда И ИЗ равенства 

S(x,y)^S\x,y) 
^ S:{x,y) 
KJ 5(х,у) 
(8) 

следует, что 

S(x,y) = S(y,x). 
(9) 

Пример 3. Для вершин b и с графа Lj - см. рис. 1 
имеем. 
5*(*,c) = ,S"(c,A)=(9); 
^~(6.с) = 5'^(с,А) ={7,8); 

S(b.с) = Sic,b) = 0; Sib,c) = Sic,b) = (7,8,9} . 

3. Рассмотрим некоторые способы задания конечных фафов. Для описания такого графа вида (1) достаточно располагать 
множествами X, 
U и инцидентором Р. X к U могут быть 
опрслелсны, 
например, 
перечислением 
их 
элементов, 
а 
Р - трехмерной таблицей истинности, которая, если использовать терминологию алгоритмических языков, представляет собой 
трехмерный массив. На плоскости он может быть изображен таблицей, имеющей m = \U\ строк и п 
столбцов, где п = \Х\. 
Столбцы разбиты на группы, любая из которых состоит из п 
элементов. Каждая ipynna помечается некоторым элементом из 
X, пршем разные фуппы имеют разные метки. Внутри грулпь! 
каждый столбец также имеет метку из X, причем, как и выше, 
разные столбцы имеют разные метки. Различные строки снабжены различными метками из U. Если на пересечении к -й строки 
(15 А 5 ffl) и у -го столбца (1 <, i,j S п) стоит 1, это означает, что 

/'(Xj,i/jt,x.)= 1, т.е. ребро U/^ инцидентно вершинам ж,- и дсу; 

если - О, то не инцидентно хотя бы одной их них. Так, плоское 
изображение таблицы истин)!ости инцидентора фафа i j — см. 
рис.1 - имеет вид: 

Коикисор Е П , Ритаком Ю В , Проюпчлк Ю Ю 

\ у. 
и\ 
1 
2 
3 
4 
5 
6 
7 
8 
9 

а 
1 
1 
0 
0 
0 
0 
0 
0 
0 

а 

b 
0 
0 
1 
1 
0 
0 
0 
0 
0 

с 
0 
0 
0 
0 
1 
1 
0 
0 
0 

d 
0 
0 
0 
0 
0 
0 
0 
0 
0 

а 
0 
0 
0 
1 
0 
0 
0 
0 
0 

b 

b 
0 
0 
0 
0 
0 
0 
0 
0 
0 

с 
0 
0 
0 
0 
0 
0 
0 
0 
1 

d 
0 
0 
0 
0 
0 
0 
0 
0 
0 

а 
0 
0 
0 
0 
0 
1 
0 
0 
0 

b 
0 
0 
0 
0 
0 
0 
1 
1 
0 

с 

с 
0 
0 
0 
0 
0 
0 
0 
0 
0 

d 
0 
0 
0 
0 
0 
0 
0 
0 
0 

Таблица 1 

d 

a
b
e
d 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

0 
0 
0 
0 

Поскольку для большинства 1рафсв гакая таблица содержит гораздо больше нулей, чем единиц, то граф "экономнее" задавать числом П и так называемой таблицей соответствий (ТС), 
которая устроена следующим образом. Она имеет три строки и 

р-т 
+ р\ столбцов. В ее первой строке расположены метки 

вершин, из которых исходят ребра, во вггороЙ - метю1 ребер, а в 
третьей — метки вершин, в которые эти ребра заходят. То есть 
столбцы этой таблицы содержат сведения о всех тех тройках, на 
каждой из которых значение инцидснтора равно 1. Так, наличие в 
ТС столбца вида 

f 
'\ 

"к 

свидетельствует о том, что ребро «^ исходит из вершины X, и 

заходит в вершину X.. Понятно, что петля «^ при вершине х, 

будет задаваться столбцом вида 

Л»6ор«торный npiumniy»» 

Если ребро Uii является звеном, инцидентным вершинам х^ и 
Xj , то оно по определению зддается двумя столбцами вида 

/' 
> 

XI Xj 

При этом столбцы, соответствующие звену, в ТС всегда располагаются рядом. Например, для графа L\ таблица соответствий 
имеет вид: 

Таблица 2 

ааааЪаасссЬ 

1 2 3 4 4 5 6 6 7 8 9 
^aabbaccabbcj 

ТС компактнее таблицы истинности и поэтому более экономна 
при про1раммировании. 

III. Вопросы И упражнения 

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

2. В каком контексте используются слова "конъюнкция", 
"дизъюнкция", "отрицание", "импликация" и тл.? 

3. Что такое предикат? 
4. Какие множества служат областями определения и значений инииаентора графа? 

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

10 

Конвиос^р Е П , Ри1ико»« Ю.В.. Прокопчук Ю.Ю. 

6. В чем состоит смысл условия I) определения иниидентора? 

7. Перечислите различные типы ребер графа и запишите 
их определения на логико - математическом языке (ЛМЯ), используя понятие инцидентора. Например, 

df 
[и - дуга графа L-< 
X,U,P>] 
и 

df 
^ 1{3х,у ^ Х){хФ у А 
Р(х,и,У)А-Р{у,и,х))]. 

- о 
~ 

8. Пусть L=< Х,и,Р> 
- граф, а U, UK U - части от 

и, состоящие только из всех дуг, петель и звеньев соответственно. Задайте эти части описанием — см. Приложение I, с. 21. 

9. Пусть Б=(д)|^^ 
- семейство конечных множеств, 

и 
п 

p={JAi .а9 = 2к|
Ответьте на следующие вопросы: 

а) в каком отношении находятся числа р и q в общем 

случае? 

б) когда выполняется равенство 
р-^Ч 

ctf 

10. Пусть 
X, » < Х,и,Р 
>• 
граф. а /Я 1 - \и.и,и\ 

множество, элементами которого служат указанные в упр.8 части 
множества U. Ответьте на вопросы. 

а) Является ли множество /Я покрытием множества ( / ? - см. Приложение I, с. 21. 

б) Является ли множество /П взаимно диэъюнкгным, то 

есть верно ли равенство U\\U\\U 
= 01 

в) Является ли множество ffl попарно дизъюнктным, то 

рна ли конъюнкция 
- см. Приложение I, с. 22. 
есть верна ли конъюнкция Vf]l/=0AVf]U=^0AUf]U=01 
~ 

11