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

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

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

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

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

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

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