Виды вершин и рёбер графа. Маршруты, цепи, циклы в графах

  • Виды вершин и рёбер графа
  • Маршруты, цепи и циклы в графах

Виды вершин и рёбер графа

Ребро u, соединяющее вершину a с
вершиной b (a ≠ b), назовём звеном, если множеству P
принадлежать две инциденции: aub и bua.

Пример 1. Найти звенья в графе, представленном на рис А (под примером).

Ответ. Звенья данного графа изображены линиями 8 и 11 без указания направления.

Иначе
говорят также, что в описанном случае порядок двух концов ребра графа не существенен.
В случае, когда порядок, в котором указаны вершины в инциденции, существенен,
соответствующее ребро называет дугой.

Пример 2. Найти дуги в графе, представленном на рис А.

Ответ. Дуги данного графа представлены направленными линиями (стрелками),
соединяющими первую из инцидентных вершин со второй. Вершины 1, 2, 9, 10 — дуги; первая из них соединяет
вершину b с вершиной a, но не наоборот. То же самое относится и к другим дугам.

О дуге
говорят, что она идёт из вершины b в вершину a.

Рёбра u, для которых имеются инциденции вида
(aua), то есть вершина соединена
сама с собой, называются петлями.

Пример 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.

Количество рёбер, инцидентных вершине графа, называется степенью
этой вершины графа
.

Маршруты, цепи и циклы в графах

Маршрутом в графе называется последовательность вершин и
рёбер (v0e1, …, envn ), такая,
что любые две соседние вершины vi и
vi+1 соединены ребром
ei+1. Если в маршруте
v0 = vn,
то есть начальная вершина совпадает с конечной, то маршрут называется замкнутым или циклическим, в противном случае
маршрут называется открытым. Число рёбер в маршруте называется длиной маршрута

Маршрут, в котором все рёбра различны, называется цепью.

Цепь, в которой все вершины, кроме, возможно, первой и последней, различны,
называется простой цепью.

Замкнутая цепь с положительной длиной называется циклом. Замкнутая
простая цепь с положительной длиной называется простым циклом.

Пример 7. В графе, представленном на рисунке ниже, найти примеры маршрута (указать длину),
любой цепи, простой цепи, цепи, не являющейся простой, любого цикла (указать длину), простого цикла (указать длину).

теория графов: чертёж для нахождения маршрутов, цепи, цикла

Ответ. В данном графе:

  • например, a1b2a1b7d8c9c8d — маршрут из вершины a в вершину d длины 7;
  • например, b5c6b7d — цепь;
  • например, цепь a1b5c8d — простая, а цепь e3e4e — не простая;
  • например, b5c9c8d7b — цикл длины 4 при вершине b;
  • например, b5c8d7b — простой цикл длины 1 при вершине b.

Граф называется связным, если существует цепь между любыми двумя его
вершинами.

Ссылка на основную публикацию