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