Математическое моделирование на графах. Часть 1. Берцун В.Н. - 12 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

12 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Используя символы таблицы Менделеева, в химии графы приме-
няются для изображения молекул. Например, на рис. 1.11 представ-
лены мультиграфы молекул ацетилена (C
2
H
2
) и этилена (C
2
H
4
).
HH
CC
HH
HH
CC
Рис. 1.11
1.3. Маршрут в графе, цикл, связанность
Рассмотрим граф на рис. 1.12, в котором из вершины x
1
в x
5
мож-
но попасть различными способами.
Маршрутом в графе называется чередующаяся последователь-
ность вершин a
i
и ребер e
i
a = a
0
, e
0
, a
1
, e
1
, …, e
n–1
, a
n
= b,
где e
i
= (a
1
, a
i+1
), a – начало маршрута, b – конец маршрута. Маршрут
можно задавать, например, перечислением его вершин (a
0
, a
1
,…, a
n
).
В маршруте ребра и вершины могут повторяться. Если в нем все
ребра различны, то он называется цепью. В цепи вершины могут по-
вторяться. Если все вершины в цепи различны, то она является про-
стой цепью. Например, на рис. 1.12 последовательность вершин x
1
,
x
2
, x
3
, x
4
, x
6
, x
4
, x
5
является мар-
шрутом из x
1
к x
5
, а вершины x
1
,
x
2
, x
3
, x
4
, x
5
определяют простую
цепь (простой путь) из x
1
в x
5
.
Длина маршрута в графе изме-
ряется количеством ребер в нем
(с повторениями). Длина крат-
чайшей простой цепи, соеди-
няющей вершины А и В, опре-
деляет расстояние между ними.
x
1
x
2
x
5
x
4
x
3
x
6
Рис. 1.12

Страницы