Свойства графов

Подграфом G_А графа G=< М, Т> называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими.

Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федерации» [18].

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

Так, карта главных дорог России – подграф карты шоссейных дорог России [18].

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Маршрут – чередующаяся последовательность вершин и ребер, в которой два соседних элемента инцидентны [26].

Если начальная вершина маршрута равна конечной, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью.

Если все вершины (а, значит и ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь – цикл.

Граф без циклов называется ациклическим.

В ориентированном графе цепь называется путем, а цикл – контуром.

Степенью вершины х, обозначаемой deg(х), называют число ребер, инцидентных ей. Если degх=1, то вершина х тупиковая, если degх=0, то вершина изолированная.

Если G – неориентированный граф с n вершинами и m ребрами, а degj – степени j-й вершины, то сумма степеней вершин равна удвоенному количеству ребер:

.

Это следует из того, что каждое ребро добавляет единицу к степени каждой из двух вершин, которое оно соединяет, т.е. добавляет 2 к сумме уже имеющихся вершин. Следствием этого факта является то, что в каждом графе число вершин нечетной степени четно. Для ориентированного графа вводятся понятия полустепень исхода и полустепень захода.