Графов теория - раздел конечной математики, особенностью которого является геометрический подход к изучению объектов. Основное понятие теории - граф. Понятие графа опирается на основные понятия теории множеств, так как граф можно рассматривать как объект, состоящий из двух множеств - множества точек (вершин) X и множества линий (рёбер) U, которые соединяют некоторые вершины. При этом совершенно несущественно, соединены ли вершины графа отрезками прямых линий или криволинейными дугами, какова длина линий, как расположены вершины графа на плоскости и другие геометрические характеристики графа. Каждое ребро представляет собой неупорядоченную пару вершин из множества X.
Математическая запись графа включает обозначения множеств вершин и рёбер, например,

G = (X, U),

(1)

где X - множество вершин;
U - множество рёбер.
Пример изображения графа G, состоящего из множества вершин X = {x₁, x₂, x₃, x₄, x₅} и множества рёбер U = {u₁₂, u₁₃, u₁₄, u₁₅, u₂₄, u₂₅, u₃₅} представлен на рис. 1.

Рис. 1 Элементы множеств X и U могут содержать индексы. Индексы вершин обозначают их номера. Индексы рёбер обозначают номера соединяемых ими вершин. Запись u_ij означает, что ребро графа образовано парой вершин x_i и x_j: u_ij = (x_i, x_j), x_i X, x_j X.
Виды графов. Основные понятия и определения
Конечный граф - это граф G = (X, U), у которого количество его вершин |X| конечно. Конечный граф представлен на рис. 1.
Нуль-граф - это граф G = (X, U), состоящий только из изолированных вершин, т.е. граф, не содержащий ни одного ребра (|U| = 0). Такой граф обозначается G₀. Нуль-граф, у которого |X| = 5 и |U| = 0 представлен на рис. 2.

Рис. 2 Пустой граф - это граф G = (X, U), не содержащий ни вершин, ни рёбер (|X| =0, |U| = 0). Такой граф обозначается G_ø.
Неориентированный граф (неограф) - это граф G = (X, U), для каждого рёбра которого несуществен порядок двух его концевых вершин. Неограф представлен на рис. 1. Рёбра неографа иногда называют звеньями. Ориентированный граф (орграф) - это граф, для каждого ребра которого существен порядок двух его концевых вершин. Орграф представлен на рис. 3 и обозначается . Рёбра орграфа иногда называют дугами.

Рис. 3	Рис. 4

Смешанный граф (рис. 4) - это граф, который содержит как ориентированные, так и неориентированные рёбра. Смешанный граф обозначается .
Любой из перечисленных видов графа может содержать одно или несколько рёбер, у которых оба конца сходятся в одной вершине, т.е. u_ij U, u_ij = (x_i, x_j), i = j. Такие рёбра называются петлями. На рис. 5 представлен смешанный граф с петлями.

Рис. 5	Рис. 6

В общем случае множество рёбер U может состоять из трёх непересекающихся подмножеств: подмножества звеньев, подмножества дуг и подмножества петель.
Ребро u_ij, соединяющее вершины xi и xj, инцидентно данным вершинам и наоборот, вершины x_i и x_j инцидентны ребру u_ij. Ребро u₁₂ (рис. 6) инцидентно вершинам x₁ и x₂, а вершины x₁ и x₂, в свою очередь, инцидентны ребру u₁₂.
Мультиграф (рис. 6) - это граф, у которого любые две вершины соединены более чем одним ребром. Рёбра, соединяющие одну и ту же пару вершин, называются кратными. Наибольшее число кратных рёбер, соединяющих какую-либо пару вершин, называется мультичислом. Мультичисло графа, представленного на рис. 6, m = 5.
Скелет мультиграфа - это граф, полученный из исходного мультиграфа путём удаления петель и сведения кратных рёбер в одно ребро. На рис. 7 показан скелет мультиграфа, представленного на рис. 6.
Полный граф (рис. 8) - это граф, у которого любые две вершины соединены ребром. Полный граф обозначается G_п.

