5.2. Основные понятия и определения

Определение. Пусть даны 2 множества: V = {v₁,v₂,...} и E = {(v_i,v_j)/ v_i,v_j V}. Тогда пара (V,E) есть граф, где V – множество вершин, E – множество ребер.

Мы будем рассматривать такие графы, в которых множества V и E конечны, такие графы называются конечными.

Все графы делятся на 2 группы:

1. ориентированные графы или орграфы (когда важен порядок вхождения вершины в пару, которая определяет ребро);

2. неориентированные графы (когда порядок вхождения вершины в пару не важен).

Замечание. По умолчанию граф неориентирован.

Определение. Ребро вида называется петлей.

Определение. Ребра вида , , где , называются кратными.

Определение. Пусть |V| = p, |E| = q, тогда граф, содержащий p вершин и q ребер, называется (p,q)-графом.

Если G – (p,q)-граф, то p(G) – число вершин в графе G, q(G) – число ребер в графе G.

Определение. Вершины и называются смежными, если ребро из E вида (если ребро, которое их соединяет). В этом случае также говорят, что вершина и ребро инцидентны друг другу.

5.3. Способы задания графа

Пусть дан граф G = (V,E) = (p,q).

1. Перечисление: Сначала перечисляем элементы множества V:

, а потом – элементы множества Е: .

Пример 1: V=,

E = ,

где , – кратные ребра, – петля, (V,E) – неориентированный граф.

2. Матрица смежности имеет p строк и p столбцов. На (i, j)-м месте

стоит число, которое означает, сколько ребер типа . В орграфе мы будем ставить число со знаком «+», если ориентирован от к и «–», если наоборот (от к ). Матрица является диагональной.

3. Матрица инцидентности. Инцидентность – геометрический термин, употребляемый для обозначения () отношения принадлежности между основными объектами. Дана матрица, которая содержит p столбцов и q строк. На пересечении i-й строки и j-го столбца стоит число 0 или 1, которое означает инцидентно ли данное ребро данной вершине.

4. С помощью диаграммы вершины графа изображаем точками на плоскости, а ребра – линиями, соединяющими соответствующие точки.

5.4. Некоторые соотношения в графе

Определение. Пусть , тогда – число ребер, инцидентных вершине (число называют степенью вершины).

Замечание. В примере 1 (с. 78) . Если , то вершина изолирована.

Утверждение. Пусть – граф без петель. Тогда .

Доказательство очевидное. Каждое ребро дает в сумму вклад 2, так как оно учитывается 2 раза.

Определение. Пусть G – граф без петель и кратных ребер. Тогда он называется полным, если любые две его вершины смежны. Полный граф обозначим через K_p, где p – число его вершин.

Замечание. Совершенно очевидно, что в полном графе число его ребер

.

Пример:

K4: K5: K3:

, ,

Определение. Пусть дан граф , тогда называетсяподграфом графа , если и .

Определение. Маршрутом в графе G называется последовательность ребер вида: ;

цепью – такой маршрут, в котором все ребра различны;

циклом – замкнутый маршрут.

В примере 1

–маршрут и цепь;

–цикл.

Определение. Граф называется связным, если для любых двух его вершин существует маршрут, который их соединяет, т.е. . В противном случае граф называется несвязным.

Замечание. Так как мы имеем дело с конечными графами, то любой граф можно представить в виде конечного объединения связных подграфов. Такие подграфы называются компонентами связности.