Линейность является характерной чертой большинства современных естественных и искусственных языков. Линейное представление информации (в виде последовательности символов) не является естественным с точки зрения человеческого восприятия. Использование нелинейных форм во многих случаях существенно облегчает понимание. В математике главным средством нелинейного представления информации служат чертежи. Один из видов чертежей – графы, которые, сохранив присущую чертежам наглядность, допускают точное теоретико-множественное описание и тем самым становятся объектом математического исследования.
В разных задачах удобно использовать чертежи разных типов. Соответственно определенные вариации допускает и определение графа. Неотъемлемыми атрибутами графов (при всем разнообразии определений) являются вершины и соединяющие их ребра или дуги.
Граф G = (V, E) состоит из конечного множества вершин (или узлов) V и конечного множества ребер E. Каждое ребро связывает (соединяет) пару вершин. Если ребро a соединяет вершины x и y, то говорят, что ребро a и вершины x, y инцидентны.
Например, на рис. 1
1 a 2
b e g c
f 6
4 h 5 d 3
Рис. 1
изображен граф с шестью вершинами, обозначенными цифрами
1, 2, 3, 4, 5, 6, и восемью ребрами, обозначенными буквами a, b, c, d, e, f, g, h. Ребро a связывает вершины 1 и 2; ребра e и f связывают вершины 1 и 4; ребро g связывает вершину 2 саму с собой; вершина 1 инцидентна ребрам a, b, e, f; ребро c инцидентно вершинам 2 и 3.
Два ребра, связывающие одну и ту же пару вершин (как e и f), называют параллельными (или кратными); ребро, связывающее вершину саму с собой (как g), называют петлей. Иногда в определении графа запрещают наличие параллельных ребер и/или петель, иногда нет. Мы не будем жестко фиксировать определение, оговаривая специально, если это оказывается существенным, какого типа граф рассматривается.
Пусть G = (V, E) – некоторый граф. Граф G′ = (V′, E′), вершины и ребра которого являются вершинами и ребрами графа G, т.е. V′⊂V, E′⊂E называется подграфом графа G.
Степенью вершины графа называется число ребер графа, инцидентных этой вершине (петли считаются дважды). Степень вершины v обозначается (v). Вершина степени 0 называется изолированной, вершина степени 1 – висячей. Так, для графа на рис. 1 имеем: (1) = (2) = (3) = 4, (4) = 3, (5) = 1, (6) = 0; вершина 5 – висячая, вершина 6 – изолированная.
Несложно убедиться в справедливости следующего
соотношения:
∑д(v) 2m ,
v∈V
где m – число ребер графа G = (V, E). В самом деле, ребро, соединяющее вершины x и y, вносит вклад по единице в слагаемые : (x) и (y) (при x = y ребро является петлей и в соответствии с определением вносит вклад 2 в одно слагаемое (x)).
В некоторых случаях рассматриваются направленные ребра,
которые называют дугами. Для дуги, соединяющей две вершины, указывают, из какой вершины она выходит (начало дуги), и в какую входит (конец дуги). На рисунке направление дуги указывают стрелкой. Если все ребра графа направлены, его называют ориентированным графом, или орграфом. В орграфе параллельными считаются дуги, соединяющие одинаковые вершины и имеющие одинаковое направление, то есть дуги, имеющие общее начало и общий конец. Когда мы, имея в виду
ориентированный граф, говорим, что дуга a соединяет вершины
x и y, предполагается, что дуга a направлена от x к y.
На рис. 2 изображен орграф. Из вершины 1 выходят дуги a
и b, в нее входит дуга e.
1 a 2
b e c
4 3
d
Рис. 2
Полустепенью исхода вершины орграфа называется число дуг графа, начинающихся в этой вершине; полустепенью захода
– число дуг графа, заканчивающихся в ней. Полустепени исхода и захода вершины v обозначаются соответственно через +(v) и –(v). Так, для графа на рис. 2 имеем +(1) = 2, –(1) = 1.
Для ориентированного графа G = (V, E), содержащего m дуг,
выполняется следующее соотношение:
∑д (v) ∑д− (v) m .
v∈V
v∈V
Вершины и дуги графа могут быть дополнительно помечены. В этом случае говорят о нагруженном, или взвешенном, графе.
Подграфом орграфа G называют любой орграф, вершины которого составляют часть множества вершин графа G, а дуги – часть множества его дуг.
f 6
b e c