Введение в теорию графов.

При использовании понятия «граф» в математике чаще всего имеют в виду графическое задание связей между объектами произвольной природы. Например, можно говорить о графическом способе задания связей между атомами в молекуле вещества; структура некоторого подразделения или карта автомобильных дорог представляется графом,

Дадим определение графа. Множество и множество пар объектов вида или из множества называется графом. Будем обозначать граф . Множество называется множеством вершин графа. Элементы множества вида называются ребрами графа. Ребро – это неупорядоченная пара вершин, т.е. неважно, какая из вершин в паре является начальной, а какая конечной, поэтому мы и взяли пару в фигурные скобки. Элементы множества вида называются дугами графа. Дуга – это упорядоченная пара вершин, указывается начальная и конечная вершина пары, пара берется в круглые скобки. Если в графе начальная и конечная вершины ребра (или дуги) совпадают, то говорят, что в графе имеется петля. Если вершины соединены несколькими ребрами (или дугами), то такие ребра (дуги) называются кратными. Граф, в котором есть кратные ребра (дуги) называется мультиграфом. Псевдографом называется граф, имеющий и петли и кратные ребра (дуги).

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

a. б. в.

Рис. 1.

На рисунке 1изображены:

1. а – простой граф;

2. б – неориентированный псевдограф;

3. в - ориентированный псевдограф;

Если - ребро графа, то вершины называются концами ребра , в этом случае также говорят, что ребро соединяет вершины .

Если - дуга орграфа, то вершина называется началом, а вершина - концом дуги , при этом говорят, что дуга исходит из вершины и заходит в вершину .

Если ребро (дуга) соединяет вершины , то говорят, что ребро (дуга) инцидентно вершинам и или вершины и инцидентны ребру (дуге) .

Вершины графа, соединенные хотя бы одним ребром, называются смежными.

Вершина графа, не смежная ни с какой другой вершиной этого графа, называется изолированной.

Два ребра называются смежными, если они имеют общую вершину.

Степенью вершины v неориентированного графа, обозначаемой называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной, степени 1 – висячей. Петля учитывается дважды. Например, для псевдографа, изображенного на рисунке 1. б, z – висячая вершина, , .

Полустепенью выхода (исхода) вершины v в орграфе D называется числодуг орграфа, исходящих из вершины v. Например, для орграфа на рис. 1. в , . Если , то вершина v называется стоком.

Полустепенью входа (захода) вершины v в орграфе D называется числодуг орграфа, заходящих в вершину v. Например, для орграфа на рис. 1. в , . В случае ориентированного псевдографа вклад каждой петли, инцидентной некоторой вершине v , равен 1, как в , так и в . Если , то вершина v называется источником.

Справедливы следующие теоремы.

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

2. В неориентированном графе число вершин нечетной степени четно.

Граф называется подграфом графа , если и . Таким образом, каждая вершина в является вершиной в , и каждое ребро в является ребром в .

На рисунке 2 приведены граф и его подграфы.

Рис. 2.

Два графа и изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин и ребер, что соответствующие ребра графов инцидентны соответствующим вершинам этих графов. Другими словами, если вершины и в соответствуют вершинам и в , то ребро в , имеющие концевые вершины и должно соответствовать ребру в , имеющие концевые вершины и и наоборот. На рисунке 3 изображены изоморфные графы.

Рис. 3.