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

UptoLike

Циклом называется цепь, начало и конец которой находятся в
одной и той же вершине.
Цикл, образованный последовательностью ребер, среди вер-
шин которых не встречается одинаковых, называется элементар-
ным.
Граф называется связным, если любые две его вершины можно
соединить цепью.
Граф называется простым, если он не содержит петель и крат-
ных ребер.
Рис. 5. Граф с кратными ребрами и петлями.
Граф, содержащий кратные ребра, но без петель, называется
мультиграфом, а граф с кратными ребрами и петлями называет-
ся псевдографом (рис. 5). Граф, не содержащий ребер, называется
пустым.
§ 2. Ориентированный граф
До сих пор рассматривались неупорядоченные пары вершин
.е. неориентированные ребра). Но если порядок существен, то вво-
дят ориентацию.
Упорядоченную пару (u, v), u, v V , будем называть ориенти-
рованным ребром или дугой и будем говорить, что u начальная
вершина, а v конечная вершина, и что u предшествует v.
42