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

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ. КЛАССЫ ГРАФОВ

Инцидентность и понятия, связанные с инцидентностью

Маршруты, цепи и циклы

Некоторые классы графов

С определением графа мы познакомились на уроке "Понятие графа и отображение отношений в виде графа". Теперь нам предстоит узнать основные определения теории графов. И сразу же важное уточнение. Чаще всего, когда говорят о графах, по умолчанию считают, что множество V вершин графа является конечным (множеством, для которого существует натуральное число, являющееся числом его элементов, проще говоря, множество, элементы которого можно пересчитать). Если же речь идёт одновременно о графах, множества вершин которых как конечны, так и бесконечны, то для ясности говорят "конечные графы" и "бесконечные графы". На практике намного чаще работают с конечными графами. Конечные графы будем разбирать здесь и мы. Поэтому уточним: имеется в виду теория конечных графов, но так как ясность внесена, будем говорить просто "теория графов". Здесь во многих примерах будет разбираться один и тот же граф и, двигаясь вперёд по основным определениям теории графов, мы будем постепенно узнавать об этом графе очень многое. И наоборот: глядя на этот граф, мы будем лучше представлять себе на примерах основные определения теории графов.

Итак, что требуется для того, чтобы начать работать с графом? Графа ещё нет, есть только прикладная задача, описанная в виде отношений на некотором множестве. Значит, если графа ещё нет, то его нужно задать. Задать граф можно двумя способами: графически и аналитически. Графически - значит нарисовать граф. Этим мы и занимались на уроке "Понятие графа и отображение отношений в виде графа".

Инцидентность и понятия, связанные с инцидентностью

Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении, будет недостаточно. Потребуется ещё и множество P троек вида (aub), указывающих какую пару ab элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов - инцидентности. Инцидентность - это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.

Понятие инцидентности - одно из главных при создании структур данных для представления графов в памяти ЭВМ.

Пример 1. Задать аналитически граф, представленный на рис 1.

Решение. Распространённые ошибки - не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V, а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U.

Итак, задаём граф следующими множествами:

множество вершин: V = {abcdef}

множество рёбер: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

множество инциденций: P = {(b, 1, a), (b, 2, a), (a, 3, b), (b, 4, b), (b, 5, b), (c, 6, c), (c, 7, c), (b, 8, d), (d, 8, b), (b, 9, d), (b, 10, e), (b, 11, e), (e, 11, b)}


Уже на первом уроке по теории графов мы обозначили различие между неориентированными и ориентированными графами. Сделано это было на простых примерах для более интуитивного понимания. Так что, наверное, будет не сложно усвоить уже более строгие определения. Ребро u, соединяющее вершину a с вершиной b (a ≠ b), назовём звеном, если множеству P принадлежать две инциденции: aub и bua.

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

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

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

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

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

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

О дуге говорят, что она идёт из вершины b в вершину a. Графы, все рёбра которых являются дугами, называются ориентированными графами или орграфами.


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

Пример 4. Найти петли в графе, представленном на всё том же рис 1.

Ответ. В данном графе петли представлены линиями, начинающимися и заканчивающимися на одной и той же вершине. Линии 4 и 5 - петли.

Если граф содержит петли, то это обстоятельство специально оговаривают, добавляя к основной харатеристике графа слова "с петлями", например, "орграф с петлями". Если граф не содержит петель, то добавляют слова "без петель".

Смешанным называют граф, в котором имеются рёбра хотя бы двух из разобранных трёх разновидностей (звенья, дуги, петли).

Голой называют вершину, которая не инцидентна ни одному ребру графа.

Пример 5. Найти голую вершину в графе, представленном на всё том же рис 1.

Ответ. В данном графе голой является вершина f.

Граф, состоящий только из голых вершин, называется пустым.

Изолированной называется вершина графа, которая инцидентна одной или нескольким петлям.

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

Пример 6. В графе, представленном на рис 1, найти изолированные вершины, смежные и не смежные вершины, вершины, смежные сами с собой.

Ответ. В данном графе вершина c изолированная. Вершины a и b смежные, а вершины a и d - не смежные, вершина b смежна сама с собой.

Кратными называются рёбра, соединяющие одну и ту же пару вершин.

Пример 7. Найти кратные рёбра в графе, представленном на всё том же рис 1.

Ответ. В данном графе рёбра 1, 2 и 3 - кратные; кратными являются также 4 и 5, рёбра 8, 9, рёбра 6, 7, а также 10 и 11.

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

Маршруты, цепи и циклы

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

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

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

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

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

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

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

Некоторые классы графов

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

Граф без дуг (то есть неориентированный), без петель и кратных рёбер называется обыкновенным. Обыкновенный граф изображён на рис. 3 ниже.

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

Граф заданного типа называют полным, если он содержит все возможные для этого типа рёбра (при неизменном множестве вершин). Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном (рис. 4 ниже).

Полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, соединяющих вершины одного множества с вершинами другого множества (рис. 5 ниже).

Эйлеровым графом называется граф, в котором можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.

Пример 9. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом? Объяснить ответ. Привести примеры.

Ответ. Если n - нечётное число, то каждая вершина инцидентна n-1 рёбрам. В таком случае данный граф является эйлеровым графом. Примеры таких графов на рис. 6.

Регулярным графом называется граф, все вершины которого имеют одинаковую степень. Таким образом, на рис. 6 (выше) изображены примеры регулярных графов, называемых по степени его вершин 4-регулярными и 2-регулярными графами.

Гамильтоновым графом называется граф, содержащий гамильтонов цикл. Гамильтоновым циклом называется простой цикл, проходящий через все вершины рассматриваемого графа. Таким образом, говоря проще, гамильтонов граф - это такой граф, в котором можно обойти все вершины и каждая вершина при обходе повторяется лишь один раз. Пример гамильтонова графа - на рис. 7.

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

Деревом называется связный граф без циклов (рис. 8).

Нет времени вникать в решение? Можно заказать работу!

Материал "Понятие графа и отображение отношений в виде графа"

Материал "Структуры данных для представления графов в памяти ЭВМ"

К началу страницы