Маршруты. Расстояния

Сентябрь 13, 2022

Главная
Математика
Маршруты. Расстояния

Содержание

2. Маршруты Пусть G =(V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и
3. Маршруты Вершина - начальная вершина маршрута М, - конечная, - внутренняя вершина, маршрут соединяющий и .
4. Маршруты Маршрут М называется цепью - если его ребра не повторяются, простой цепью – если его
5. Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.
6. Маршруты Циклический маршрут М называется циклом - если его ребра не повторяются, простым циклом – если
7. Маршруты М1 =(1, 2, 3, 4, 1, 3, 4, 5) – общ вида. М1 =(1, 2,
8. Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1,
9. Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их.
10. Расстояния в графе
11. Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной
12. Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по
13. Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины
14. Расстояния в графе Радиус графа G –расстояние от центра графа до наиболее удаленной вершины. r(G)=min ri
15. Расстояния в графе Центр графа G –такая вершина i, для которой ri =r(G). Замечание: Центр в
16. Расстояния в графе В нашем примере центром является вершина 5. Радиус -1, диаметр – 2.
17. Расстояния в графе Диаметральные цепи графа G – простые цепи, длина которых равна d(G), соединяющие наиболее
18. Расстояния в графе Радиальные цепи графа G – простые цепи, длина которых равна r(G), соединяющие центр
20. Скачать презентацию

Слайд 2

Маршруты
Пусть G =(V, E) – н-граф.
Маршрутом в графе G называется чередующаяся

последовательность вершин и ребер
где ребро инцидентно вершинам

Слайд 3

Маршруты
Вершина - начальная вершина маршрута М,
- конечная,
- внутренняя

вершина,
маршрут
соединяющий и .
Дина маршрута – число его ребер.

Слайд 4

Маршруты
Маршрут М называется
цепью - если его ребра не повторяются,
простой цепью –

если его вершины не повторяются,
маршрутом общего вида, если вершины и ребра повторяются.

Слайд 5

Маршруты
Маршрут М называется циклическим, если начальная и конечная вершина совпадают.
Замечание: совпадают,

не значит повторяются.

Слайд 6

Маршруты
Циклический маршрут М называется
циклом - если его ребра не повторяются,
простым циклом

– если его вершины не повторяются (кроме начала и конца),
маршрутом общего вида, если вершины и ребра повторяются.

Слайд 7

Маршруты
М1 =(1, 2, 3, 4, 1, 3, 4, 5) – общ

вида.
М1 =(1, 2, 3, 4, 1, 5) – цепь
М1 =(1, 2, 3, 4, 5) –
простая цепь.

Слайд 8

Маршруты
М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут

общего вида.
М1 =(1, 3, 4, 5, 6, 4, 1) – цикл (не пр)
М1 =(1, 2, 3, 4, 1) –
простой цикл.

Слайд 9

Расстояния в графе
Расстоянием между вершинами a и b
называется длина минимальной простой

цепи, связывающей их.
Расстояние обозначается d(a, b).
Аксиомы метрики:
1) d(a, b) = d(b, a);
2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b;
3) d(a, b) ≤ d(a, c) + d(c, b)

Слайд 10

Расстояния в графе

Слайд 11

Расстояния в графе
ri – эксцентриситет i-ой вершины – расстояние от этой

вершины до наиболее удаленной от нее вершины.
ri = max d(vi,vj)
по всем j от 1 до n

Слайд 12

Расстояния в графе
Диаметр графа G – максимальное расстояние между вершинами графа
d(G)=

max d(vi,vj) по всем i и j от 1 до n. Или
d(G)=max ri по всем i от 1 до n

Слайд 13

Расстояния в графе
Центр графа G – это вершина, расстояние от

которой до наиболее удаленной вершины – минмальное.
Что бы найти центр, надо сначала найти радиус графа.

Слайд 14

Расстояния в графе
Радиус графа G –расстояние от центра графа до наиболее

удаленной вершины.
r(G)=min ri
по всем i от 1 до n

Слайд 15

Расстояния в графе
Центр графа G –такая вершина i, для которой

ri =r(G).
Замечание:
Центр в графе может быть не единственный.

Слайд 16

Расстояния в графе
В нашем
примере
центром
является
вершина 5.
Радиус -1,

диаметр – 2.

Слайд 17

Расстояния в графе
Диаметральные цепи графа G – простые цепи, длина которых

равна d(G), соединяющие наиболее удаленные вершины графа.

Слайд 18

Расстояния в графе
Радиальные цепи графа G – простые цепи, длина которых

равна r(G), соединяющие центр и наиболее удаленные от него вершины графа.