Математическое моделирование на графах. Часть 1. Берцун В.Н. - 8 стр.

UptoLike

Составители:

Рубрика:

8 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

Говорят, что вершины графа x, y – смежные, если они соединены

ребром. Поэтому вершины C и D на рис. 1.4 являются смежными, а

D и A – нет.

Рис. 1.4

Граф называется полным, если любые две различные его верши-

ны соединены одним и только одним ребром. Такой граф имеет мак-

симальное число ребер. Каждой вершине в полном графе с n верши-

нами, который в дальнейшем будем обозначать K

, принадлежит (n –

1) ребро. Но в произведении n(n – 1) каждое ребро учитывается

дважды, поэтому в полном графе n(n – 1)/2 ребер. На рис. 1.5 приве-

дены примеры полных графов: K

, K

Рис. 1.5

Граф, не являющийся полным, можно преобразовать в полный,

добавив к нему недостающие ребра. Дополнением графа G называ-

ется граф D с теми же вершинами, что и граф G, и теми и только

теми ребрами, которые необходимо добавить к графу G, чтобы