Рис. 7	Рис. 8	Рис. 9

Плотный граф (рис. 9) - это полный граф, у которого при каждой вершине имеется петля. Плотный граф обозначается G′_п.
Изоморфные графы - это два графа G = (X, U) и G′ = (X′, U′), у которых можно установить взаимно однозначное соответствие X ↔ X′, U ↔ U′, такое, что, если x_i, x_j X соответствует x′_i, x′_j X′ то ребро u_ij U соответствует ребру ребро u′_ij U′. На рис. 10 и 11 показаны изоморфные графы G₁ и G₂, у которых вершинам x₁, x₂, x₃, x₄, x₅, x₆ поставлены во взаимно однозначное соответствие вершины x′₁, x′₂, x′₃, x′₄, x′₅, x′₆.

Рис. 10	Рис. 11

Плоский граф - это граф G = (X, U), у которого рёбра расположены на плоскости таким образом, что пересекаются только в вершинах.
Планарный граф - это граф G = (X, U), изоморфный плоскому графу.
Смежными вершинами называются любые две вершины x_i, x_j X графа G = (X, U), инцидентные одному и тому же ребру. Так, например, вершины x_i и x_j (рис. 1) являются смежными, а вершины x₄ и x₄ смежными не являются, так как не соединены между собой, т.е. ребро u₄₅ отсутствует.
Локальной степенью (или просто степенью) вершины x_i графа G = (X, U) называется количество рёбер ρ(x_i), инцидентных данной вершине. Сумма локальных степеней всех вершин графа G = (X, U) есть удвоенное количество всех его рёбер:
Поскольку для полного графа ρ(x₁) = ρ(x₂) = ... = ρ(xn) = n - 1, то в этом случае
. Заметим, что и, следовательно, в графе G = (X, U) количество вершин нечётной степени чётно.
Граф называется однородным степени t, если локальные степени всех его вершин равны между собой, т.е.
ρ(x₁) = ρ(x₂) = ... = ρ(x_n) = t. Количество рёбер однородного графа степени t равно
. Элементы графов
Подграф G′ = (X′, U′) - это часть графа G = (X, U), если X′ X, а множество U? ? U образовано всеми рёбрами, соединяющими между собой только вершины их множества X′.
Cуграф G′ = (X′, U′) - это часть графа G = (X, U), если X′ = X, U′ U.
Кусок G_i = (X_i, U_i) - это часть графа G = (X, U), если Xi X, U_i U, причём U_i=U_iiU_ij, где Uii - множество рёбер, соединяющих вершины из множества X_i между собой;
U_ij - множество рёбер, соединяющих вершины из множества X_i с вершинами из множества XX_i.
На рис. 12 показан граф G = (X, U), а на рис. 13-15 - подграф, суграф и кусок этого графа соответственно.

Рис. 12	Рис. 13
Рис. 14	Рис. 15

