![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Граф задается множеством точек или вершин х1, х2,..., хn и множеством линий или ребер a1, a2,..., am, соединяющих между собой все или часть точек. Формальное определение графа может быть дано следующим образом.
Графом называется двойка вида
G = (X, A),
где X = {xi}, i = 1, 2,..., n – множество вершин графа, A = {ai}, i = 1, 2,..., m – множество ребер графа.
Графы могут быть ориентированными, неориентированными и смешанными (рис. 1.2). Если ребра у множества A ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом или орграфом (рис. 1.2,а).
Рис. 1.2.
Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.2,б). Граф, в котором присутствуют и ребра, и дуги называется смешанным (рис. 1.2,в). В случае, когда G = (X, A) является орграфом, и мы хотим пренебречь направленностью дуг из множества A, то неориентированный граф, соответствующий G, будет обозначаться и называться неориентированным дубликатом или неориентированным двойником (рис. 1.2,г).
Дуга ai может быть представлена упорядоченной парой вершин (хn, хk), состоящей из начальной хn и конечной хk вершин. Например, для графа G1 (рис. 1.2,а) дуга a1 задается парой вершин (x2, x1), а дуга а3 парой (x2, x3). Если хn, хk – концевые вершины дуги ai, то говорят, что вершины хn и хk инцидентны дуге ai или дуга ai инцидентна вершинам хn и хk.
Дуга, у которой начальная и конечная вершины совпадают, называется петлей. В графе G3 (рис. 1.2,в) дуга a7 является петлей.
Каждая вершина орграфа хi может характеризоваться полустепенью исхода d0(хi) и полустепенью захода dt(хi).
Полустепенью исхода вершины хi — d0(хi) называется количество дуг, исходящих из этой вершины. Например, для орграфа G1 (рис. 1.2,а) характеристики полустепеней исхода следующие: d0(х1)=1, d0(х2)=2, d0(х3)=2, d0(х4)=1.
Полустепенью захода вершины хi — dt(хi) называется количество дуг, входящих в эту вершину. Например, для орграфа G1: dt(х1)=2, dt(х2)=1, dt(х3)=2, dt(х4)=1.
Очевидно, что сумма полустепеней исхода всех вершин графа, а также сумма полустепеней захода всех вершин графа равна общему числу дуг графа, т. е.
ni=1d0(xi)=
ni=1dt(xi)=m
где n – число вершин графа, m – число дуг.
Каждая вершина неориентированного графа хi может характеризоваться степенью вершины d(хi).
Степенью вершины хi – d(хi) называется количество ребер, инцидентных этой вершине. Например, для орграфа G1 (рис. 1.2,б) характеристики степеней следующие: d(х1)=2, d(х2)=3, d(х3)=3, d(х4)=2.
Дата публикования: 2014-11-04; Прочитано: 371 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!