Тема 1. Теория графов

1. Понятие графа. Основные элементы и свойства графов.

Граф – множество точек плоскости или пространства и множество отрезков, соединяющих все или некоторые из этих точек.

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

Дуги графа имеют направления, обозначаемые стрелкой:

Рёбра не имеют направления:

Обозначим граф G = (X, U), где X – множество вершин, U – множество дуг (рёбер).

Граф, состоящий из дуг, называется ориентированным (орграфом), а образованный ребрами – неориентированным.

Смешанные графы содержат и дуги, и рёбра.

Две вершины x_i и x_j называются смежными, если они образуют ребро, т.е. (x_i, x_j)Î U.

Ребро (x_i, x_j)Î U называется инцидентным вершинам x_i и x_j.

Два ребра называются смежными, если они инцидентны одной и той же вершине.

Т.к. вершины можно располагать произвольно, а также выбирать любую форму линий, то один и тот же граф можно изобразить по-разному – это свойство изоморфизма графов.

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

Если граф состоит из конечного числа вершин и дуг (ребер), то этот граф называют конечным.

Степенью вершины x_i называется число дуг (ребер), которым она принадлежит (инцидентна) Р(x_i). Вершина, у которой Р(x_i)= 1, называется висячей.

Для орграфов выделяют полустепень захода Р⁺(x_i) вершины x_i – количество дуг, заходящих в x_i, и полустепень исхода Р ^–(x_i). – количество дуг, исходящих из x_i. Р⁺(x_i)+ Р ^–(x_i) = Р(x_i).

Петлёй называется ребро, которое выходит из вершины и входит в неё же.

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

(может изображать автомобильную или железную дорогу).

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

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

Путь называется простым, если в нём ни одна дуга не встречается дважды, и составным, если какая-либо из дуг встречается более одного раза; элементарным - если никакая вершина не встречается дважды.

Контур может быть простым и составным (сложным), как и путь.

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

Терминология различается для орграфов (дуга, путь, контур) и для неориентированных графов (ребро, цепь, цикл).

Неориентированный граф называется связным, если любые 2 его вершины можно соединить путем, и несвязным – в противном случае.

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

Например,

(может быть расстояние между пунктами)

(может обозначать поставку товаров от xi к xj на 20 млн. руб.).

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

Задача I . На каких графах можно найти простой цикл (контур), содержащий все рёбра (дуги)?

Её сформулировал Леонард Эйлер (1707 - 1783) в первой работе о графах, рассматривая задачу о кёнигсбергских мостах: выйдя из дома, необходимо вернуться обратно, пройдя только 1 раз по каждому мосту

(B и C - ,берега реки, A и D - острова; мосты между островами и берегами).

Граф, соответствующий данному рисунку, имеет вид:

Эйлер показал, что такой путь существует тогда и только тогда, когда граф G содержит не более двух вершин нечётной степени. Так как в задаче о мостах имеется 4 вершины с нечётной степенью, то решение задачи имеет отрицательный ответ. Если все вершины имеют чётную степень, то такой цикл существует, называется эйлеровым путём, а граф, обладающий им, называется эйлеровым графом. Контур (цикл), в котором ни одно ребро не встречается дважды, называется эйлеровым.

Задача II. Содержит ли граф элементарный цикл (контур), включающий все вершины?

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

Такой цикл называют гамильтоновым по имени ирландского математика У. Гамильтона (1805 - 1861). Это понятие применяется в задаче о коммивояжёре: торговцу надо посетить все города, расстояние между которыми известны, и вернуться в исходное положение. Другими словами, среди всех гамильтоновых циклов найти такой, общая длина рёбер которого минимальна. Признака наличия гамильтонова цикла пока нет.