Спирина, М.С. Дискретная математика

На рис. 2.1, в вершина А имеет степень, равную 1, вершина С — 4 , вершина D — 2. Записывается это в виде: deg (А)= 1, deg (С) = 4, deg (D )- 2- Граф G4 (рис. 2.1, г) содержит пять вершин V= {А, В, С, D ,E} и шесть ребер Х= {р, д, г, s, t, и}. Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, н а ­ зывается нуль-графом. Для нуль-графа Х=0 . Вершина графа, име­ ющая степень, равную 1, называется висячей. На рис. 2.1, г вер ­ шина Е — изолированная: deg (Е) = 0, а вершины А, В, Е, G, Н на рис. 2.1, в — висячие. Теорема 2.1. В графе G{ V,X) сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа : S d e g ( ^ ) = 2т, /=1 где п - |F| — число вершин; т - \Х \— число ребер графа. Ч6ТНОИ ЧСТНОР Вершина называется ----------- если ее степень — —- — нечетнои нечетное число. На рис. 2.1, в deg (D) =2, deg (Е) = 3, значит, у графа G3 верши­ на D является четной, а F — нечетной. В теории графов доказана следующая теорема. Теорема 2.2. Число нечетных вершин любого графа — четно. Следствие. Невозможно начертить граф с нечетным числом нечетных вершин. Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Полным я в ­ ляется граф G2 на рис. 2.1, б. Таким образом, полный граф опре­ деляется только своими вершинами. Пусть число вершин полного графа п. Тогда степень любой вершины, очевидно, равна deg ( V) = = п - 1, а число ребер равно числу сочетаний из п по 2, т. е. т = С}. Число ребер также можно найти по теореме 2.1: w ^ X deg (Г/) = - | « deg (V) = = d . Дополнением графа G{V, X) называется граф G(V, X') с теми же вершинами V, что и граф G, и имеющий те и только те ребра X', которые необходимо добавить к графу G, чтобы он стал п о л ­ ным. Очевидно, что граф с кратными ребрами не имеет дополне­ ния. Напримещ дополнением графа G5 до графа G2 на рис. 2.1, б является граф Gb (рис. 2.2). Как отмечалось в подразд. 1.2, дополнением универсального множества является пустое, и наоборот. Поскольку граф и его д о ­ полнение отличаются только ребрами (множества X и X ') и допол­ нение графов сводится к дополнению множества X, то частным 71