Эйлеровы графы. Гамильтоновы графы. 1 2 3 45 6 78 G. - презентация

1 Эйлеровы графы. Гамильтоновы графы

2

3

4 G

5

6 G

7 Уи́льям Ро́уэн Га́мильтон – (4 августа сентября 1865) выдающийся ирландский математик, механик и физик. Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли

8 Достаточные условия гамильтоновости графа Теорема Дирака. Пусть G - неориентированный граф порядка n и m - минимальная степень его вершин. Если n3 и m n/2, то G - гамильтонов граф. Теорема Оре. Пусть G - неориентированный граф порядка n. Если n3 и deg(u)+deg(v) n для любых двух различных несмежных вершин u и v, то G - гамильтонов граф. Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2. Необходимое условие гамильтоновости графа

9 Задание Построить эйлеров, квазиэйлеров, гамильтонов, квазигамильтонов графы порядка n=F+N, p>n, где F-количество букв в Вашей фамилии, N-количество букв в Вашем полном имени. Описать полученные графы матрицами смежности вершин, смежности ребер, инцидентности, Кирхгофа соответственно.