Составители:
Рубрика:
Циклом называется цепь, начало и конец которой находятся в
одной и той же вершине.
Цикл, образованный последовательностью ребер, среди вер-
шин которых не встречается одинаковых, называется элементар-
ным.
Граф называется связным, если любые две его вершины можно
соединить цепью.
Граф называется простым, если он не содержит петель и крат-
ных ребер.
Рис. 5. Граф с кратными ребрами и петлями.
Граф, содержащий кратные ребра, но без петель, называется
мультиграфом, а граф с кратными ребрами и петлями называет-
ся псевдографом (рис. 5). Граф, не содержащий ребер, называется
пустым.
§ 2. Ориентированный граф
До сих пор рассматривались неупорядоченные пары вершин
(т.е. неориентированные ребра). Но если порядок существен, то вво-
дят ориентацию.
Упорядоченную пару (u, v), u, v ∈ V , будем называть ориенти-
рованным ребром или дугой и будем говорить, что u — начальная
вершина, а v — конечная вершина, и что u предшествует v.
42
Страницы
- « первая
- ‹ предыдущая
- …
- 39
- 40
- 41
- 42
- 43
- …
- следующая ›
- последняя »