Если G_i = (X_i, U_i), i I = {1, 2, ..., l} - части графа G = (X, U), причём, , , то граф G можно определить как объединение всех его частей G_i, т.е. .
Связность графов
Пусть задан неограф G = (X, U) без петель и кратных рёбер.
Маршрут - это последовательность рёбер u_i U, заданных парами вершин вида (x₁, x₂) (x₂, x₃) ... (x_i-1, x_i), в которой любые два соседних ребра смежные. Количество рёбер в маршруте определяет его длину.
Если все рёбра в маршруте различны, то такой маршрут является цепью.
Если в цепи нет повторяющихся вершин, кроме соседних, то такая цепь называется простой.
Цепь, в которой совпадают начальная и конечная вершины, называется циклом.
Простая цепь, в которой совпадают начальная и конечная вершины, образует простой цикл.
Граф, представленный на рис. 1, содержит, например,
маршрут: (x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₄) (x₄, x₁);
простую цепь (x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₄);
простой цикл (x₁, x₃) (x₃, x₅) (x₅, x₂) (x₂, x₁).
Две вершины x_i, x_j X, x_i ≠ x_j графа G = (X, U) называются связанными, если их можно соединить маршрутом.
Граф G = (X, U) называется связным, если любые две его вершины связаны маршрутом.
Если взять какую-либо вершину x_i X графа G = (X, U) и построить подмножество X′ X, состоящее из всех вершин, которые можно соединить с вершиной x_i произвольным маршрутом, причём x_i включается в множество X′, то подграф G′ = (X′, U′), образованный на множестве вершин X′, называется компонентой связности графа G.
Связный граф состоит из единственной компоненты связности. Если граф имеет несколько компонент связности, то он несвязен, так как вершины из разных компонент связности нельзя соединить маршрутом. На рис. 16 показан граф G = (X, U), состоящий из трёх компонент связности G₁, G₂ и G₃, представленных на рис. 17-19.

Рис. 16	Рис. 17	Рис. 18	Рис. 19

Связный граф без циклов называется деревом. В дереве любые две вершины связаны единственной цепью. Пример дерева показан на рис. 20.

Рис. 20 Общее количество деревьев d, которое можно построить на n вершинах, определяется по формуле (теорема Кэли)
d = n^n-2 Цикл C_э, в котором содержатся все рёбра графа, причём каждое ребро встречается только один раз, называется эйлеровым. Граф содержит Эйлеров цикл, если он связен и все локальные степени его вершин чётны.
Цикл C_г, проходящий через каждую вершину графа по одному разу, называется гамильтоновым. Для гамильтонова цикла, в отличие от эйлерова цикла, неизвестен общий критерий существования. В литературе можно встретить только частные критерии, например, согласно одному из критериев в графе существует гамильтонов цикл, если для любой пары вершин x_i, x_j X графа G сумма локальных степеней ρ(x_i) + ρ(x_j) ≥ n.
Характеристические числа графов
Характеристические числа графов рассмотрим на примере графа G = (X, U) без петель и кратных рёбер.
Раскраска вершин графа - это такое разбиение множества его вершин на p непересекающихся подмножеств
X₁, X₂, ..., X_p, X = Xi, Xi ∩ Xj = Ø, i, j {1, 2, ..., p}, при котором каждое подмножество X_i не содержит смежных вершин.
Если каждому подмножеству X_i поставить в соответствие определённую "краску", то вершины этого подмножества будут окрашены одинаковым цветом, вершины другого подмножества X_j - другим и т.д., т.е. вершины любой смежной пары окрашиваются в разные цвета.
Хроматическое число ξ(G) - это наименьшее количество подмножеств, на которое можно разбить граф при раскраске.
Пример: множество вершин X = { x₁, x₂, x₃, x₄, x₅, x₆) графа G (рис. 21) можно разбить не менее чем на три непересекающихся подмножества: X1 = {x₁,x₃, x₆}; X₂ = {x₂, x₄}; X₃ = {x₅}.

