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

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

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

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

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

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

Если множества вершин, имеющих четные и нечетные степени соответственно, то, очевидно, четно, так как это конечная сумма четных чисел. Отсюда следует, что

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

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

Рис. 1.5.

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

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

Пусть задан граф . Систему будем называть подграфом графа тогда и только тогда, когда выполняются следующие условия.

для каждого

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

Упражнение 1.1. (см. скан)