Введение

Дискретная математика, или дискретный анализ – область математики, которая занимается исследованием структур и задач на конечных множествах. Поэтому в качестве синонима иногда используется термин «конечная математика». Можно считать общепринятым деление математики на непрерывную и дискретную. Последняя представляет собой важное направление, имеющее характерные для него предмет исследований, методы и задачи. Специфика задач дискретной математики в первую очередь предполагает отказ от основных понятий классической математики – предела и непрерывности.

Дискретная и непрерывная математика взаимно дополняют друг друга. Понятия и методы одной часто используются в другой. Один и тот же объект может рассматриваться с двух точек зрения и в зависимости от этого выбирается непрерывная или дискретная математика.

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

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

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

1. Теория графов

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

Определение1.1. Пара (V(G), E(G)) называется простым графом, если V(G) – непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). В простом графе данную пару вершин может соединять не более чем одно ребро.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v₁, v₂, если оно соединяет эти вершины и наоборот, каждая из вершин v₁, v₂ инцидентна ребру е.

Рассмотрим графическое представление графов (табл. 1.1).

Таблица 1.1

Элементы графов	Геометрические элементы	Наименование элемента
х Х – вершина		точка в пространстве
(vi, vj)  V  (vi, vj)  V		направленный отрезок, ориентированное ребро
(vi, vj)  V  (vi, vj)  V		отрезок, неориентированное ребро
(vi, vi)  V		замкнутый отрезок, петля

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

Пример 1.1.

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

Иногда удобно преобразовать неориентированный граф в ориентированный – заменой одного неориентированного ребра парой ребер с противоположной ориентацией.

Приведем ряд понятий и определений для ориентированных и неориентированных графов. Там, где это специально не оговорено, те же понятия и определения переносятся без изменений на ориентированные и неориентированные псевдографы.

1.1.1. Смежность, инцидентность, степени

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

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

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v, w, если оно соединяет эти вершины и наоборот, каждая из вершин v, w инцидентна ребру е.

Определение1.5. Две вершины называются смежными, если существует ребро, концами которого они являются. Два ребра называются смежными, если они имеют общую вершину.

Определение1.6. Степенью вершины v графа G называется число (v) ребер графа, которым инцидентна эта вершина.

Определение1.7.Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.

Замечание.В случае неориентированного псевдографа обычно считается, что вклад каждой петли, инцидентной некоторой вершине v, равен 2 (тогда как вклад любого другого ребра, инцидентного вершине v, равен 1).

Определение1.8.Полустепенью исхода (захода) вершины v орграфа D называется число ⁺(v) (^-(v)) дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

Замечание.В случае ориентированногопсевдографа вклад каждой петли, инцидентной некоторой вершине v, равен 1, как в ⁺(v), так и в ^-(v).

Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).

Утверждение. Для любого псевдографаG выполняется равенство

Утверждение. Для любого ориентированного псевдографаD выполняется равенство

Пример 1.2.

Найти локальные степени графа (рис. 1.1) и орграфа (рис. 1.2).

Решение.

	 (u) = 2;  (v) = 2;  (z) = 3;  (m) = 1.
		+(u) = 1;  - (u) = 1; +(v) = 2;  - (v) = 0; +(z) = 0;  - (z) = 3; +(m) = 1;  - (m) = 0.

1.1.2. Изоморфизм, гомеоморфизм

Определение1.9. Два графа G₁ и G₂ называются изоморфными, если существует взаимно однозначное соответствие между множествами их вершин, обладающее тем свойством, что число ребер, соединяющих любые две вершины в G₁, равно число ребер, соединяющих соответствующие вершины в G₂.

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

Изоморфизм графов есть отношение эквивалентности.

Пример 1.3.

На рисунке 1.3 изображены три изоморфных графа. На рисунке 1.4 изображены два неизоморфных графа.

Графы рассматриваются с точностью до изоморфизма, то есть рассматриваются классы эквивалентности по отношению изоморфизма.

Пример 1.4.

С точностью до изоморфизма существует ровно четыре простых графа с тремя вершинами и одиннадцать с четырьмя вершинами. Постройте эти графы.

Решение.

1. Построим четыре простых графа с тремя вершинами с точностью до изоморфизма (рис. 1.5):

2. Построим одиннадцать простых графов с четырьмя вершинами с точностью до изоморфизма (рис. 1.6):

Определение1.10. Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | {(u, v)} двух дуг (u, v), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Определение1.11. Орграф D₁ называется подразбиением орграфа D₂, если орграф D₁ можно получить из D₂ путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Определение1.12.Орграфы D₁, D₂ называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

1.1.3. Матричное задание графов.

Матрицы смежности, инцидентности

