Графы; циклы

ДИСКРЕТНАЯ МАТЕМАТИКА ГРАФЫ. ЦИКЛЫ Преподаватель: Шилова З.В. 3. Виды графов Связный граф Цепь: простая цепь, цикл Простой цикл Эйлеров цикл Гамильтонов цикл Путь, цикл Открытая цепь называется путем, если все ее вершины различны (v1, e1, v2, e2, v3). Цикл – это замкнутая цепь ( простой цикл, если цепь простая) (v1,e1,v2,e3,v5,e6,v4,e5,v1). Число ребер в пути называется длиной пути. Аналогично определяется длина цикла. G 3 Цепь и цикл Путь ― граф P = ({v1,…,vk+1 },{e1,…,ek}) такой, что vi ≠ vj для 1≤ i < j ≤ k+1, и последовательность v1,e1,v2 ,e2 ,…,vk ,ek ,vk+1 является обходом. Циклом называется граф ({v1,…,vk }, {e1,…,ek}) такой, что последовательность v1,e1,v2 ,e2 ,…,vk ,ek ,v1 является замкнутым обходом и vi ≠ vj for 1 ≤ i < j ≤ k +1. Длина пути и цикла ― число его ребер. Гамильтонов цикл Простой цикл, который проходит через все вершины графа, называется гамильтоновым (У. Р. Гамильтон, 1805—1865). Задача коммивояжера (о странствующем торговце). Пусть имеется несколько связанных между собой пунктов (городов). Выходя из фиксированного пункта, коммивояжер должен вернуться в него, посетив все пункты ровно один раз. При этом пройти маршрут за самое короткое время или с минимальными затратами на транспорт. Рис. Граф, имеющий гамильтонов цикл Рис. Граф, не имеющий гамильтонов цикл Эйлеров цикл (граф) Плоский эйлеров граф можно изобразить одним росчерком пера, при этом начальная и конечная вершины совпадут. На рис. изображен граф, обход всех ребер которого ровно один раз возможен по маршруту: а1, а2, а3, а4, а5, а6 и а7. Теорема: конечный неориентированный граф эйлеров существует тогда и только тогда, когда он связан и степени всех его вершин четны степени его вершин х1 х2 и х4 — 2, вершин х3 и х5 — 4. Рис. Эйлеров граф Расстояние Расстоянием (dist(v,w), distG(v,w) ) для двух вершин v и w называется длина кратчайшего v-w-пути в G. Если такого пути нет, то есть w недостижима от v, полагаем dist(v,w) = ∞. В неориентированном случае dist(v,w) = dist(w,v) для всех v, w V (G). Cвойства путей и циклов 1. Степень каждой неконцевой вершины пути равна 2, концевые вершины имеют степень, равную 1. 2. Каждая вершина цикла имеет степень 2 или другую четную степень. Обращение этого утверждения, а именно то, что ребра подграфа, в котором каждая вершина имеет четную степень, образуют цикл, — неверно. 3. Число вершин в пути на единицу больше числа ребер, тогда как в цикле число ребер равно числу вершин. 8