Файл: Дискрет-ная мат-ка_УМП.pdf

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

81

3 ᇉ‡˜Ë ËÁ письменной ÍÓÌÚðÓθÌÓÈ ð‡·ÓÚ˚.               

íÂχ 10: «ç‡ıÓʉÂÌË ÔðÓÒÚ˚ı ˆÂÔÂÈ 
‚ „ð‡Ù» 

 

3.1 Содержание работы 

 

Задача по теории графов, входящая во вторую контрольную 

работу, состоит из трех пунктов. 

По  первому  из  них  требуется  найти  все  простые  цепи,  со-

единяющие  две  заданные  вершины  неориентированного  графа. 
В разных вариантах контрольной работы заданными могут быть 
различные вершины, например 1 и 6 либо 2 и 4 и т.д. В данном 
же  случае  для  определенности  заданными  будем  считать  вер-
шины 1 и 5. Тогда тему контрольной работы можно сформули-
ровать  следующим  образом:  найти  все  простые  цепи,  соеди-
няющие  вершины 1 и 5 неориентированного  графа,  заданного 
множеством ребер: 

G = {{1,2}, {1,3}, {1,4}, {1,5}, 

{2,3}, {2,4}, {3,4}, {3,5}, {4,5}}. 

Для  решения  задачи  сначала  следует  построить  граф.  Для 

этого в выражении G имеется полная информация. Из записи G 
видно, что в графе пять вершин: 

V = {1, 2, 3, 4, 5}, 

где V — множество вершин графа. 

Элементами  множества  G  являются 

ребра  графа,  заданные  подмножествами 
множества  V,  содержащими  по  два  эле-
мента.  Например,  первое  подмножество 
имеет  вид {1,2}. Эта  запись  обозначает: 
вершины 1 и 2 соединены ребром. Точно 
так же интерпретируются все остальные 
элементы множества G

Граф изображен на рис. 14. 
По  второму  пункту  задачи  для  того 

же неориентированного графа требуется найти все простые цик-
лы, которые начинаются в вершине 1 и в ней же оканчиваются. 

По третьему пункту задача формулируется как и первая, но 

при  условии,  что  граф  является  ориентированным  (орграфом), 

  1 

Рис. 14 

 


background image

 

82

т.е.  теперь  надо  считать,  что  в  множестве  G  перечислены  не 
ребра графа, а дуги, где первая цифра — начало дуги. Например, 
запись {1,2} обозначает:  дуга  соединяет  вершины 1 и 2, при 
этом стрелка направлена от вершины 1 к вершине 2. 

В  следующих  трех  подразделах  приведены  образцы  реше-

ния всех трех пунктов задачи о поиске всех простых цепей. 

 
3.2 Простые цепи в неориентированном графе 
 
Применение  алгоритма  нахождения  всех  простых  цепей, 

соединяющих  две  заданные  вершины  графа,  проиллюстрируем 
на  примере  графа,  изображенного  на  рис. 14. При  этом  будем 
полагать, что заданными являются вершины 1 и 5 и что началь-
ной является вершина 1, а конечной — вершина 5. В общем же 
случае,  так  как  граф  является  неориентированным,  начальной 
можно  объявить  и  пятую  вершину,  а  конечной — первую.  Ре-
зультаты от этого не изменятся. 

• 

На  первом  этапе  найдем  все  варианты  выхода  из  первой 

вершины, т.е. найдем все простые цепи, выходящие из вершины 
1 и содержащие точно по одному ребру: 

1 – 2,   1 – 3,  1 – 4,  1 – 5. 

Одна  простая  цепь,  соединяющая  вершины 1 и 5, найдена 

(она подчеркнута). 

• 

На  втором  этапе  найдем  все  простые  цепи,  содержащие 

точно по два ребра и выходящие из вершины 1. Для этого вос-
пользуемся результатами предыдущего этапа:  
 

1 – 2 – 3, 

1 – 3 – 2, 

1 – 4 – 2, 

 

1 – 2 – 4, 

1 – 3 – 4, 

1 – 4 – 3, 

 

 

1 – 3 – 5, 

1 – 4 – 5. 

Получены еще две искомые цепи (подчеркнуты). 

• 

