Читать курсовая по математике: "Эйлеровы графы" Страница 3

(Назад) (Cкачать работу)

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

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

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

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

Рисунок 1.4

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

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

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

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

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

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

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

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

.1.3 Примеры графов

Вполне несвязные графы

Определение.Граф, у которого множество рёбер пусто, называется вполне несвязным (или пустым) графом.

Будем обозначать вполне несвязный граф с nвершинами через ;показан на рис. 1.5. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

Рисунок 1.5

Полные графы

Определение.Простой граф, в котором любые две вершины смежны, называется полным графом.

Полный граф с n вершинами обозначается через . Графы иизображены на рис. 1.6 и 1.7.

Рисунок 1.6 Рисунок 1.7

Регулярные графы

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

Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3 называются кубическими (или трёхвалентными) графами. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф- регулярным степени n-1.

Платоновы графы

Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и

Похожие работы