Что называется маршрутом циклом и цепью графа
Маршруты, пути, цепи, циклы
Тема 4.2. Маршруты и деревья
Резюме по теме
Вопросы для повторения
1.Чему посвящен раздел дискретной математики, изучающий теорию графов?
2.В чем отличие ориентированного и неориентированного графов?
3.Дайте определение графа?
4.В чем заключается смысл отношения инцидентности?
5.Локальная степень вершины графа это?
6.В каком случае графы называются изоморфными?
7.Назовите способы задания графов?
8.Перечислите отличия матрицы инцидентности и матрицы смежности?
9.Когда граф называется частью графа?
Рассматривается раздел дискретной математики изучающий теорию графов. Приведены основные понятия теории графов такие, как вершина, ребро, ориентированный граф и так далее. Дано понятие локальной степени. Показаны способы задания графов с их демонстрацией. Отдельно рассмотрены операции над частями графа, а так же графы и бинарные отношения.
Цель: изучить различные виды конструкций графов.
Задачи:
1 Рассмотреть понятия маршрут, путь, цепь и цикл применительно к графам.
2 Рассмотреть структуру графа дерева и леса.
Пусть G – неориентированный граф.
Маршрутом в G называется такая последовательность ребер M
, в которой каждые два соседних ребра 
и 
имеют общую вершину. В маршруте одно и то же ребро может встречаться несколько раз. Начало маршрута – вершина 
, инцидентная ребру и не инцидентная 
; конец маршрута 
инцидентен 
и не инцидентен 
. Если 
— кратные, требуется дополнительное указание, какую из двух инцидентных вершин считать началом (концом) маршрута.
Маршрут, в котором совпадают его начало и конец 
, (т.е. замкнутый), называется циклическим. Маршрут, в котором все ребра разные, называется цепью. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, именуется простой цепью.
Циклический маршрут называется циклом, если он является цепью, и простым циклом, когда это – простая цепь.
Вершины 
называются связанными, если существует маршрут М с началом 
и 
концом. Связанные маршрутом вершины связаны также и простой цепью. Отношение связанности вершин обладает свойствами эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества 
. Граф G называется связанным, если все его вершины связаны между собой. Поэтому все подграфы G(
) связаны и называются связанными компонентами графа. Каждый н-граф распадается единственным образом в прямую сумму своих связанных компонент 
Пусть G – ориентированный граф.
Последовательность ребер, в которой конец каждого предыдущего ребра совпадает с началом следующего 
, называется путем(в нем все ребра проходят по их ориентации). В пути одно и то же ребро может встречаться несколько раз. Началом пути является начало ребра , концом пути – конец ребра .
Путь называется ориентированной цепью (или просто цепью), если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа G инцидентна не более чем двум его ребрам.
Контур – путь, в котором . Контур называется циклом, если он является цепью, и простым циклом, когда это – простая цепь. Если граф содержит циклы, то он содержит и простые циклы. Граф, не содержащий циклов, называется ациклическим.
Вершина 
называется достижимой из вершины 
, если существует путь 
с началом и концом .
Орграф G именуется связным, если он связен без учета ориентации дуг, и сильно связен, если из любой вершины в любую существует путь.
Число ребер маршрута (пути) называется его длиной.
Расстояние d(,) между вершинами и н-графа G называется минимальная длина простой цепи с началом и концом . Центромназывается вершина н-графа, от которой максимальное из расстояний до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершины называется радиусомграфа r(G).
Эйлеров цикл – цикл графа, содержащий все ребра графа. Эйлеров граф– граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом пера, вычеркивающего этот граф, не отрываясь от бумаги).
Теорема Эйлера: конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершины четны.
Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало и конец . Чтобы в конечном н-графе G существовала эйлерова цепь, необходимы и достаточны его связанность и четность степеней всех вершин, кроме начальной и конечной (и должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходимы и достаточны его связанность, а так же равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. 
.
Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтонова цепь – простая цепь, проходящая через все вершины графа, с началом и концом в разных вершинах 
.
Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах
Виды вершин и рёбер графа
Пример 1. Найти звенья в графе, представленном на рис А (под примером).
Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.
Иначе говорят также, что в описанном случае порядок двух концов ребра графа не существенен. В случае, когда порядок, в котором указаны вершины в инциденции, существенен, соответствующее ребро называет дугой.
Пример 2. Найти дуги в графе, представленном на рис А.
Пример 3. Найти петли в графе, представленном на всё том же рис А.
Голой называют вершину, которая не инцидентна ни одному ребру графа.
Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.
Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.
Две вершины a и b называются смежными, если существует по крайней мере одно соединяющее их ребро. В частности, вершина смежна сама с собой в том и только в том случае, когда при ней имеется хотя бы одна петля.
Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.
Кратными называются рёбра, соединяющие одну и ту же пару вершин.
Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.
Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.
Маршруты, цепи и циклы в графах
Маршрут, в котором все рёбра различны, называется цепью.
Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.
Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.
Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).
Ответ. В данном графе:
Граф называется связным, если существует цепь между любыми двумя его вершинами.
Учебная тема: Путь в графе
Содержание
Маршрут, цепь, цикл [ править ]
Маршрут [ править ]
Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены).
!В случае простого графа (графа без петель и кратных ребер) маршрут однозначно определяется последовательностью вершин или последовательностью ребер.
Длиной маршрута называют число ребер в нем с учетом повторений.
Цепь [ править ]
Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой
Путь – это ориентированная простая цепь
Эйлеров путь (эйлерова цепь) — это путь, проходящий по всем ребрам графа и притом только по одному разу.
Цикл [ править ]
Простой цикл – это замкнутая простая цепь.
Эйлеров цикл — это эйлеров путь, являющийся циклом.
Контур – это простой ориентированный цикл.
Расстояние между вершинами, диаметр, мост [ править ]
Расстояние между вершинами – это длина кратчайшей цепи, соединяющей эти вершины (сама такая цепь называется геодезической) рисунок
Например: расстояние между вершинами V1 и V5 это длина геодезической цепи V1-V2-V4-V5
Диаметр – это самая длинная геодезическая цепь.
Мост – это такое ребро графа, удаление которого приводит к тому, что его вершины перестают быть связными.
Например: на рисунке это ребра (2,4), (7,10), (11,12)
Точка сочленения, блок [ править ]
Точка сочленения – это вершина графа v, удаление которой из графа увеличивает число компонентов связности.
Блок – связный граф, не имеющий точек сочленения.
После удаления точки сочленения (вершины V) граф распадается на три блока
Ссылки на буклет и презентацию по данной теме [ править ]
Ресурсы [ править ]
Учебник «Дискретная математика. Курс лекций» Палий И.А.
Материал из википедии: статья «Эйлоров цикл»
Теория графов. Основные понятия и виды графов
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
