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. Написать для данного графа матрицы смежности и инцидентности, задать его списком ребер и вершин.
Докажите, что полные (пустые) графы изоморфны тогда и только тогда, когда они имеют одинаковое количество вершин.
Найдите все попарно неизоморфные графы пятого порядка.
Лекция 16. Маршруты, пути, цепи, циклы. Эйлеровы циклы и цепи. Гамильтонов цикл. Взвешенные графы (4 ачса)
План:
1. Маршруты и пути, цепь, цикл.
2. Связность. Компоненты связности.
3. Цикл Эйлера. Граф Эйлера. Теоремы о графах Эйлера, гамильтоновый цикл. Гамильтон Граф.
Ключевые слова: маршрут, пути, цепь, цикл, компоненты связности, цикл Эйлера, граф Эйлера, гамильтоновый цикл, граф Гамильтона.
1. Маршруты и пути, цепь, цикл.
Определение. Последовательность
v1x1v2x2v3...xkvk+1, (где k1, viV, i=1,...,k+1, xjX, j=1,...,k)
в которой чередуются вершины и ребра (дуги) и для каждого j=1,...,k ребро (дуга) xj имеет вид {vj,vj+1} (для орграфа (vj,vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).
Пример
v1x1v2x2v3x4v4x3v2 - маршрут,
x1x2x4x3 - маршрут можно восстановить и по этой записи,
v1v2v3v4v2 - если кратности ребер (дуг) равны 1, то можно и так.
v2x2v3x4v4 - подмаршрут.
Число ребер в маршруте (дуг в пути) называется длиной маршрута (пути).
Маршрут (путь) называется замкнутым, если начальная вершина совпадает с конечной v1=vk+1.
Незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны называется цепью.
Цепь, в которой все вершины попарно различны называется простой цепью.
Замкнутый маршрут (путь), в котором все ребра (дуги) попарно различны, называется циклом (контуром).
Цикл (контур), в котором все вершины попарно различны называется простым.
Теорема. В псевдографе G (в ориентированном псевдографе D) из всякого цикла (контура) можно выделить простой цикл (простой контур).
Доказательство (индукцией).
Пусть k – количество ребер, k+1 – количество вершин в цикле (или контуре).
При k=1 (петля) цикл всегда является простым.
Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.
Теорема. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же начальной и конечной вершинами.
Доказательство || аналогично предыдущему.
Определение. Композицией путей (маршрутов)
1=v1x1v2...xk-1vk, 2=vkxkvk+1...xL-1vL называется путь (маршрут) 1 2=v1x1v2...xk-1vkxkvk+1xk+1...xL-1vL.
Do'stlaringiz bilan baham: |