Пусть D = (V, Х) – орграф, где V={v₁, v₂, …,v_n}, X={x₁, x₂, …, x_m}.

Определение1.13. Матрицей смежности орграфа D называется квадратная матрица A(D)=[a_ij] порядка n, у которой

Определение1.14.Матрицей инцидентности орграфа D называется (nm) –матрица B(D)=[b_ij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v₁, v₂, …,v_n}, X={x₁, x₂, …, x_m}.

Определение1.15.Матрицей смежности графа G называется квадратная матрица A(G)=[a_ij] порядка n, у которой

Определение1.16.Матрицей инцидентности графа G называется (nm) –матрица B(G)=[b_ij], у которой

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

Пример 1.5.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 1.7).

Решение.

Матрица смежности имеет вид .

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

Для того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 1.8). Матрица инцидентности имеет вид:

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

Пример 1.6.

Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 1.9).

Решение.

	Матрица смежности имеет вид:
	Матрица инцидентности имеет вид

1.1.4. Примеры графов. Операции над графами

Рассмотрим некоторые важные типы графов.

Определение 1.17.Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают Nn. Заметим, что у вполне несвязного графа все вершины изолированы.
Определение 1.18.Простой граф, в котором любые две вершины смежны, называется полным. Полный граф обозначают Кn.

Заметим, что для полного графа выполняется равенство , где m – число ребер, n – число вершин графа.

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

Регулярные графы степени 3 называются кубическими (или трехвалентными).

Пример 1.7.

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

Среди регулярных графов особенно интересны так называемые платоновы графы – графы, образованные вершинами и ребрами пяти правильных многогранников – Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

На рис. 1.11 приведен граф, соответствующий кубу.

Определение1.20. Допустим, что множество вершин графа G можно разбить на два непересекающихся подмножества V₁ и V₂ так, что каждое ребро в G соединяет какую-нибудь вершину из V₁ с какой-нибудь вершиной из V₂, тогда данный граф называется двудольным.

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

Определение1.21. Если в двудольном графе каждая вершина из V₁ соединена с каждой вершиной из V₂, то граф называется полным двудольным.

Обозначение. К_{m. n}

Заметим, что граф К_{m. n} имеет ровно m + n вершин и mn ребер.

Пример 1.8.

На рис. 1.12 изображены двудольные графы.

Определение1.22.Объединением графов называется граф

Определение1.23.Пересечением графов , где , называется граф

Определение1.24.Соединением графов G₁ и G₂ является новый граф, у которого V=V₁V₂ , а множеством ребер являются все ребра первого и второго графа и ребра, соединяющие между собой каждую вершину первого графа с первой вершиной второго графа.

Определение1.25. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

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

Определение 1.26. Связный регулярный граф степени 2 называется циклическим графом. Обозначается Сn (рис. 3.13). Определение 1.27. Соединение графов N1 и Cn-1 (n3) называется колесом с n вершинами. Обозначается Wn (рис. 1.13).

Определение1.28.Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

Обозначение.

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

Определение1.29.Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

1.1.5. Маршруты, цепи, циклы

Введем понятие маршрута для графа G = (V, E) (и соответственно понятие пути для орграфа D = (V, E)).

Определение1.30.Маршрутом в данном графе G называется конечная последовательность ребер вида {v₀, v₁}, {v₁, v₂}, …, {v_m-1, v_m} (обозначаемая также v₀v₁v₂…v_m).

Каждому маршруту соответствует последовательность вершин v₀v₁v₂…v_m; v₀ – начальная вершина, аv_m – конечная вершина маршрута.Одна и та же вершина может одновременно оказаться начальной, конечной и внутренней. Таким образом, мы будем говорить о маршруте из v₀ в v_m.

Определение1.31.Длиной маршрута называется число ребер в нем.

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

Определение1.33.Цепь или простая цепь замкнуты, если начальная и конечная вершины совпадают.

Определение1.34. Замкнутая простая цепь, содержащая, по крайней мере, одно ребро, называется циклом.

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

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

Определение1.36.Вершинаw орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w(маршрут, соединяющий v, w).

Дадим более удобное определение связных графов.

Определение1.37. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.

Определение1.38. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

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

Определение1.40. Если граф не является связным, то он называется несвязным.

Определение1.41.Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

В дальнейшем количество компонент связности графа будем обозначать k.

Пример 1.9.

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

Теорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

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

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

Определение1.43.Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Определение1.44.Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение1.45. Разрез, состоящий из одного ребра, называется мостом (перешейком).

Пример 1.10.

Для графа, изображенного на рис. 1.14, каждое из множеств {e1, e2, e5} и {e3, e6, e7, e8} является разделяющим. Разрезом является множество ребер {e1, e2}. В графе возможно выделить несколько разделяющих множеств и разрезов.