Связность графов

Лекции по Дискретной математике Лекция 5 Связность графов Маршруты и пути в графе n Последовательность v1e1v2e2 …. vk-1ek-1vk – маршрут, при условии, что соседние элементы последовательно инцидентны. n e1e2 ….ek-1 - маршрут из ребер n v1v2….vk-1vk – маршрут из вершин n Цепь (в орграфе - путь) – маршрут, в котором каждое ребро в смежности встречается только однажды. . Простая цепь n Цепь, содержащая вершины ровно по одному разу, называется простой. Всякий маршрут графа содержит простую цепь. Замкнутая цепь называется циклом (в орграфе - контур). Граф без циклов называется ациклическим. Пример маршрутов и цепей графа Пути: * gc * edabc *ef *abc Маршруты: * abcgcbedf * def * abefdebcg * abedfeba Цепи: * adebcg (простая) * dfedab *adfeba (простая замкнутая) Циклы Цепь называется замкнутой (цикл), если ее концами является одна и та же вершина Цикл орграфа называется орцикл (контур) Количество непересекающихся циклов в графе называется цикломатическим числом Мощность цикла - количество ребер, образующих этот цикл Пример графа с циклом Цикл: * abdea Циклы: * abeda * defd * abefda * abedfeba * adeba * dfed *adfeba Отношение связности n Две вершины графа связны, если между ними существует маршрут. n Граф, в котором все вершины попарно связны, называется связным. n Связность есть отношение эквивалентности. n Классы эквивалентности по отношению связности называются компонентами связности графа. Связность графа 3 2 a a 2 c b d 4 1 Связный граф – одна компонента связности 3 4 3 4 d 1 Несвязный граф – две компоненты связности 2 d 1 Несвязный граф – три компоненты связности Отношение связности орграфа n Две вершины сильно связны, если существует путь из первой вершины во вторую и обратно. n Две вершины односторонне связны, если существует путь из одной вершины в другую, но нет пути из второй в первую. n Орграф без контуров с одним источником и одним стоком, с рёберной нагрузкой, называется сетью. Кенигсбергские мосты Эйлеров граф n Замкнутая цепь, содержащая каждое ребро графа ровно один раз, называется эйлеровым циклом n Граф с эйлеровым циклом называется эйлеров граф n Открытая цепь, содержащая каждое ребро графа ровно один раз называется эйлеровой цепью n Граф с эйлеровой цепью называется полуэйлеровым Примеры графов Не эйлеров полуэйлеров эйлеров Теорема Эйлера . конечный неориентированный граф эйлеров тогда и только тогда, когда: 1) он связен; 2) он нетривиален; 3) каждая вершина имеет четную степень. конечный неориентированный граф полуэйлеров тогда и только тогда, когда: 1) он связен; 2) он нетривиален; 3) ровно две вершины имеют нечетную степень. Для орграфа эйлеровость характеризуется равенством входов и выходов у каждой вершины. Гамильтонов граф n Если в простом цикле каждая вершина графа встречается ровно один раз, то цикл гамильтонов. n Граф, содержащий гамильтонов цикл, называется гамильтоновым графом. n Если открытая цепь проходит через все вершины графа ровно один раз, то цепь гамильтонова n Граф полугамильтонов, если в нем содержится гамильтонова цепь Гамильтоновы графы Не гамильтонов полугамильтонов гамильтонов Теоремы о гамильтоновых графах n Теорема Дирака: Если в графе степени всех вершин >=|V|/2, то граф гамильтонов. n Теорема: Если в графе есть гамильтонова цепь из х в у и имеется ху – ребро графа, то суграф без ребра ху – полугамильтонов.