Рис. 21 Хроматическое число рассматриваемого графа ξ(G) = 3, т.е. вершины графа можно раскрасить красками тремя цветов.
Предположим, что граф G = (X, U) имеет n вершин, r рёбер и p компонент связности. Наименьшее количество рёбер, после удаления которых в графе не содержится ни одного цикла, называется цикломатическим числом γ(G). Цикломатическое число определяется по формуле
γ(G) = r - n + p Для графа G (рис. 21), у которого n = 6, r = 7, p = 1 цикломатическое число γ(G) = 7 - 6 + 1 = 2.
Цикломатическое число не может принимать отрицательные значения.
Связный граф, у которого γ(G) = 0, является деревом, так как не содержит ни одного цикла.
Подмножество ψ_i X графа G называется внутренне устойчивым, если любые две вершины из этого подмножества не смежные.
В каждом графе без петель и кратных рёбер можно выделить семейство
Ψ = {ψ₁, ψ₂, ..., ψ_i} всех внутренне устойчивых подмножеств. Эти подмножества различаются количеством входящих в них элементов.
Число внутренней устойчивости η(G) определяется мощностью внутренне устойчивого подмножества, содержащего наибольшее число элементов, т.е. характеризует максимальное число несмежных вершин графа:
η(G) = max | ψ_i | Пример: граф, представленный на рис. 22, имеет:
Ψ_i = { Ψ₁, Ψ₂, Ψ₃, Ψ₄, Ψ₅}, Ψ₁ = {x₁, x₄, x₆}, Ψ₂ = {x₂, x₅}, Ψ₃ = {x₂, x₆}, Ψ₄ = {x₃, x₄, x₅}, Ψ₅ = {x₄, x₅}.
Число внутренней устойчивости η(G) = 3.

Рис. 22 Иногда по аналогии с числом внутренней устойчивости рассматривают число внутренней полноты χ(G), которое определяет максимальное число вершин графа G, образующих полный подграф. Для графа G, представленного на рис. 22, семейство внутренне полных подмножеств имеет вид:
Φ = {φ₁, φ₂, φ₃, φ₄,}, φ₁ = {x₁, x₂, x₃}, φ₂ = {x₁, x₃, x₅}, φ₃ = {x₂, x₄}, φ₄ = {x₅, x₆}, а число внутренней полноты χ(G) = max |φ_i| = 3,φ Φ.
Способы задания графа
1-й способ - рисунок. Это самый наглядный способ, хорошо раскрывает содержательный смысл интерпретируемого объекта, но он не формален. Следует заметить, что современный уровень развития машинной графики уже позволяет задавать граф в виде рисунка на экране дисплея и последующее его числовое представление в виде различного рода матриц, над которыми можно производить различные математические преобразования, предписываемые алгоритмами решения конкретных задач. Для преобразования рисунка в формальное математическое описание на языке программирования несложно разработать прикладную пользовательскую программу.
2-й способ - метод соответствий. Если задано множество вершин X и соответствие T, сопоставляющее каждой вершине x X графа множество вершин T_x, связанных с ней рёбрами, то определён граф G = (X, T). Для графа, представленного на рис. 1: X = {x₁, x₂, x₃, x₄, x₅}.
T_x1 = {x₂, x₃, x₄, x₅}; T_x2 = {x₁, x₄, x₅}; T_x3 = {x₁, x₅}; Tx₄ = {x₁, x₂}; Tx₅ = {x₇, x₂, x₃}. 3-й способ - матричный. Граф может описываться матрицей смежности, матрицей инцидентности или списком рёбер. Для описания метрических свойств графа используются матрица расстояний и матрица геометрии. В процессе решения конкретных задач действия на матрицами могут порождать производные матрицы, содержащие промежуточные результаты и окончательные решения. Рассмотрим матрицы, описывающие исходное состояние графа.
Матрица смежности - это квадратная матрица R = ||r_ij||_n×n, у которой строки и столбцы соответствуют вершинам графа, r_ij - элемент матрицы, расположенный на пересечении i-й строки и j-го столбца. Значение r_ij определяет количество рёбер, соединяющих вершины x_i и x_j. Порядок матрицы n определяется количеством вершин графа. Граф, представленный на рис. 22, описывается матрицей смежности:

		x1	x2	x3	x4	x5	x6
	x1	0	1	1	0	1	0
	x2	1	0	1	1	0	0
R=	x3	1	1	0	0	1	0
	x4	0	1	0	0	0	0
	x5	1	0	1	0	0	1
	x6	0	0	0	0	1	0

