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

Основные виды графов

Двудольный граф

Эйлеров граф

Регулярный граф

Гамильтонов граф

Взвешеный граф

Графы-деревья

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

Двудольный граф

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

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

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

Эйлеров граф

Мы уже касались задачи о кёнигсбергских мостах. Отрицательное решение Эйлером этой задачи привело к первой опубликованной работе по теории графов. Задачу об обходе мостов можно обобщить и получить следующую задачу теории графов: можно ли найти в данной графе цикл, содержащий все вершины и все рёбра? Граф, в котором это возможно, называется эйлеровым графом.

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

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

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

Регулярный граф

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

Число вершин регулярного графа k-й степени не может быть меньше k+1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример 3. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

Решение. Рассуждаем так: для того, чтобы длина цикла удовлетворяла заданному условию, требуется, чтобы число вершин графа было кратно четырём. Если число вершин равно четырём, то получится граф, изображённый на рисунке ниже. Он является регулярным, но в нём самый короткий цикл имеет длину 3.

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

Гамильтонов граф

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

Пример 4. Задан двудольный граф, в котором n - число вершин из множества A, а m - число вершин из множества B. В каком случае граф будет эйлеровым графом, а в каком случае - гамильтоновым графом?

Ответ. Если n и n - чётные, то граф будет эйлеровым. Если n = n, то граф будет гамильтоновым.

Взвешенный граф

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

Графы-деревья

Деревом называется связный граф без циклов (рисунок ниже). Любые две вершины дерева соединены лишь одним маршрутом.

Число q рёбер графа находится из соотношения

q = n - 1,

где n - число вершин дерева.

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

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

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