Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 41 стр.

UptoLike

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

Рубрика:

Циклом называется цепь, начало и конец которой находятся в

одной и той же вершине.

Цикл, образованный последовательностью ребер, среди вер-

шин которых не встречается одинаковых, называется элементар-

ным.

Граф называется связным, если любые две его вершины можно

соединить цепью.

Граф называется простым, если он не содержит петель и крат-

ных ребер.

Рис. 5. Граф с кратными ребрами и петлями.

Граф, содержащий кратные ребра, но без петель, называется

мультиграфом, а граф с кратными ребрами и петлями называет-

ся псевдографом (рис. 5). Граф, не содержащий ребер, называется

пустым.

§ 2. Ориентированный граф

До сих пор рассматривались неупорядоченные пары вершин

(т.е. неориентированные ребра). Но если порядок существен, то вво-

дят ориентацию.

Упорядоченную пару (u, v), u, v ∈ V , будем называть ориенти-

рованным ребром или дугой и будем говорить, что u — начальная

вершина, а v — конечная вершина, и что u предшествует v.