ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

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

Термин «граф» впервые появился в книге выдающе­гося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Одна из задач, положивших начало теории графов, – задача о кенигсбергских мостах будет рассмотрена в разделе 4.12.

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

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

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

Основные понятия и определения теории графов

Пусть задано некоторое конечное множество X, элементы которого будем называть вершинами, и множество V, состоящее из пар элементов (x_i, x_j) множества X. Упорядоченная пара множеств G=(X,V) называется графом. Вершины изображаются точками, а пары элементов – линиями, соединяющими точки, соответствующие образующим пары вершинам.

Если в определении графа существенно в каком порядке выбираются вершины (то есть пара (x_i, x_j) отлична от пары (x_j,x_i)), то такой граф называют ориентированным илиорграфом, а пару (x_i, x_j)–дугой, при этом считается, что х_i –начальная вершина, a x_j – конечная. В геометрической интерпретации дуге соответствует направленный отрезок. Часто орграф задают парой G=(X,Г), где Х – множество вершин, а Г – неоднозначное отображение, ставящее в соответствие каждой вершине подмножество в X. Г(х_i)– множество вершин х_jÎХ, для которых в графе G существует дуга (х_i, х_j). (х_i)– множество вершин х_jÎX, для которых в графе G существует дуга (x_j, х_i).

Если в определении графа не существенен порядок вершин при образовании пары (х_i, x_j), то граф называют неориентированным или неорграфом, а пару (x_i , x_j) – ребром.

Число вершин графа называется его порядком.

Пример. На рис. 4.1 изображен ориентированный граф G=({x₁, x₂, x₃, x₄}, {(x₁, x₂), (x₁, x₄), (x₂, x₄), (x₃, x₁), (x₃, x₂), (x₄, x₃)}), а на рис. 4.2 – неориентированный граф.

Рис. 4.1 Рис. 4.2

Путем в графе G называется такая последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Для неорграфа такая последовательность ребер называется цепью. Если путь (цепь) проходит через вершины х₁, ..., х_k, то будем обозначать его (ее) символом [x₁, …, x_k].

Для графа на рис. 4.1 последовательность дуг (x₁, x₂), (x₂, x₄), (x₄, x₃) является путем и может быть обозначена следующим образом [x₁, x₂, x₄, x₃]. Для графа на рис. 4.2 цепью является, например, следующая последовательность ребер (x₂, x₃), (x₃, x₅), (x₅, x₄), которую обозначим через [x₂, x₃, x₅, x₄].

Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом). Для графа на рис. 4.2 циклом является, например, следующая цепь [x₂, x₃, x₅, x₁, x₂].

Простым циклом графа называется цикл, в котором все вершины различны за исключением начальной и конечной вершины, которые совпадают. Например, для графа на рис. 4.2 цикл [x₂, x₃, x₅, x₁, x₂] является простым, а цикл [x₂, x₃, x₄, x₅, x₃, x₁, x₂] не является простым.

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

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

Пример. На рис. 4.3.б изображен граф, который является основание графа, изображенного на рис. 4.3.а.

Две вершины х_i и х_j называются смежными, если существует соединяющее их ребро (дуга) (х_i, x_j), при этом вершины называются инцидентными этому ребру (дуге), а ребро (дуга) – инцидентным(-ой) этим вершинам. Аналогично, два различных ребра (дуги) называются смежными, если они имеют по крайней мере одну общую вершину.

а б

Рис. 4.3

Вершины х₁ и х₄ смежны (рис. 4.3), дуга (х₁, х₄) инцидентна вершинам х₁ и х₄, а вершины х₁ и х₄ инцидентны дуге (х₁, х₄). Ребра (х₁, х₃) и (х₃, х₄) смежны (рис. 4.2).

Замечание. Смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Множество всех вершин графа G, смежных с некоторой вершиной x, называется окружением вершины x и обозначается через N_G(x) или просто N(x).

В неориентированном графе число ребер, инцидентных данной вершине х_i, называется степенью (валентностью) вершины х_i и обозначается d(х_i). Вершина графа, имеющая степень 0, называется изолированной, а вершина, имеющая степень 1 – висячей. Для неорграфа на рис. 4.2 d(х₁)=3, d(х₃)=4.

Число дуг, исходящих из вершины х_i ориентированного графа, называется полустепенью исхода вершины х_i и обозначается . Число дуг, заходящих в вершину х_i ориентированного графа, называется полустепенью захода вершины х_i и обозначается . Так, для орграфа, представленного на рис. 4.3.а) , .

Утверждение (лемма о рукопожатиях). Сумма степеней вершин графа G равна 2m, где m – число ребер графа G.

Доказательство. Поскольку каждое ребро инцидентно двум вершинам, то оно добавляет двойку к сумме степеней графа G. Следовательно, все ребра дают вместе сумму степеней 2m.

Подграфом графа G=(X,V) называется граф G'=(X',V'), для которого X'ÍX, V'ÍV, причемребро (x_i, x_j) содержится в V' только в том случае, если x_i и x_j содержатся в X'. Одним из подграфов графа на рис. 4.1 является следующий (рис. 4.4)

Если все вершины графа G=(X,V) присутствуют в подграфе G'=(X',V'), тогда G' называется остовным подграфом, т. е. X'=Х, V'ÍV.

Пусть X' – подмножество вершин Х графа G=(X,V). Тогда граф G'=(X',V') называется порожденным подграфом графа G на множестве вершин X' (вершинно-порожденный подграф), если V' является таким подмножеством V, что ребро (x_i, x_j) входит в V' тогда и только тогда, когда x_i и x_j входят в X'.

На рис. 4.5 представлен порожденный подграф на множестве вершин {х₁, х₃, x₅} неориентированного графа, изображенного на рис 4.2.

Рис. 4.4 Рис. 4.5