Гамильтоновы графы. Эйлеровы графы. Гамильтоновы графы
 Скачать 0.53 Mb.
|
Эйлеровы графы. Гамильтоновы графы1 2 3 4 5 6 7 8 G 1 2 3 4 5 G 1 2 3 4 5 Уи́льям Ро́уэн Га́мильтон – (4 августа 1805 — 2 сентября 1865) — выдающийся ирландский математик, механик и физик . Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли Достаточные условия гамильтоновости графа Теорема Дирака. Пусть G - неориентированный граф порядка n и m - минимальная степень его вершин. Если n≥3 и m ≥n/2, то G - гамильтонов граф. Теорема Оре. Пусть G - неориентированный граф порядка n. Если n≥3 и deg(u)+deg(v) ≥ n для любых двух различных несмежных вершин u и v , то G - гамильтонов граф. Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2. Необходимое условие гамильтоновости графа ЗаданиеПостроить эйлеров, квазиэйлеров, гамильтонов, квазигамильтонов графы порядка n=F+N, p>n, где F-количество букв в Вашей фамилии, N-количество букв в Вашем полном имени. Описать полученные графы матрицами смежности вершин, смежности ребер, инцидентности, Кирхгофа соответственно. |