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` и ребра 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` и ребра a1; a2; : : : ; a` попарно различны.
Замкнутая цепь называется циклом.
Связность графов и маршруты Эйлеровы и гамильтоновы графы
Связность графа
Определение. Вершины 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; ) называется мостом, если его удаление приводит к увеличению числа компонент связности