Введение в теорию графов.
При использовании понятия «граф» в математике чаще всего имеют в виду графическое задание связей между объектами произвольной природы. Например, можно говорить о графическом способе задания связей между атомами в молекуле вещества; структура некоторого подразделения или карта автомобильных дорог представляется графом,
Дадим определение графа. Множество и множество
пар объектов вида
или
из множества
называется графом. Будем обозначать граф
. Множество
называется множеством вершин графа. Элементы множества
вида
называются ребрами графа. Ребро – это неупорядоченная пара вершин, т.е. неважно, какая из вершин в паре является начальной, а какая конечной, поэтому мы и взяли пару в фигурные скобки. Элементы множества
вида
называются дугами графа. Дуга – это упорядоченная пара вершин, указывается начальная и конечная вершина пары, пара берется в круглые скобки. Если в графе начальная и конечная вершины ребра (или дуги) совпадают, то говорят, что в графе имеется петля. Если вершины соединены несколькими ребрами (или дугами), то такие ребра (дуги) называются кратными. Граф, в котором есть кратные ребра (дуги) называется мультиграфом. Псевдографом называется граф, имеющий и петли и кратные ребра (дуги).
Граф, состоящий из вершин и соединяющих их ребер, называется неориентированным графом. Неориентированный граф, не содержащий петель и кратных ребер, называется простым. Граф, состоящий из вершин и дуг – ориентированным или орграфом. Графы, содержащие и дуги и ребра, называются смешанными. При графическом изображении графа вершины обозначаются точками, а ребра (дуги) – линиями, соединяющие соответствующие вершины, для орграфа на дуге ставится стрелка, задающая направление от начальной вершины к конечной.
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.