Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

a	b	c
d
a	0	1	1	0
b	1	0	1	0
c	1	1	0	1
d	0	0	1	0

	u	v	w	x
a	1	0	0	0
b	1	1	1	0
c	0	1	0	1
d	0	0	1	1

8. Написать для данного графа матрицы смежности и инцидентности, задать его списком ребер и вершин.

8. 
   Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.
   
9. 
   Найдите все попарно неизоморфные графы пятого порядка.
   

Лекция 16. Маршруты, пути, цепи, циклы. Эйлеровы циклы и цепи. Гамильтонов цикл. Взвешенные графы (4 ачса)
План:
1. Маршруты и пути, цепь, цикл.
2. Связность. Компоненты связности.
3. Цикл Эйлера. Граф Эйлера. Теоремы о графах Эйлера, гамильтоновый цикл. Гамильтон Граф.
Ключевые слова: маршрут, пути, цепь, цикл, компоненты связности, цикл Эйлера, граф Эйлера, гамильтоновый цикл, граф Гамильтона.


1. Маршруты и пути, цепь, цикл.
Определение. Последовательность
v₁x₁v₂x₂v₃...x_kv_k+1, (где k1, v_iV, i=1,...,k+1, x_jX, j=1,...,k)
в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) x_j имеет вид {v_j,v_j+1} (для орграфа (v_j,v_j+1)), называется маршрутом, соединяющим вершины v₁ и v_k+1 (путем из v₁ в v_k+1).

Пример

v₁x₁v₂x₂v₃x₄v₄x₃v₂ - маршрут,

x₁x₂x₄x₃ - маршрут можно восстановить и по этой записи,
v₁v₂v₃v₄v₂ - если кратности ребер (дуг) равны 1, то можно и так.
v₂x₂v₃x₄v₄ - подмаршрут.
Число ребер в маршруте (дуг в пути) называется длиной маршрута (пути).
Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v₁=v_k+1.
Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).
Цикл (контур), в котором все вершины попарно различны называется простым.
Теорема. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).
Доказательство (индукцией).
Пусть k – количество ребер, k+1 – количество вершин в цикле (или контуре).
При k=1 (петля) цикл всегда является простым.
Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: v_i=v_j, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между v_iи v_j (вместе с v_j). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.

Теорема. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.
Доказательство || аналогично предыдущему.
Определение. Композицией путей (маршрутов)
₁=v₁x₁v₂...x_k-1v_k, ₂=v_kx_kv_k+1...x_L-1v_L называется путь (маршрут) ₁ ₂=v₁x₁v₂...x_k-1v_kx_kv_k+1x_k+1...x_L-1v_L.