Основы синтеза и диагностирования автоматов. Воронин В.В. - 61 стр.

UptoLike

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

Рубрика:

Путь, являющийся замкнутой простой орцепью, называют кон-

туром. На рис. 2.21 пути (2.5) и (2.7) – контуры, а (2.6) – нет.

Контур, проходящий через все вершины графа, называют га-

мильтоновым контуром. Контур (2.7) – это гамильтонов контур. В

графе на рис. 2.20 такого контура нет. Замкнутый маршрут является

неориентированным двойником замкнутого пути. В неориентирован-

ном графе понятию контур соответствует понятие цикл.

Для вершин r и j графа G существует три возможности: путь

отсутствует; существует один путь; существует несколько путей.

Некоторый фиксированный путь между начальной вершиной r и ко-

нечной вершиной j будем обозначать

P , k=1,2,3,… .

Путь

P можно задавать тремя способами: перечислением но-

меров вершин; перечислением номеров дуг; перечислением пар но-

меров вершин, образующих дуги. Рассмотрим эти способы на приме-

ре графа, представленного на рис.

2.22.

Зададим пути между вершинами 7 (выход) и 8 (вход) в виде:

множеств вершин

P ={7,6,5,4,10,9,8},

P ={7,6,11,10,9,8};

множеств дуг

13 14 15 12

8 9 10 11 12

1 2 3 5 6 8

1 2 4 3 5 6 7

1 10 11

Рис. 2.22