Маршруты в графах

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

Для неориентированных графов справедливы следующие понятия.

Цепь – последовательность ребер S = (g1, g2,..., gn), в которой у каждого ребра gk одна из вершин явля­ется вершиной ребра gk-1, а другая - вершиной ребра gk+1. При этом одно и то же ребро или вершина может встречаться несколько раз. Пример цепи для графа (рис. 3.6):

S = (g0, gl, g2, g3, g4, g5, g2, gб) = ((x0, х1), (х1, х2), (х2, х3), (х3, х1), (х1, х4), (х4, х3), (х3, х2), (х2, х5)).

 
 

Рис. 3.6. Пример цепи

Цепь называется про­стой, если все ребра в ней раз­личны, и сложной (составной) – в противном слу­чае. Вершины в простой цепи могут повторяться.

Цепь назы­вается элементарной, если в ней ни одна из вершин не повторяется.

Циклом называется конечная цепь, начинающаяся на некото­рой вершине хi, и окачивающаяся на ней же. Простые, сложные и элементарные циклы определяются по аналогии с цепями.

Для ориентированных графов введены следующие дополни­тельные понятия.

Путем в графе G(X) называется такая последовательность дуг (gl, g2, …), что конец каждой предыдущей дуги является началом следующей. Существуют простые, сложные и элементар­ные пути.

Х|

Х0

Контур графа – это конечный путь, у которого начальная вер­шина совпадает с конечной. Существуют простые, слож­ные (составные) и элементарные контуры.

Длина пути есть число дуг L(s) в последовательности дуг пути s. В случае бесконечного пути L(s) = ¥.

 
 

Граф называется симметрическим, если " xi, xj из того, что xi Î G(xj) Þ xj Î G(xi), то есть две смеж­ные вершины xi, xj всегда соединены противоположно ориентирован­ными дугами (рис.3.7).

Рис. 3.7. Симметрический граф

Граф называется антисимметрическим, если " xi, xj
xi Î G(xj) Þ xj Ï G(xi), то есть каждая пара смежных вершин соединена только в одном направлении.

Граф называется конечным, если число его вершин конечно и бесконечным, если число вершин бесконечно. Граф G(X) называется G – конечным, если для каждой его верши­ны х Î X множество G(x) конечно.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



double arrow
Сейчас читают про: