Построение.

Один и тот же граф можно изобразить по-разному.

Примеры

Замечание 1. Не всегда точка пересечения ребер принимается за вершину, например, на рис. точка А – не вершина.

Замечание 2. Диаграмма графа наглядно иллюстрирует его свойства. Но не надо отождествлять эти понятия прежде всего потому, что одному и тому же графу можно поставить в соответствие внешне различные диаграммы. Например, графу , где , , можно поставить в соответствие диаграмму рис.3. Здесь по ошибке точку пересечения ребер (b,e) (c,d) можно принять за вершину, которой она не является. Этот же граф можно изобразить на рис. 4, 5, 6, на которых ребра пересекаются только в вершинах.

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

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

Пример: мультиграф кенигсбергских мостов

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

Замечание. В полном графе каждая его вершина принадлежит одному и тому же числу ребер.

Определение 6. Если ребро соединяет вершины и , то говорят, что оно инцидентно вершине а и вершине b. Эти вершины называются смежными и инцидентными ребру . Два ребра называются смежными, если они инцидентны одной вершине.

Определение 7. Матрицей смежности называется квадратная матрица , строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент равен числу дуг, идущих из вершины x_i в вершину x_j. Если исходящих дуг нет, то .

Пример. Составить матрицу смежности графа

Решение.Граф имеет 4вершины, следовательно, матрица смежности имеет размерность . Наличие ребер: 1 в 1 – нет ребра, 1 в 2 – есть ребро, 1 в 3 – есть ребро, 1 в 4 – нет ребра. Следовательно, первая строка имеет вид: 0 1 1 0.

Вершина 2 соединена только с вершиной 1, следовательно, вторая строка имеет вид: 1 0 0 0. Вершина три – изолированная, следовательно, третья строка – нулевая. Вершина 4 соединена ребром с вершиной 1 и дугой с самой собой, следовательно, четвертая строка: 1 0 0 1.

Тогда матрица смежности имеет вид: .

Определение 8. Матрицей инцидентности или инциденций называется прямоугольная матрица , строки которой соответствуют вершинам графа, а столбцы – ребрам. Если вершина x_i и ребро u_j инцидентны, то , и в противном случае.

Пример. Составить матрицу инциденции для графа.

Решение. Обозначим ребра как u₁, u₂, u₃, u₄.

Матрица имеет вид: .

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

Определение 9. Граф Г называется подграфом графа G, если все вершины и ребра графа Г принадлежат графу G.

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