Основные определения теории графов — различия между версиями
(→Ориентированные графы) |
(→Ориентированные графы) |
||
Строка 41: | Строка 41: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | '''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>. | + | '''Путём'''(маршрутом) в графе называется последовательность вида <tex>v_0 e_1 v_1 ... e_k v_k</tex>, где <tex>e_i \in E,~e_i = (v_{i-1}, v_i)</tex>; <tex>k</tex> {{---}} '''длина''' пути. |
}} | }} | ||
{{Определение | {{Определение |
Версия 21:05, 27 октября 2011
Ориентированные графы
Определение: |
Ориентированным графом (directed graph) | называется пара , где - конечное множество вершин, а - множество рёбер. Ребром (edge, дугой(arc), линией(line)) ориентированного графа называют упорядоченную пару вершин .
В графе ребро, концы которого совпадают, то есть , называется петлей. Мультиграф с петлями принято называть псевдографом.
Если имеется ребро
, то говорят:- — предок .
- и — смежные
- Вершина инцидентна ребру , вершина инцидентна ребру
Заметим, что инцидентность — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Граф с
вершинами и ребрами называют - графом. - граф называют тривиальным.Заметим, что по определению ориентированного графа, данному выше, любые две вершины
нельзя соединить более чем одним ребром . Поэтому часто используют другое определение.
Определение: |
Ориентированным графом | называется четверка , где , а и - некоторые абстрактные множества.
Иногда граф, построенный таким образом называют мультиграфом. В мультиграфе не допускаются петли, но пары вершин допускается соединять более чем одним ребром. Такие ребра называются кратными (иначе - параллельные).
Так же для ориентированных графов определяют полустепень исхода вершины
и полустепень захода вершины .Так как у каждого ребра ровно одно начало и ровно один конец выполнено следующее равенство:
.
Определение: |
Путём(маршрутом) в графе называется последовательность вида | , где ; — длина пути.
Определение: |
Циклическим путём называется путь, в котором | .
Определение: |
Цикл - это класс эквивалентности циклических путей на отношении эквивалентности таком, что два пути эквивалентны, если | ; где и - это две последовательности ребер в циклическом пути.
Неориентированные графы
Определение: |
Неориентированным графом (undirected graph) | называется пара , где - конечное множество вершин, а - множество рёбер. Ребром в неориентированном графе называют неупорядоченную пару вершин .
Иное определение:
Определение: |
Неориентированным графом | , где , а и - некоторые абстрактные множества.
Две вершины называются смежными если между ними есть ребро.
Степеню вершины
в неориентированном называют число ребер, инцидентных . Будем считать, что петли добавляют к степени вершины .
Определение: |
Циклическим путём в неориентированном графе называется путь, в котором | , а так же .
Остальные определения в неориентированном графе совпадают с аналогичными определениями в ориентированном графе.
См. также
- Лемма о рукопожатиях
- Ориентированный граф
- Матрица смежности графа
- Связь степени матрицы смежности и количества путей
Литература
- Харари Фрэнк Теория графов = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
- Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — 288 с. — ISBN 5-93972-076-5
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)