Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах
Виды вершин и рёбер графа
Ребро 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.
Количество рёбер, инцидентных вершине графа, называется степенью этой вершины графа.
Маршруты, цепи и циклы в графах
Маршрутом в графе называется последовательность вершин и рёбер (v0, e1, ..., en, vn ), такая, что любые две соседние вершины vi и vi+1 соединены ребром ei+1. Если в маршруте v0 = vn, то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута
Маршрут, в котором все рёбра различны, называется цепью.
Цепь, в которой все вершины, кроме, возможно, первой и последней, различны, называется простой цепью.
Замкнутая цепь с положительной длиной называется циклом. Замкнутая простая цепь с положительной длиной называется простым циклом.
Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину), любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).
Ответ. В данном графе:
- например, a1b2a1b7d8c9c8d - маршрут из вершины a в вершину d длины 7;
- например, b5c6b7d - цепь;
- например, цепь a1b5c8d - простая, а цепь e3e4e - не простая;
- например, b5c9c8d7b - цикл длины 4 при вершине b;
- например, b5c8d7b - простой цикл длины 1 при вершине b.
Граф называется связным, если существует цепь между любыми двумя его вершинами.
| Назад<<< | Листать | Вперёд>>> |
