Теория графов

Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации и линий (ребер), отражающих связи между элементами. Такие рисунки называются графами.

Граф может изображать сеть улиц в городе (вершины – перекрестки, улицы – ребра), блок-схемы программ (вершины – блоки, ребра – переходы), электрические цепи, географические карты и т.д. Более точно, граф определяется как упорядоченная пара (V, E), где V – непустое множество вершин, - множество ребер. Граф будем обозначать G. Число вершин графа называется его порядком и обозначается , число ребер обозначается как . Вершины u и v называются смежными, если существует ребро их соединяющее. Вершина v и ребро e инцидентны, если v является концом е.

Пример 4.1.

Пример 4.2.

Различные ребра графа могут быть инцидентны одной и той же паре вершин, в этом случае они называются кратными, а сам граф – мультиграфом. Ребро может соединять вершину саму с собой, тогда такое ребро называется петлей, а граф – псевдографом. В некоторых задачах инцидентные ребру вершины рассматриваются в определенном порядке, тогда ребру приписывается направление от одной вершины к другой, и ребро называется дугой. Граф, все ребра которого являются дугами, называется орграфом. Иногда ребрам и дугам графа приписывают некоторые числа, такой граф называется взвешенным.

Граф называется помеченным, если всем его вершинам присвоены некоторые метки 1,2,…,n. Степенью вершины v называется число инцидентных ей ребер. Степень вершины обозначается deg v.

Пример 4.3.

Лемма ("о рукопожатиях"). Сумма степеней всех вершин графа равна удвоенному числу его ребер, т.е.

Последовательность степеней вершин графа, записанных в каком-либо порядке, называется степенной последовательностью.

Пример 4.4.

Выпишем степени всех вершин графа в соответствии с их номерами (2,2,3,2,1).