На третьем этапе находим все простые цепи, ведущие из 

вершины 1 и  содержащие  точно  по  три  ребра.  Для  этого  вос-
пользуемся результатами второго этапа: 
 

1 – 2 – 3 – 4, 

1 – 3 – 2 – 4, 

1 – 4 – 2 – 3, 

 

1 – 2 – 3 – 5,  

1 – 3 – 4 – 2,  

1 – 4 – 3 – 2, 

 

1 – 2 – 4 – 3, 

1 – 3 – 4 – 5, 

1 – 4 – 3 – 5, 

 

1 – 2 – 4 – 5. 

 

 


background image

 

83

На третьем этапе получено еще четыре искомых цепи. Все 

они подчеркнуты. 

• 

Четвертый  этап  в случае  данного графа  является  послед-

ним: 
 

1 – 2 – 3 – 4 – 5, 

1 – 3 – 2 – 4 – 5, 

1 – 4 – 2 – 3 – 5, 

 

1 – 2 – 4 – 3 – 5, 

1 – 3 – 4 – 2 – ?   

1 – 4 – 3 – 2 – ? 

На  последнем  этапе  получено  четыре  простые  цепи  из  ис-

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

Две последние цепи оканчиваются вопросительным знаком. 

Это значит, что они являются тупиковыми, так как любое дви-
жение из вершины 2 приводит к повтору номеров вершин, в ре-
зультате чего появляется цикл. Все подобные цепи удаляем.  

 
3.3 Простые циклы в неориентированном графе 
 
Эта  задача  решается  точно  так  же,  как  и  предыдущая.  Ре-

шение  ее  проиллюстрируем  на  примере  графа,  изображенного 
на рис. 14. 

На  первом  этапе  найдем  все  простые  цепи,  выходящие  из 

вершины 1 и содержащие точно по одному ребру: 

1 – 2,   1 – 3,  1 – 4,  1 – 5. 

На  втором  этапе  найдем  все  простые  цепи,  выходящие  из 

вершины 1 и содержащие точно по два ребра: 
 

1 – 2 – 1, 

1 – 3 – 1, 

1 – 4 – 1, 

1 – 5 – 1, 

 

1 – 2 – 3, 

1 – 3 – 2, 

1 – 4 – 2,  

1 – 5 – 3, 

 

1 – 2 – 4, 

1 – 3 – 4, 

1 – 4 – 3,  

1 – 5 – 4, 

 

 

1 – 3 – 5, 

1 – 4 – 5. 

Найдено четыре простых цикла, правда, содержащих по два 

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

Третий этап: 
 


background image

 

84

 

1 – 2 – 3 – 1, 

1 – 3 – 2 – 1, 

1 – 4 – 2 – 1,   1 – 5 – 3 – 1, 

 

1 – 2 – 3 – 4, 

1 – 3 – 2 – 4, 

1 – 4 – 2 – 3,   1 – 5 – 3 – 2, 

 

1 – 2 – 3 – 5, 

1 – 3 – 4 – 1, 

1 – 4 – 3 – 1, 

1 – 5 – 3 – 4, 

 

1 – 2 – 4 – 1, 

1 – 3 – 4 – 2, 

1 – 4 – 3 – 2, 

1 – 5 – 4 – 1, 

 

1 – 2 – 4 – 3, 

1 – 3 – 4 – 5, 

1 – 4 – 3 – 5,   1 – 5 – 4 – 2, 

 

1 – 2 – 4 – 5, 

1 – 3 – 5 – 1, 

1 – 4 – 5 – 1, 

1 – 5 – 4 – 3, 

 

 

1 – 3 – 5 – 4, 

1 – 4 – 5 – 3. 

На  третьем  этапе  получено  десять  искомых  простых  цик-

лов, содержащих по три ребра. 

Четвертый этап дает 16 новых простых циклов: 

 

1 – 2 – 3 – 4 – 1, 

1 – 3 – 2 – 4 – 1, 

1 – 4 – 2 – 3 – 1, 

 

1 – 2 – 3 – 4 – 5, 

1 – 3 – 2 – 4 – 5, 

1 – 4 – 2 – 3 – 5, 

 

1 – 2 – 3 – 5 – 1, 

