Маршруты. Цепи. Циклы.

Маршрутом в графе называют чередующуюся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.

Если , то маршрут называют замкнутым. Если все ребра различны, то маршрут называют цепью. Если все вершины, а значит и все ребра, различны – то маршрут называют простой цепью. Обозначают маршрут . Восклицательный знак – обозначение простой цепи. – длина маршрута . В маршруте и называют концами. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Число циклов в графе обозначают . Граф без циклов, , называют ациклическим.

Пример:

v-v3-v4-v3 – маршрут, но не цепь;

v1-v3-v5-v2-v3-v4 – цепь, но не простая цепь;

v1-v4-v3-v5 – простая цепь;

v1-v3-v5-v2-v3-v4-v1 – цикл, но не простой цикл;

v1-v3-v4-v1 – простой цикл.

 

Длиной маршрута называют количество ребер в нем (учитывая повторения). Расстоянием между вершинами и , обозначается , называется длина кратчайшей цепи , а сама кратчайшая цепь называется геодезической цепью. Множество вершин, находящихся на одинаковом расстоянии от вершины называют ярусом.








Дата добавления: 2015-12-16; просмотров: 827;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.