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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Контур, проходящий через все вершины графа, имеет особое название -
гамильтонов контур. Путь М
3
является гамильтоновым контуром. Он показан
штриховой линией на рис. 32.
Для неориентированного графа
замкнутым маршрутом является
неориентированный двойник замкнутого пути, т.е. замкнутым маршрутом является
маршрут, в котором совпадают начальные и конечные вершины.
Для неориентированного графа понятия цикла и гамильтонова цикла
аналогичны понятиям орцикла и гамильтонова контура в орграфе.
Эйлеровым циклом в графе называется цикл, содержащий все ребра
графа. Граф, содержащий эйлеров цикл называется
эйлеровым графом.
Основная теорема о существовании эйлерова цикла формулируется так.
ТЕОРЕМА: Связный неориентированный граф G содержит эйлеров цикл
тогда и только тогда, когда число вершин нечетной степени равно нулю (0 или 2).
Эйлер первым в своей знаменитой задаче о Кенигсбергских мостах
поставил вопрос о существование такого цикла.
На реке Преголя в Кенигсберге было два острова. Они соединялись между
собой и с берегами реки семью
мостами, как схематично показано на рис. 33.
Задача заключалась в том, чтобы за одну прогулку обойти все семь мостов,
проходя по каждому мосту только один раз, и вернуться в исходное место.
Если каждый берег реки и острова считать вершинами графа, а каждый
мост - ребром, то карту рис. 33,а. можно представить в виде
графа на рис. 33,б и
x
1
a
2
a
3
x
2
a
4
a
5
x
3
a
8
x
4
a
9
x
5
a
11
x
6
a
1
a
10
a
6
a
7
a
12
Рис.32 Орциклы в графе. 
                            x2             a4         x3
                                                            a5

                       a3             a6                         a8
            a2
                                                      a12              x4
                 x1

                                 a7                   a10
                                                                      a9
                      a1
                                                a11   x5
                            x6

                            Рис.32 Орциклы в графе.




      Контур, проходящий через все вершины графа, имеет особое название -
гамильтонов контур. Путь М3 является гамильтоновым контуром. Он показан
штриховой линией на рис. 32.
      Для   неориентированного        графа     замкнутым        маршрутом   является
неориентированный двойник замкнутого пути, т.е. замкнутым маршрутом является
маршрут, в котором совпадают начальные и конечные вершины.
      Для неориентированного графа понятия цикла и гамильтонова цикла
аналогичны понятиям орцикла и гамильтонова контура в орграфе.
      Эйлеровым циклом в графе называется цикл, содержащий все ребра
графа. Граф, содержащий эйлеров цикл называется эйлеровым графом.
      Основная теорема о существовании эйлерова цикла формулируется так.
      ТЕОРЕМА: Связный неориентированный граф G содержит эйлеров цикл
тогда и только тогда, когда число вершин нечетной степени равно нулю (0 или 2).
      Эйлер первым в своей знаменитой задаче о Кенигсбергских мостах
поставил вопрос о существование такого цикла.
      На реке Преголя в Кенигсберге было два острова. Они соединялись между
собой и с берегами реки семью мостами, как схематично показано на рис. 33.
Задача заключалась в том, чтобы за одну прогулку обойти все семь мостов,
проходя по каждому мосту только один раз, и вернуться в исходное место.
      Если каждый берег реки и острова считать вершинами графа, а каждый
мост - ребром, то карту рис. 33,а. можно представить в виде графа на рис. 33,б и

Страницы