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

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

Рисунок 1.8

Рисунок 1.9 Рисунок 1.10

Двудольные графы

Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества итак, что каждое ребро в G соединяет какую-нибудь вершину изс какой-нибудь вершиной из(рис. 1.10); тогда G называется двудольным графом. Такие графы иногда обозначают G(, ), если хотят выделить два указанных подмножества. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина изсоединена с каждой вершиной из ; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается , где m и n - число вершин соответственно ви . Например, на рис. 1.11 изображён граф . Заметим, что графимеет ровно m+nвершин и mn рёбер.

Рисунок 1.11

Связные графы

Почти все графы, рассмотренные до сих пор, состояли «из одного куска». Исключением были вполне несвязные графы(n ≥ 2) и объединения графов, состоящие из «не соединённых друг с другом частей». Формализуем это различие, называя граф связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае. Очевидно, что всякий несвязный граф Gможно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой (связности) графа G. На рис. 1.12 изображён граф с тремя компонентами.

Рисунок 1.12

Дополнение простого графа

Пусть G - простой граф с множеством вершин V(G).

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

Отсюда следует, что если граф Gсодержит nвершин, то граф можно построить, удалив из графа все рёбра, принадлежащие G(здесь G считается подграфом). Заметим, что дополнение полного графа является вполне несвязным графом и наоборот; дополнение регулярного графа регулярно.

.2 Эйлеров и полуэйлеров графы

.2.1 Определение эйлерова и полуэйлерова графа. Примеры

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

Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый граф будет полуэйлеровым. На рис. 1.13 и 1.14 изображены соответственно полуэйлеров и эйлеров графы. Заметим, что предположение о связности графа Gвведено только ради удобства, так как оно позволяет не рассматривать тривиальный случай графа, содержащего несколько изолированных вершин.

Рисунок 1.13 Рисунок 1.14

.2.2 Решение задачи Эйлера о семи кёнигсбергских мостах

Начало теории графов как раздела математики связывают с так называемой задачей о кёнигсбергских мостах. Эта знаменитая в своё время задача состоит в следующем.

Семь мостов города Кёнигсберга (ныне Калининград) были расположены на реке Прегольтак, как изображено на рис. 1.15. Спрашивается, можно ли, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому

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