"Чистая"
и прикладная математика

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

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

Ребро 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.

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

Весь блок "Теория графов"