Основные определения, способы задания,

Основные классы, изоморфизм графов

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

Вершина  и  инцидентны друг другу, если вершина является для этого ребра концевой точкой.

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

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

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

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

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

Ребро, концевые вершины которого совпадают, называется петлей.

Граф называется конечным, если множество его элементов (вершин и ребер) конечно.

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

Простым графом называется граф без петель или кратных ребер.

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

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

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

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

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

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

Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности.

Для описания вершин и ребер достаточно их занумеровать.

Пусть  вершины графа;  ребра графа G.

Отношение инцидентности задается:

а) матрицей инцидентности  размера  (строкам соответствуют ребра, столбцам – вершины графа), в которой

для н-графа 

для ор-графа

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

в) матрицей смежности  размера , столбцам и строкам которой соответствуют вершины графа. Для н-графа  равно количеству ребер, инцидентных i-й и j-й вершинам, для ор-графа  равно количеству ребер с началом в i-й и концом в j-й вершине.

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

Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Перенумерация вершин и ребер графа задается соответственно строками  и  новых номеров вершин и ребер, расположенных в исходном порядке.

Степени вершин графа

(Локальной) Степенью или (валентностью)  вершины называется число ребер, инцидентных вершине v.

Если не оговаривается особо, то петля учитывается дважды при подсчете валентности вершины.

Граф называется правильным (с валентностью r) или r-валентным графом (регулярным, однородным), если степени всех его вершин равны.

Вершина называется изолированной, если она несмежна ни с одной из вершин графа, или, что то же самое, неинцидентна ни одному ребру. Степень этой вершины равна 0.

Вершина, имеющая степень, равную 1, называется висячей (концевой). Ребро, инцидентное висячей вершине, называют концевым.

Утверждение 1. (лемма о рукопожатиях): В н-графе сумма степеней всех вершин равна удвоенному числу ребер (т.е. четна): , где m – число ребер.

Следствие 1. Произвольный граф имеет четное число вершин нечетной степени.

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

В ор-графе две (локальных) степени вершины:  и  число ребер с началом и концом в v соответственно.

Утверждение 2.Суммы степеней всех вершин ор-графа равны количеству ребер этого графа и, следовательно, равны между собой: , m – число ребер.

Части, суграфы и подграфы

Граф H называется частью графа G ( ), если множества его вершин и ребер содержатся в множествах вершин и ребер графа G:

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

Подграфом  графа  с множеством вершин  называется часть графа, которой принадлежат все ребра инцидентные

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

Операции над частями графа

Дополнение  к части H определяется множеством всех ребер графа G, не принадлежащих H:

, ;

Сумма  частей  и  графа G, это граф, у которого

 и ;

Произведение  частей  и  графа G, это граф, у которого

 и .

Части  и  не пересекаются по вершинам, если они не имеют общих вершин, а значит и общих ребер:

, .

Части  и  не пересекаются по ребрам, если

.

Если , то сумма  называется прямой.

Графы и бинарные отношения

Отношению R, заданному на множестве V, взаимно однозначно соответствует ориентированный граф G(R) без кратных ребер с множеством вершин V, в котором ребро  существует, только если выполнено . Симметричному отношению R взаимно однозначно соответствует неориентированный граф без кратных ребер G(R). Антисимметричному отношению R взаимно однозначно соответствует ориентированный граф без кратных ребер, не содержащий пар вершин с ребрами, противоположно направленными к разным вершинам. Если R рефлексивно, то граф G(R) без кратных ребер имеет петли во всех вершинах. Если R антирефлексивно, то граф G(R) без кратных ребер не имеет петель. Если R транзитивно, то в графе G(R) без кратных ребер для каждой пары ребер  и  имеется замыкающее ребро . Пусть  – дополнение отношения R на V: , где U –универсальное (полное) отношение , т.е. отношение, имеющее место между любой парой элементов из V.

Граф G( ) является дополнением графа G(R) (до полного орграфа K с множеством вершин V и множеством ребер ).

Граф обратного отношения G( ) отличается от графа G(R) тем, что направления всех ребер заменены на обратные.

Граф объединения двух отношений, заданных на V,  является графом суммы двух графов  и :

.

Граф пересечения отношений на V,  является графом пересечения двух графов  и :

.

УПРАЖНЕНИЯ

1. Для приведенных графов построить матрицу инцидентности и матрицу смежности. Найти степени вершин графа. Определить свойства отношения, которому соответствует граф.

             .

                Рис. 1                                                 Рис. 2

2. Для приведенных графов построить матрицу инцидентности. Стереть рисунок. Найти степени вершин по матрице инцидентности.

Рис. 1                                                Рис. 2

3. Для приведенных графов построить матрицу смежности. Стереть рисунок. Найти степени вершин по матрице смежности.

Рис. 1                                                     Рис.2

4. Дана матрица инцидентности графа. Задать граф рисунком.

1)                            2)                             3)

5. Дана матрица смежности неориентированного графа. Задать граф рисунком.

1)                                 2)                                     3)

6. Дана матрица смежности орграфа. Задать граф рисунком.

1)                                 2)                                    3)

7. Дана матрица смежности. Построить соответствующий ей неориентированный и ориентированный графы.

1)                                      2)                                        3)

8. Для графа G, приведенного на рисунке определить различные части графа:

 – подграф общего вида;

 – суграф не покрывающий;

 – суграф покрывающий;

 – подграф, порожденный множеством вершин

 – звездный граф (для некоторой выбранной вершины);

Найти сумму  и , будет ли эта сумма прямой?

Найти пересечение  и .

Найти дополнение до графа G частей ,  и .

Рис. 1                                             Рис. 2

Рис. 3                                                            Рис. 4

9. Для графа G, изображенного на рисунке:

Определить, является ли следующая часть  ( ) графа G подграфом, суграфом, покрывающим суграфом, если:

1) ,       ;

2) ,       ;

3) ,      ;

4) , ;

5) ,            .

Выполнить операции над ,  и .

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

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

Указание: для проверки изоморфизма построить матрицы смежности.

1)

2)

12. Среди пар графов, изображенных на рисунке, указать пары изоморфных графов и пары неизоморфных графов. Ответ обосновать.

1)
2)

13. Задать различными способами, определенные ниже графы G. Определить их типы, построить дополнения , если   – треугольник;  – четырехугольник;  – пятиугольник.