Рис. 1. Иллюстрация к задаче о Кенигсбергских мостах
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Между понятием графа и понятием отношения, имеется глубокая связь — в сущности это равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией. Понятие отношения также можно полностью выразить через понятие множества. Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа. Само название “граф” подразумевает наличие графической интерпретации. Картинки позволяют сразу “усмотреть” суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы. Эта глава практически полностью посвящена описанию языка теории графов.
Как это ни удивительно, но для понятия “граф” нет общепризнанного единого определения. Разные авторы, особенно применительно к разным приложениям, называют “графом” очень похожие, но все-таки различные объекты. Здесь используется терминология, которая была выбрана из соображений максимального упрощения определений и доказательств.
1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис.1). Эта задача была решена Эйлером в 1736 году.
2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис.2). Эта задача была решена Куратовским в 1930 году.
3. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3).
| Определение |
|---|
| Графом G(V,E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е — множество ребер). |
Число вершин графа G обозначим р, а число ребер — q:
Пусть v1, v2 — вершины, е = (v1, v2) — соединяющее их ребро. Тогда вершина v1 и ребро е инцидентны, вершина v2 и ребро е также инцидентны.
| Определения |
|---|
| Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. |
| Два ребра, инцидентные одной вершине, называются смежными; |
| две вершины, инцидентные одному ребру, также называются смежными. |
|
Множество вершин, смежных с вершиной v, называется
множеством смежности вершины v и обозначается
Г+(v):
|
| Замечание |
|---|
|
Если не оговорено противное, то подразумевается Г+ и
обозначается просто Г. |
Если А 
V — множество вершин, то Г(A) — множество всех вершин, смежных с вершинами из А:
Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.
Пример
На рис. 4 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины v1 и v2, v2 и v3, v3, и v4, v4 и v1, v2 и v4 смежны, а вершины v1 и v3 не смежны. Смежные ребра: e1 и е2, е2 и е3, е3 и e4, e4 и e1, e1 и e5, e2 и e5, e3 и e5, e4 и e5. Несмежные ребра: e1 и е3, е2 и e4.
Часто рассматриваются следующие родственные графам объекты.
1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е — дугами.
2. Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).
3. Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
4. Если элементами множества Е являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества Е называются гипердугами, а граф называется гиперграфом.
5. Если задана функция F: V 
М и/или F: Е
М, то множество М называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.
Далее выражение “граф G(V,E)” означает неориентированный непомеченный граф без петель и кратных ребер.
Говорят, что два графа G1(V1, E1) и
G2{V2, Е2) изоморфны (обозначается
G1 ~ G2), если существует биекция
h: V1
V2, сохраняющая смежность:
Изоморфизм графов есть отношение эквивалентности.
Действительно, изоморфизм обладает всеми необходимыми свойствами:
1. рефлексивность: G ~ G, где требуемая биекция суть тождественная функция;
2. симметричность: если G1 ~ G2 с биекцией h, то G2 ~ G1 с биекцией h-1;
3. транзитивность: если G1~ G2 с биекцией h и G2 ~ G3 с биекцией g, то G1 ~ G3 с биекцией g о h.
Т.о.
| Определение |
|---|
| изоморфными являются графы разные по начертанию, но отражающие одну и ту же сущность (имеющие одинаковые связи между вершинами. |
Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются
классы эквивалентности по отношению изоморфизма (вместо любого графа можно
использовать другой - изоморфный).
Пример
Три внешне различные диаграммы, приведенные на рис. 5, являются диаграммами одного и того же графа К3,3.
Числовая характеристика, одинаковая для всех изоморфных графов, называется инвариантом графа. Так, p(G) и q(G) — инварианты графа G.
Не известно никакого набора инвариантов, определяющих граф с точностью до изоморфизма.
Пример
Количество вершин, ребер и количество смежных вершин для каждой вершины не определяют граф. На рис. 6 представлены диаграммы графов, у которых указанные инварианты совпадают, но графы при этом не изоморфны.
Графом G(V,E) называется
Вершина и ребро называются инцидентными друг другу, если
Две вершины называются смежными, если
Два ребра называются смежными, если
Граф называется ориентированным (или орграфом), если
Граф называется псевдографом, если
Граф называется мультиграфом, если
Граф называется гиперграфом, если
Граф называется помеченным (или нагруженным), если
Ребра в орграфе называются
Вершины в орграфе называются
Ребра, каждое из которых, инцидентно только одной вершине назывются
Ребра инцидентные одной паре вершин называются
Ребра, инцидентные более чем двум вершинам назывaются