1.5. Термины, описывающие локальные свойства

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

Если e~(v&w), то будем называть v и w граничны­ми точками е независимо от того, является граф геомет­рическим или нет. Если v — w, тогда v — единственная граничная точка е, а е называется петлей. Если «i~ (v&w) ие₂~ (v&w), тогда в\ и е₂ называются парал­лельными ребрами. В частности, две петли, инцидентные одной и той же вершине, являются параллельными. Гово­рят, что вершины v и w смежные, если существует, по крайней мере, одно ребро е такое, что е~ (v&w). В част- вости, вершина v смежна сама с собой, если существует аетля, инцидентная и; в противном случае v не может быть смежной сама с собой. Аналогично ребра е\ и е₂ называются смежными, если они имеют, по крайней ме­ре, одну общую граничную точку. Заметим, что смеж­ность является отношением между двумя подобными 9ле- *• ч,

ментами (между вершинами или между-ребрами), тогда как инцидентность есть отношение между разнородными элементами.

Число ребер, инцидентных вершине v (петля учиты­вается дважды), называется степенью вершины v и обоз­начается б (и). Говорят, что вершина v изолирована, ес­ли 6(у)=0. В частности, вырожденным графом назы­вается граф, у которого все вершины изолированы.

Пусть S — любое конечное множество. Обозначим че­рез |S| число элементов в множестве S. Таким образом, |У| и |£| — число вершин и ребер конечного графа G=(V, Е) соответственно. Учитывая, что появление каж­дого нового ребра добавляет по единице к степеням двух вершин (или в случае петли два к степени одной вершины), имеем

2б(о) = 2|£1.

Если V₀ и Vi — множества вершин, имеющих четные и нечетные степени соответственно, то, очевидно, 2 (v)

V€=V₀

четно, так как это конечная сумма четных чисел. Отсюда следует, что

2 «и- 2 б(в)= 2б(»)

U(EEV UfcsVo vg^Vi

также обязательно четно, что доказывает следующую

теорему.

Теорема 1.3. В ко­нечном графе число вершин нечетной сте­пени четно.

Для лучшего усвое­ния введенной выше терминологии проил­люстрируем ее на при- .у мере г{>афа, изобра-

^я женного на рис. 1.5.

Граничными точками р_ис j g ребра в\ являются вер­

шины Vz и v₂. Петля е₄ имеет единственную граничную точку v_x. Ребро е₂ смежно ребру е\ и парал­лельно ребру е_г. (Заметим, что параллельные ребра яв-

11 Эта теорема впервые установлена, но не опубликована Ж, С. Повтрягиным. Позднее независимо от него доказана Куратов- : В дальнейшем мы будем ее называть второй теоремой Понтря«

шн — Куратовского. (Прим. ред.)

fa- щ ;. Т. Саатн