Эйлеровы графы

курсовая работа

1.1.2 Основные понятия, связанные с графом

Определение. Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (то есть ребро вида {v, w}); при этом вершины v и w называются инцидентными этому ребру (а ребро -- инцидентным эти вершинам).

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

Определение.Степенью (или валентностью) вершины v графа G называется число рёбер, инцидентных v.

Степень вершины v обозначается через d(v). Если вершине vинцидентна петля, то принято считать, что при подсчёте степени этой вершины петля даёт две единицы. Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей (или концевой) вершиной. Так, граф, изображённый на рис. 1.2, имеет одну висячую вершину, одну вершину степени 3, одну -- степени 6 и одну -- степени 8.

Легко видеть, что если сложить степени всех вершин графа, то получится чётное число -- равное удвоенному числу рёбер, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный ещё двести лет назад Эйлеру, часто называют леммой о рукопожатиях.

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

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

Так, два графа, изображённые на рис. 1.4, изоморфны при соответствии

u - l, v - m, w - n, x - p, y - q, z - r. Заметим, что эти графы имеют по шесть вершин -- другие точки пересечения рёбер вершинами не являются.

Определение.Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все рёбра принадлежат E(G).

Рисунок 1.4

Определение.Маршрутом в данном графе G называется конечная последовательность рёбер вида {, }, {, }, …, {, } (обозначаемая также через > >> …> ).

Определение.Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все вершины ,, …, различны (кроме, может быть, = ).

Цепь или простая цепь замкнуты, если =.

Определение.Замкнутая простая цепь, содержащая по крайней мере одно ребро, называется циклом.

В частности, любая петля или любая пара кратных рёбер образует цикл.

Определение.Граф G называется связным, если для любых двух его вершин v и w существует простая цепь из v в w.

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

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

Делись добром ;)