Тема 4.2. Маршруты и деревья
Цель: изучить различные виды конструкций графов.
- Рассмотреть понятия маршрут, путь, цепь и цикл применительно к графам.
- Рассмотреть структуру графа дерева и леса.
- например, a1b2a1b7d8c9c8d — маршрут из вершины a в вершину d длины 7;
- например, b5c6b7d — цепь;
- например, цепь a1b5c8d — простая, а цепь e3e4e — не простая;
- например, b5c9c8d7b — цикл длины 4 при вершине b;
- например, b5c8d7b — простой цикл длины 1 при вершине b.
4.2.1. Маршруты, пути, цепи, циклы
Пусть G – неориентированный граф.
Маршрутом в G называется такая последовательность ребер M , в которой каждые два соседних ребра и имеют общую вершину. В маршруте одно и то же ребро может встречаться несколько раз. Начало маршрута – вершина , инцидентная ребру и не инцидентная ; конец маршрута инцидентен и не инцидентен . Если — кратные, требуется дополнительное указание, какую из двух инцидентных вершин считать началом (концом) маршрута.
Маршрут, в котором совпадают его начало и конец , (т.е. замкнутый), называется циклическим. Маршрут, в котором все ребра разные, называется цепью. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, именуется простой цепью.
Циклический маршрут называется циклом, если он является цепью, и простым циклом, когда это – простая цепь.
Вершины называются связанными, если существует маршрут М с началом и концом. Связанные маршрутом вершины связаны также и простой цепью. Отношение связанности вершин обладает свойствами эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества . Граф G называется связанным, если все его вершины связаны между собой. Поэтому все подграфы G( ) связаны и называются связанными компонентами графа. Каждый н-граф распадается единственным образом в прямую сумму своих связанных компонент
Пусть G – ориентированный граф.
Последовательность ребер, в которой конец каждого предыдущего ребра совпадает с началом следующего , называется путем (в нем все ребра проходят по их ориентации). В пути одно и то же ребро может встречаться несколько раз. Началом пути является начало ребра , концом пути – конец ребра .
Путь называется ориентированной цепью (или просто цепью), если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа G инцидентна не более чем двум его ребрам.
Контур – путь, в котором . Контур называется циклом, если он является цепью, и простым циклом, когда это – простая цепь. Если граф содержит циклы, то он содержит и простые циклы. Граф, не содержащий циклов, называется ациклическим.
Вершина называется достижимой из вершины , если существует путь с началом и концом .
Орграф G именуется связным, если он связен без учета ориентации дуг, и сильно связен, если из любой вершины в любую существует путь.
Число ребер маршрута (пути) называется его длиной.
Расстояние d( , ) между вершинами и н-графа G называется минимальная длина простой цепи с началом и концом . Центром называется вершина н-графа, от которой максимальное из расстояний до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершины называется радиусом графа r(G).
Эйлеров цикл – цикл графа, содержащий все ребра графа. Эйлеров граф – граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом пера, вычеркивающего этот граф, не отрываясь от бумаги).
Теорема Эйлера: конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершины четны.
Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало и конец . Чтобы в конечном н-графе G существовала эйлерова цепь, необходимы и достаточны его связанность и четность степеней всех вершин, кроме начальной и конечной ( и должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходимы и достаточны его связанность, а так же равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. .
Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтонова цепь – простая цепь, проходящая через все вершины графа, с началом и концом в разных вершинах .
Для вершин и графа G на рис.4.4 привести примеры маршрута, цепи, простой цепи; определять в графе циклический маршрут, цикл, простой цикл, приняв вершину за их начало и конец.
Источник
Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах
Ребро u , соединяющее вершину a с вершиной b ( a ≠ b ), назовём звеном, если множеству P принадлежать две инциденции: a, u, b и b, u, a .
Пример 1. Найти звенья в графе, представленном на рис А (под примером).
Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.
Иначе говорят также, что в описанном случае порядок двух концов ребра графа не существенен. В случае, когда порядок, в котором указаны вершины в инциденции, существенен, соответствующее ребро называет дугой.
Пример 2. Найти дуги в графе, представленном на рис А.
Ответ. Дуги данного графа представлены направленными линиями (стрелками), соединяющими первую из инцидентных вершин со второй. Вершины 1, 2, 9, 10 — дуги; первая из них соединяет вершину b с вершиной a , но не наоборот. То же самое относится и к другим дугам.
О дуге говорят, что она идёт из вершины b в вершину a .
Рёбра u , для которых имеются инциденции вида (a, u, a) , то есть вершина соединена сама с собой, называются петлями.
Пример 3. Найти петли в графе, представленном на всё том же рис А.
Ответ. В данном графе петли представлены линиями, начинающимися и заканчивающимися на одной и той же вершине. Линии 4 и 5 — петли.
Голой называют вершину, которая не инцидентна ни одному ребру графа.
Пример 4. Найти голую вершину в графе, представленном на всё том же рис А.
Ответ. В данном графе голой является вершина f .
Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.
Две вершины a и b называются смежными, если существует по крайней мере одно соединяющее их ребро. В частности, вершина смежна сама с собой в том и только в том случае, когда при ней имеется хотя бы одна петля.
Пример 5. В графе, представленном на рис А, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.
Ответ. В данном графе вершина c изолированная. Вершины a и b смежные, а вершины a и d — не смежные, вершина b смежна сама с собой.
Кратными называются рёбра, соединяющие одну и ту же пару вершин.
Пример 6. Найти кратные рёбра в графе, представленном на всё том же рис А.
Ответ. В данном графе рёбра 1, 2 и 3 — кратные; кратными являются также 4 и 5, рёбра 8, 9, рёбра 6, 7, а также 10 и 11.
Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.
Маршруты, цепи и циклы в графах
Маршрутом в графе называется последовательность вершин и рёбер (v 0 , e 1 , . e n , v n ) , такая, что любые две соседние вершины v i и v i+1 соединены ребром e i+1 . Если в маршруте v 0 = v n , то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута
Маршрут, в котором все рёбра различны, называется цепью.
Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.
Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.
Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).
Граф называется связным, если существует цепь между любыми двумя его вершинами.
Источник
Маршруты, пути, цепи, циклы
1.Чему посвящен раздел дискретной математики, изучающий теорию графов?
2.В чем отличие ориентированного и неориентированного графов?
4.В чем заключается смысл отношения инцидентности?
5.Локальная степень вершины графа это?
6.В каком случае графы называются изоморфными?
7.Назовите способы задания графов?
8.Перечислите отличия матрицы инцидентности и матрицы смежности?
9.Когда граф называется частью графа?
Рассматривается раздел дискретной математики изучающий теорию графов. Приведены основные понятия теории графов такие, как вершина, ребро, ориентированный граф и так далее. Дано понятие локальной степени. Показаны способы задания графов с их демонстрацией. Отдельно рассмотрены операции над частями графа, а так же графы и бинарные отношения.
Цель: изучить различные виды конструкций графов.
1 Рассмотреть понятия маршрут, путь, цепь и цикл применительно к графам.
2 Рассмотреть структуру графа дерева и леса.
Пусть G – неориентированный граф.
Маршрутом в G называется такая последовательность ребер M , в которой каждые два соседних ребра и имеют общую вершину. В маршруте одно и то же ребро может встречаться несколько раз. Начало маршрута – вершина , инцидентная ребру и не инцидентная ; конец маршрута инцидентен и не инцидентен . Если — кратные, требуется дополнительное указание, какую из двух инцидентных вершин считать началом (концом) маршрута.
Маршрут, в котором совпадают его начало и конец , (т.е. замкнутый), называется циклическим. Маршрут, в котором все ребра разные, называется цепью. Цепь, не пересекающая себя, т.е. не содержащая повторяющихся вершин, именуется простой цепью.
Циклический маршрут называется циклом, если он является цепью, и простым циклом, когда это – простая цепь.
Вершины называются связанными, если существует маршрут М с началом и концом. Связанные маршрутом вершины связаны также и простой цепью. Отношение связанности вершин обладает свойствами эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества . Граф G называется связанным, если все его вершины связаны между собой. Поэтому все подграфы G( ) связаны и называются связанными компонентами графа. Каждый н-граф распадается единственным образом в прямую сумму своих связанных компонент
Пусть G – ориентированный граф.
Последовательность ребер, в которой конец каждого предыдущего ребра совпадает с началом следующего , называется путем (в нем все ребра проходят по их ориентации). В пути одно и то же ребро может встречаться несколько раз. Началом пути является начало ребра , концом пути – конец ребра .
Путь называется ориентированной цепью (или просто цепью), если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа G инцидентна не более чем двум его ребрам.
Контур – путь, в котором . Контур называется циклом, если он является цепью, и простым циклом, когда это – простая цепь. Если граф содержит циклы, то он содержит и простые циклы. Граф, не содержащий циклов, называется ациклическим.
Вершина называется достижимой из вершины , если существует путь с началом и концом .
Орграф G именуется связным, если он связен без учета ориентации дуг, и сильно связен, если из любой вершины в любую существует путь.
Число ребер маршрута (пути) называется его длиной.
Расстояние d (,) между вершинами и н-графа G называется минимальная длина простой цепи с началом и концом . Центром называется вершина н-графа, от которой максимальное из расстояний до других вершин являлось бы минимальным. Максимальное расстояние от центра G до его вершины называется радиусом графа r(G).
Эйлеров цикл – цикл графа, содержащий все ребра графа. Эйлеров граф – граф, имеющий эйлеров цикл (эйлеров цикл можно считать следом пера, вычеркивающего этот граф, не отрываясь от бумаги).
Теорема Эйлера: конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершины четны.
Эйлерова цепь – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало и конец . Чтобы в конечном н-графе G существовала эйлерова цепь, необходимы и достаточны его связанность и четность степеней всех вершин, кроме начальной и конечной (и должны иметь нечетные степени). Чтобы в конечном орграфе существовал эйлеров цикл, необходимы и достаточны его связанность, а так же равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. .
Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа. Гамильтонова цепь – простая цепь, проходящая через все вершины графа, с началом и концом в разных вершинах .
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник