Раздел 4. Основы теории графов

Тема 4.1.Основные понятия теории графов

 

Тема лекции: ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

План:

1. Введение

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

3. Некоторые типы графов

 

1. Введение

 

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

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

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

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

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

 

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

 

Определение: Пусть задано некоторое конечное множество 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) – ребром.

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

 

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

Рис. 1                                               Рис. 2

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

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

Определение: Путь (цепь), у которого(-ой) начальная и конечная вершина совпадают, называется контуром (циклом).

Для графа на рис. 2 циклом является, например, следующая цепь [ x ₂, x ₃, x ₅, x ₁, x ₂ ].

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

Например, для графа на рис.2 цикл [ x ₂, x ₃, x ₅, x ₁, x ₂ ] является простым, а цикл [ x ₂, x ₃, x ₄, x ₅, x ₃, x ₁, x ₂ ] не является простым.

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

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

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

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

Рис.3           а                                                 б

 

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

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

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

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

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

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

Определение: Подграфом графа G=(X, V) называется граф G'=(X', V '), для которого X' Í X, V ' Í V, причемребро (x_i, x_j) содержится в V ' только в том случае, если x_i и x_j содержатся в X'. Одним из подграфов графа на рис.1 является следующий (рис..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'.

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

Рис. 4                                     Рис.5

 

Некоторые типы графов

Определение: Граф G называется полным, если любые две его вершины смежны.Полный граф порядка n обозначается символом К _n, число ребер в нем равно . На рис.6 изображены графы К _n, n £5.

Рис.6

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

Определение: Граф, не содержащий вершин и, следовательно, ребер, называется ноль-графом. Граф, состоящий из одной вершины, называется тривиальным.

 

Красивыми примерами являются графы пяти платоновых тел (т. е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра

 

К онтрольные вопросы:

1. Понятие графа.

2. Применение графов.

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

4. Типы графов.

Тема лекции: Представление информации в форме графа

 

План:

1. Вводные понятия.

2. История возникновения и развития теории графов.

3. Представление графа в памяти компьютера.

 

1. Вводные понятия

 

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

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

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

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

Две вершины, соединенные ребром (дугой) называются смежными.

Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.

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