9-
.pdf
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Эйлеровы пути
Определение. Эйлеровым путем называют замкнутый путь, проходящий через каждое ребро без повторений. Эйлеровым графом называют граф, имеющий эйлеров путь.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Эйлеровы пути
Определение. Эйлеровым путем называют замкнутый путь, проходящий через каждое ребро без повторений. Эйлеровым графом называют граф, имеющий эйлеров путь.
Определение. Полуэйлеровым путем называют путь (необязательно замкнутый), проходящий через каждое ребро без повторений.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Эйлеровы пути
Определение. Эйлеровым путем называют замкнутый путь, проходящий через каждое ребро без повторений. Эйлеровым графом называют граф, имеющий эйлеров путь.
Определение. Полуэйлеровым путем называют путь (необязательно замкнутый), проходящий через каждое ребро без повторений. Полуэйлеровым графом называют граф, имеющий полуэйлеров путь.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Эйлеровы пути
Определение. Эйлеровым путем называют замкнутый путь, проходящий через каждое ребро без повторений. Эйлеровым графом называют граф, имеющий эйлеров путь.
Определение. Полуэйлеровым путем называют путь (необязательно замкнутый), проходящий через каждое ребро без повторений. Полуэйлеровым графом называют граф, имеющий полуэйлеров путь.
Теорема. Связный граф является эйлеровым тогда и только тогда, когда степени всех вершин четны.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Эйлеровы пути
Определение. Эйлеровым путем называют замкнутый путь, проходящий через каждое ребро без повторений. Эйлеровым графом называют граф, имеющий эйлеров путь.
Определение. Полуэйлеровым путем называют путь (необязательно замкнутый), проходящий через каждое ребро без повторений. Полуэйлеровым графом называют граф, имеющий полуэйлеров путь.
Теорема. Связный граф является эйлеровым тогда и только тогда, когда степени всех вершин четны. Связный граф является полуэйлеровым тогда и только тогда, когда и имеется не более двух вершин с нечетными степенями.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Связность графа
Определение. Вершины A и B графа G = (V ; E) называются связанными, если существует путь
a1 |
a2 |
a3 |
a` |
|
= B: |
||||||||
A = A1 !A2 |
!A3 |
! !A`+1 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Связность графа
Определение. Вершины A и B графа G = (V ; E) называются связанными, если существует путь
a1 |
a2 |
a3 |
a` |
= B: |
A = A1 !A2 |
!A3 |
! !A`+1 |
||
Отметим, что можно считать этот путь цепью.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Связность графа
Определение. Вершины A и B графа G = (V ; E) называются связанными, если существует путь
a1 |
a2 |
a3 |
a` |
= B: |
A = A1 !A2 |
!A3 |
! !A`+1 |
||
Отметим, что можно считать этот путь цепью.
Граф G называется связным, если любые его две вершины связанны.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Связность графа
Определение. Вершины A и B графа G = (V ; E) называются связанными, если существует путь
a1 |
a2 |
a3 |
a` |
= B: |
A = A1 !A2 |
!A3 |
! !A`+1 |
||
Отметим, что можно считать этот путь цепью.
Граф G называется связным, если любые его две вершины связанны.
Компонентой связности графа G = (V ; E) называется любое связное непустое подмножество K V , такое что не существует ребер с началом a 2 K и концом b 2= K .
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Мосты и циклы
Определение. Ребро графа G = (V ; E; ) называется мостом, если его удаление приводит к увеличению числа компонент связности