Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 75 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

ответ на поставленный вопрос зависит теперь от существования эйлерова цикла
в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла,
и этот результат ознаменовал рождение теории графов.
. Упражнения к п. 5.5 .
1.
Для графа, представленного на рисунке, даны
замкнутые пути:
М
1
: (x2, x3), (x3, x4), (x4, x7), (x7, x2);
М
2
: (x2, x3), (x3, x4), (x4, x5), (x5, x6), (x6,
x2) (x2, x3), (x3, x7), (x7, x2);
М
3
: (x2, x3), (x3, x4), (x4, x5), (x5, x6), (x6,
x2);
М
4
: (x3, x4), (x4, x5), (x5, x7), (x7, x3);
М
5
: (x1, x2), (x2, x3), (x3, x4), (x4, x5), (x5, x6), (x6,
x1);
М
6
: (x1, x2), (x2, x3), (x3, x4), (x4, x5), (x5, x7), (x7,
x6) (x6, x1);
М
7
: (x2, x3), (x3, x4), (x4, x5), (x5, x7), (x7, x6), (x6, x1), (x1, x2);
a). Какие из этих путей являются контурами?
а)
A
A
D
D
B
B
б)
Рис.33 а) Схема Кенигсбергских мостов; б)Эквивалентный граф
C
C
C 
ответ на поставленный вопрос зависит теперь от существования эйлерова цикла
в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла,
и этот результат ознаменовал рождение теории графов.




                                          C

                                                                                 B

                                                           C                     D
                 B                       A
                                                                                 A



          D
                                                                            б)
                        а)



     Рис.33 а) Схема Кенигсбергских мостов; б)Эквивалентный граф




                                        C

.      Упражнения к п. 5.5                                                           .

1. Для графа, представленного на рисунке, даны
замкнутые пути:
М1: (x2, x3), (x3, x4), (x4, x7), (x7, x2);
М2: (x2, x3), (x3, x4), (x4, x5), (x5, x6),             (x6,
x2) (x2, x3), (x3, x7), (x7, x2);
М3: (x2, x3), (x3, x4), (x4, x5), (x5, x6),             (x6,
x2);
М4: (x3, x4), (x4, x5), (x5, x7), (x7, x3);
М5: (x1, x2), (x2, x3), (x3, x4), (x4, x5), (x5, x6), (x6,
x1);
М6: (x1, x2), (x2, x3), (x3, x4), (x4, x5), (x5, x7), (x7,
x6) (x6, x1);
М7: (x2, x3), (x3, x4), (x4, x5), (x5, x7), (x7, x6), (x6, x1), (x1, x2);
a). Какие из этих путей являются контурами?

Страницы