Лекция 17

ТЕМА: НЕОРИЕНТИРОВАННЫЙ ГРАФ.

ПЛАН:

1. Основные понятия

2. Смежность, инцидентность. Степени вершин

3. Способы задания графов

4. Маршруты в неориентированном графе

5. Операции над графами

6. Связность. Компоненты связности

Главная

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

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

1. Основные понятия .

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

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

При рассмотрении задач теории графов ограничиваются исследованием совокупности двух конечных множеств V и Х. Элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

Сформулируем определение неориентированного графа:

Непустое множество V = {v₁, v₂,…,v_n} и набор Х пар объектов {v_i, v_i+1}, где v_iV, v_i+1V, называется графом.

Т.к. V и Х конечные множества, то граф называется конечным.

Если пара упорядоченная (v_i, v_i+1), граф называется ориентированным и обозначается D(V,X).

Если пара неупорядоченная {v_i, v_i+1}, то граф называется неориентированным и обозначается G(V,X).

Рассмотрим сначала неориентированные графы.

Как было сказано выше граф изображается диаграммой на плоскости. Приведем пример:

Рис. 13.1

В данном графе есть пара с одинаковыми вершинами {v₃, v₃}. Ребро соответствующее такой паре называется петлей.

Граф также содержит одинаковые пары {v₆, v₅}. Такие пары называются кратными ребрами. Количество одинаковых пар, соответствующих вершинам v_i и v_i+1 называется кратностью ребра. В приведенном примере кратность ребра {v₆, v₅} равна двум.

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

Псевдограф без петель называется мультиграфом (рисунок 13.2).

Мультиграф без кратных ребер называется простым графом (13.3).

Рис. 13.2. Мультиграф. Рис. 13.3. Граф.

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

Рис. 13.4. Полный граф.

2. Смежность, инцидентность, степени вершин.

Если х = {v, w} – ребро графа, то v, w называются концами ребра х, в этом случае говорят, что ребро х соединяет вершины v и w.

Если вершина v является концом ребра х, то говорят, что v и х инцидентны .

Вершины v, w графа G(V,X) называются смежными, если {v, w}Х.

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

Рассмотрим граф на рисунке 13.1.

Вершине v₃ инцидентны ребра {v₃, v₃}, {v₃, v₁}, {v₃, v₂}, {v₃, v₄}.

Ребру {v₂, v₆} инцидентны вершины v₂, v₆.

Вершины v₅, v₆ – смежные, т.к. {v₅, v₆}- ребро. Вершины v₅, v₃ – не смежные, т.к. нет ребра их соединяющего.

Ребра {v₃, v₁}, {v₃, v₂}- смежные, т.к. имеют общую вершину v₃.

Степень вершины v – это количество ребер графа, инцидентных этой вершине. Обозначение  (v).

Для графа 13.1:

 (v₁) = 1  (v₅) = 2

 (v₂) = 2  (v₆) = 3

 (v₃) = 5  (v₇) = 0

 (v₄) = 1

Заметим, что вклад каждой петли равен двум.

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

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

Значит, вершины v₁ и v₄ – висячие, а вершина v₇ – изолированная.

Теорема о сумме степеней вершин графа: Для любого псевдографа G(V, X) выполняется равенство:

m – количество ребер графа. Действительно, каждое ребро графа инцидентно двум вершинам.

Проверим справедливость теоремы для графа 13.1:

m =7, 7 2 =14 и 1+2+5+1+2+3+0 =14.