Введение в теорию графов

Введение в теорию графов

2-е издание, исправленное

Князьков В.С.
Волченская Т.В.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Введение в теорию графов/ В.С. Князьков, Т.В. Волченская - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2008-2016
(c) Князьков В.С., Волченская Т.В., 2008-2016

3

Графы и способы их представления

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

Введение

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

Значительно возросла популярность теории графов – ветви дискретной математики.
Графы встречаются во многих областях под разными названиями: “структуры” в
гражданском строительстве, “сети” – в электронике, “социограммы” – в социологии и
экономике, “молекулярные структуры” – в химии, “дорожные карты”, электрические
или газовые распределительные сети и т. д.

Родившись при решении головоломок и игр, таких, например, как задача о
кенигсбергских мостах и игра Гамильтона, теория графов стала мощным средством
исследования и решения многих задач, возникающих при изучении больших и
сложных систем. Для специалистов по вычислительной технике, информационным
системам и системам цифровой связи теория графов – это удобный язык выражения
понятий из этой области; многие результаты теории графов имеют непосредственную
связь с задачами, с которыми им приходится сталкиваться. Графическая интерпретация
различных моделей графов дана на рис. 1.1 Так в виде ориентированных графов можно
представить любую логическую или функционально - логическую схему (рис. 1.1,а).
На таких графовых моделях можно, например, оценить быстродействие схемы. Блоксхема алгоритма может быть представлена вероятностным графом (рис. 1.1,б), который
позволяет оценить временные характеристики алгоритма, затраты процессорного
времени, трудоемкость и другие. Графом типа “дерево” можно отобразить практически
любую структуру организации или предприятия (рис. 1.1,в).

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

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

4

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

a

б

5

Рис. 1.1.  Графическая интерпретация применения графовых структур: а – орграф; б –
вероятностный граф; в – граф-дерево

Графы и способы их представления

Основные определения

Граф задается множеством точек или вершин х1, х2, …, хn и множеством линий или
ребер a1, a2, … , am, соединяющих между собой все или часть точек. Формальное
определение графа может быть дано следующим образом.

Графом называется двойка вида

G = (X, A),

где X = {xi}, i = 1, 2, …, n – множество вершин графа, A = {ai}, i = 1, 2,… , m –
множество ребер графа.

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

6