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

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

Цикл называется эйлеровым, если он содержит все ребра графа.

7

2

4

5

3

1

6

G

7

8

1

2

G

5

2

1

3

4

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

n , где F- количество букв в Вашей фамилии, N- количество букв в Вашем полном имени. Описать полученные графы матрицами смежности вершин, смежности ребер, инцидентности, Кирхгофа соответственно. " width="640"

Задание

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