1 – 3 – 4 – 2 – 1,  

1 – 4 – 3 – 2 – 1, 

 

1 – 2 – 3 – 5 – 4, 

1 – 3 – 4 – 5 – 1, 

1 – 4 – 3 – 5 – 1, 

 

1 – 2 – 4 – 3 – 1, 

1 – 3 – 5 – 4 – 1, 

1 – 4 – 5 – 3 – 1, 

 

1 – 2 – 4 – 3 – 5, 

1 – 3 – 5 – 4 – 2, 

1 – 4 – 5 – 3 – 2, 

 

1 – 2 – 4 – 5 – 1, 

1 – 5 – 3 – 2 – 1, 

1 – 5 – 4 – 2 – 1, 

 

1 – 2 – 4 – 5 – 3,  

1 – 5 – 3 – 2 – 4, 

1 – 5 – 4 – 2 – 3, 

 

 

1 – 5 – 3 – 4 – 1,  

1 – 5 – 4 – 3 – 1, 

 

 

1 – 5 – 3 – 4 – 2,  

1 – 5 – 4 – 3 – 2. 

На заключительном (пятом) этапе получаем еще двенадцать 

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

1 – 2 – 3 – 4 – 5 – 1, 

1 – 3 – 2 – 4 – 5 – 1,  

 

1 – 2 – 3 – 5 – 4 – 1, 

1 – 3 – 5 – 4 – 2 – 1,  

 

1 – 2 – 4 – 3 – 5 – 1, 

1 – 4 – 5 – 3 – 2 – 1,  

 

1 – 2 – 4 – 5 – 3 – 1,  

1 – 5 – 4 – 2 – 3 – 1, 

 

1 – 4 – 2 – 3 – 5 – 1, 

1 – 5 – 4 – 3 – 2 – 1. 

 

1 – 5 – 3 – 2 – 4 – 1,  

 

 

1 – 5 – 3 – 4 – 2 – 1,  

 

Таким образом, всего в графе, приведенном на рис. 1, суще-

ствует 42 простых  цикла,  начинающихся  и  оканчивающихся  в 
вершине 1. Из них 4 цикла содержат по два ребра (например, 1 – 
2 – 1), 10 циклов – по  три  ребра  (например, 1 – 2 – 3 – 1), 16 
циклов    —  по  четыре  ребра  (например, 1 – 2 – 3 – 4 – 1) и 12 
циклов  — по пять ребер (например, 1 – 2 – 3 – 4 – 5 – 1). 


background image

 

85

3.4 Простые цепи в ориентированном графе 
 
В  двух  предыдущих  случаях  заданный  граф  считался  не-

ориентированным.  Теперь  же  будем  считать,  что  он  является 
ориентированным и что каждая пара номеров вершин обознача-
ет не ребро, а дугу. При этом первая цифра в обозначении дуги 
является ее началам, а вторая — концом. 

Чтобы записать аналитическое выражение ориентированно-

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

G = {(1,2), (1,3), (1,4), (1,5), 

(2,3), (2,4), (3,4), (3,5), (4,5)}. 

Построим для этого выражения граф (рис. 15). Согласно за-

писи (1,2) проводим дугу от вершины 1 к вершине 2. Согласно 
паре (1,3) проводим дугу от вершины 1 к вершине 3 и т.д. 

В соответствии с заданием найдем 

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

Первый этап. Из вершины 1 выхо-

дит четыре дуги 

1 – 2,   1 – 3,  1 – 4,  1 – 5. 

Последняя из этих однореберных цепей оканчивается циф-

рой 5. Следовательно,  одна  из  искомых  простая  цепь  получена 
(подчеркнута). 

Второй  этап.  Находим  все  простые  цепи,  выходящие  из 

вершины 1 и состоящие из двух дуг: 
 

1 – 2 – 3, 

1 – 3 – 4, 

1 – 4 – 5, 

 

1 – 2 – 4, 

1 – 3 – 5.   

Получены еще две искомые цепи (обе подчеркнуты). 
Третий этап: 

 

1 – 2 – 3 – 4, 

1 – 3 – 4 – 5, 

1 – 2 – 4 – 5, 

 

1 – 2 – 3 – 5.  

  1 

Рис. 15