Основные определения теории графов — различия между версиями
Kn793 (обсуждение | вклад) м (→Для неориентированного графа) |
(→Граф) |
||
| Строка 4: | Строка 4: | ||
Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер. | Графом <math> G </math> называется пара <math> G = (V, E); </math> где V - конечное множество вершин, а <math> E \subset V \times V </math> - множество рёбер. | ||
}} | }} | ||
| − | В | + | В неориентированном графе (v, u) = (u, v). |
==Ребро== | ==Ребро== | ||
Версия 00:35, 12 октября 2010
Содержание
Граф
| Определение: |
| Графом называется пара где V - конечное множество вершин, а - множество рёбер. |
В неориентированном графе (v, u) = (u, v).
Ребро
Для неориентированного графа
| Определение: |
| Ребром называют неупорядоченную пару вершин . |
Для ориентированного графа
| Определение: |
| Ребром называют упорядоченную пару вершин . |
Степень вершины
Для неориентированного графа
| Определение: |
| Степенью вершины vi называется число рёбер инцидентных vi, и обозначается deg vi |
Говорят, что ребро инцидентно вершине a, если u = a или v = a.
Для ориентированного графа
| Определение: |
| Полустепенью входа вершины vi называется число рёбер, входящих в эту вершину, и обозначается deg+ vi. |
| Определение: |
| Полустепенью выхода вершины vi называется число рёбер, выходящих из этой вершину, и обозначается deg- vi. |
Петля
| Определение: |
| Петлёй в ориентированном графе называется ребро, концы которого совпадают, то есть . |
В неориентированном графе петли запрещены.
Путь
| Определение: |
| Путём в графе называется последовательность вида v0 e1 v1 ... ek vk; где ei = (vi-1; vi). |
Цикл
Для ориентированного графа
| Определение: |
| Циклом называется путь, начало и конец которого совпадают, тоесть v0 = vk |
Для неориентированного графа
| Определение: |
| Циклом называется путь в котором нет двух одинаковых рёбер подряд, а также начало и конец которого совпадают, то есть v0 = vk |
