Вопрос 40 Графы и их свойства

Графические представления - удобный способ иллюстрации содержания различных понятий, относящихся к другим способам формализованных представлений. Мощным и наиболее исследованным классом объектов, относящихся к графическим представлениям, являются так называемые графы, изучаемые в теории графов.

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

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

Ребро, соединяющее две вершины, может иметь направление от одной вершины к другой; в этом случае оно называется направленным, или ориентированным, или дугой и изображается стрелкой, направленной от вершины, называемой началом, к вершине, именуемой концом.

Граф, содержащий направленные ребра (дуги) с началом v и концом v , называется ориентированным (орграфом), а ненаправленные – неориентированным (назовем н - графом).

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

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

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

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

Локальной степенью (или просто степенью) вершины v н-графа G называется количество ребер r(v), инцидентных вершине v. В н – графе сумма степеней всех вершин равна удвоенному числу ребер m графа, т.е. четна (предполагается, что в графе с петлями петля дает вклад 2 в степень вершины):

= 2m,

Отсюда следует, что в н – графе число вершин нечетной степени четно. Граф, у которого вершины имеют одну и ту же валентность r называют правильным или r-валентным. Вершина изолирована, если её валентность (степень)=0.

Теорема. Во всяком графе с n вершинами всегда сущ-ет по меньшей мере 2 с одинаковыми степенями.

Для вершин орграфа определяются две локальные степени:

· (v) – число ребер с началом в вершине v, или количество выходящих из v ребер;

· (v) – количество входящих в v ребер, для которых эта вершина является концом.

В орграфе суммы степеней всех вершин (v) и (v) равны количеству ребер m этого графа, а значит и равны между собой:

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