Матрица смежности симметрична относительно главной диагонали. Матрицы смежности в большинстве случаев на 80 85% заполнены нулевыми элементами, поэтому иногда используют список рёбер (кодовую реализацию R_k) матрицы смежности R. Матрица R_k - это таблица, состоящая из строк вида i, z_k, x_j>, каждая из которых определяет количество рёбер z_k, соединяющих вершины x_i и x_j. Для графа, представленного на рис. 22, список рёбер имеет вид

xi	zk	xj
x1	1	x2
x1	1	x3
x1	1	x5
x2	1	x1
x2	1	x3
x2	1	x4
x3	1	x1
x3	1	x2
x3	1	x5
x4	1	x1
x5	1	x1
x5	1	x3
x5	1	x6
x6	1	x5

Матрица инцидентности - это прямоугольная матрица I = ||i_mn||_n×u, у которой строки соответствуют вершинам x₁, x₂, ..., x_m графа, а столбцы - ребрам графа u₁, u₂, ..., u_n. Граф, представленный на рис. 22, описывается матрицей инцидентности

		u1	u2	u3	u4	u5	u6	u7
	x1	1	1	1	0	0	0	0
	x2	1	0	0	1	1	0	0
I=	x3	0	1	0	0	1	1	0
	x4	0	0	0	1	0	0	0
	x5	0	0	1	0	0	1	1
	x6	0	0	0	0	0	0	1

Метрические свойства графа
Расстояние d(x_i, x_j) между вершинами x_i, x_j X графа G = (X, U) называется длина кратчайшей цепи, соединяющей эти вершины. Длина цепи - это количество входящих в неё рёбер. Функцию расстояний удобно задавать матрицей расстояний D = ||d_ij||_n×n. Для графа, представленного на рис. 22, матрица расстояний имеет вид

		x1	x2	x3	x4	x5	x6
	x1	0	1	1	2	1	2
	x2	1	0	1	1	2	3
I=	x3	1	1	0	2	1	2
	x4	2	1	2	0	3	4
	x5	1	2	1	3	0	1
	x6	2	3	2	4	1	0

Матрица расстояний, как и матрица смежности, симметрична относительно главной диагонали.
Функция расстояний часто определяется для графов G_r, называемых координатной решёткой (рис. 23). Расстояние между двумя соседними узлами решётки называется шагом решётки и принимается равным единице. Расстояние между любыми двумя вершинами графа, отображённого в решётку, определяется по формуле
d_ij = | s_i - s_j | + | t_i - t_j |, где s_i, s_j, t_i, t_j - координаты узлов решётки, в которых расположены вершины x_i и x_j.
Отображение произвольного графа в решётку часто осуществляется для решения практических задач, например, размещения радиоэлектронных компонентов на коммутационном поле печатной платы. На рис. 24 представлен произвольный граф, а на рис. 25 - отображение этого графа в решётку с размерами 4×2.

Рис. 24	Рис. 25

Для определения суммарной длины рёбер графа используется матрица геометрии Dγ - часть матрицы расстояний, в которой исключены элементы d_ij, если вершины графа x_i и x_j не смежны. Для получения матрицы геометрии необходимо перемножить соответственные элементы матрицы смежности и матрицы расстояний, т.е.
Dγ = || r_ij • d_ij || Сумма элементов матрицы геометрии равна удвоенной суммарной длине рёбер графа при данном отображении его в решётку.
Если известны расстояния между каждой парой вершин графа, то можно определить его диаметр d(G) как максимальное расстояние между двумя вершинами:
d(G) = max d(x_i, x_j), где x_i, x_j X.
Центр графа - это вершина x₀, для которой выполняется следующее условие
x X [max d(x_i, x_j) ≥ max d(x₀, x_j)], а величина d(x₀, x_j) определяет радиус графа.
Источники информации:

1. Кузнецов О.П. Дискретная математика для инженеров. / О.П. Кузнецов, Г.М. Адельсон-Вельский - 2-е изд., перераб. и доп. - М.: Энергоатомиздат, 1988 - 400 с.: ил.
2. Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик - М.: Наука, 1974. 304 с.: ил.