Помощь по Теле2, тарифы, вопросы

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

Алгорифм для непосредственного выявления эйлерова цикла.
[Флёрн (Fleury)]. Рассмотрим связный мультиграф G, все вершины которого имеют четную степень, и постараемся нарисовать его одним росчерком, не прибегая в процессе построения к исправлениям уже начерченной части траектории. Достаточно придерживаться следующего правила:
1 Выходим из произвольной вершины а; каждое пройденное ребро зачеркиваем.
2 Никогда не идем по такому ребру и, которое в рассматриваемый момент является перешейком (т.е. при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру),

Соблюдая это правило, мы всегда будем находиться в благоприятном положении, потому что когда мы находимся в х = а, граф (из незачеркнутых ребер) имеет две вершины нечетной степени: х и а; если отбросить изолированные вершины, то останется связный граф, который в силу теоремы 1 имеет эйлерову цепь, начинающуюся в х.

Содержание
Введение
Глава 1. Основные определения
Множества и многозначные отображения
Граф. Пути и контуры
Цепи и циклы
Глава 2. Предварительное изучение квазиупорядоченности
Квазипорядок, определяемый графом
Индуктивный граф и базы
Глава 3. Порядковая функция и функция
Гранди для бесконечного графа
Общие соображения относительно бесконечных графов
Порядковая функция
Функции Гранди
Операции над графами
Глава 4. Основные числа теории графов
Цикломатическое число
Хроматическое число
Число внутренней устойчивости
Число внешней устойчивости
Глава 5. Ядра графа
Теоремы существования и единственности
Приложение к функциям Гранди
Глава 6. Игры на графе
Игра Ним
Общее определение игры (с полной информацией)
Стратегии
Глава 7. Задача о кратчайшем пути
Процессы по этапам Некоторые обобщения
Глава 8. Транспортные сети
Задача о наибольшем потоке Задача о наименьшем потоке
Задача о потоке, совместимом с множеством значений
Бесконечные транспортные сети
Глава 9. Теорема о полустепенях
Полу степени исхода и захода
Глава 10. Паросочетание простого графа
Задача о наибольшем паросочетании
Дефицит простого графа
Венгерский алгорифм
Обобщение на бесконечный случай
Приложение к теории матриц
Глава 11. Факторы
Гамильтоновы пути и гамильтоновы контуры
Нахождение фактора
Нахождение частичного графа с заданными полустепенями
Глава 12. Центры графа
Центры
Радиус
Глава 13. Диаметр сильно связного графа
Общие свойства сильно связных графов без петель
Диаметр
Глава 14. Матрица смежности графа
Применение обычных матричных операций
Задачи на подсчет
Задача о лидере
Применение булевых операций
Глава 15. Матрицы инциденций
Вполне унимодулярные матрицы
Вполне унимодулярные системы
Цикломатические матрицы
Глава 16. Деревья и прадеревья
Деревья
Аналитическое исследование
Прадеревья
Глава 17. Задача Эйлера
Эйлеровы циклы Эйлеровы контуры
Глава 18. Паросочетание произвольного графа
Теория чередующихся цепей
Нахождение частичного графа с заданными степенями вершин
Совершенное паросочетание
Приложение к числу внутренней устойчивости
Глава 19. Фактороиды
Гамильтоновы циклы и фактороиды
Необходимое и достаточное условие существования фактороида
Глава 20. Связность графа
Точки сочленения
Графы без сочленений
h-связные графы
Глава 21. Плоские графы
Основные свойства
Обобщение
Добавления
I. Off общей теории, игр
II. О транспортных задачах
III. Об использовании, понятия потенциала в транспортных сетях
IV. Нерешенные задачи, и недоказанные предположения
V. О некоторых основных принципах подсчета (Ж. Риге)
VI. Дополнения к русскому переводу (А.А. Зыков и Г.И. Кожухин)
Литература
Теория графов и книга К. Бержа (послесловие к русскому переводу)
Указатель символов
Именной указатель
Предметный указатель.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория графов и её применение, Берж К. - fileskachat.com, быстрое и бесплатное скачивание.

Теория графов - раздел математики, используемый в информатике и программировании, экономике, логистике, химии.

Что такое граф

Часто для описания строения систем используют графические схемы. Элементы в них изображают кружками, точками, квадратами и т. п., а связи между элементами - линиями или стрелками. При этом ни то, как изображаются элементы, ни длина или форма линий не важны - имеет значение только, какие элементы соединены. Итак, граф - это пара вида (A, M), где A - конечное множество вершин, а M - множество ребер - линий, связывающих некоторые вершины.

Основные понятия теории графов

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

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

Если вершины a и b - концы ребра (или начало и конец дуги) графа, то говорят, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b - концы ребра, то они (a и b) называются смежными.

Чаще всего рассматривают графы, ребра которых имеют один тип - являются ориентированными или нет.

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

Теория графов также использует понятие «петля» - ребро, выходящее и заходящее в одну и ту же вершину. Граф, в котором есть петли, называется псевдографом.

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

Каждая вершина орграфа характеризуется:

• Полустепенью исхода. Это количество дуг, выходящих из нее.
• Полустепенью захода. Это количество дуг, которые входят в данную вершину.

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

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

Вершина со степенью 0 называется изолированной.

Висячей вершиной является вершина со степенью 1.

Теория графов называет пустым графом такой, в котором нет ни одного ребра. Полный граф - это обыкновенный граф, в котором смежны любые 2 вершины.

Взвешенные графы - это графы, вершинам или ребрам (дугам) которых или и вершинам, и ребрам (дугам) сразу, приписываются некоторые числа. Они называются весами. На втором рисунке показан неориентированный граф, ребра которого взвешены.

Графы: изоморфизм

Понятие изоморфизма используется в математике. В частности, теория графов определяет его так: два графа U и V изоморфны, если в этих графах существует биекция между множествами их вершин: каждые 2 вершины в графе U соединены ребром в том и только том случае, если в графе V связаны ребром те же вершины (которые могут по-другому называться). На рисунке ниже показаны два изоморфных графа, в которых между вершинами, окрашенными в одинаковые цвета и в первом, и во втором графе, существует вышеописанная биекция.

Пути и циклы

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

Теория графов в программировании используется для построения граф-схем алгоритмов.

Теория графов - один из обширнейших разделов дискретной математики, широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, психологии, социологии, лингвистике, других областях знаний. Теория графов систематически и последовательно изучает свойства графов, о которых можно сказать, что они состоят из множеств точек и множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард Эйлер (1707-1882), решивший в 1736 году известную в то время задачу о кёнигсбергских мостах.

Графы строят для того, чтобы отобразить отношения на множествах . Пусть, например, множество A = {a 1 , a 2 , ... a n } - множество людей, а каждый элемент будет отображён в виде точки. Множество B = {b 1 , b 2 , ... b m } - множество связок (прямых, дуг, отрезков - пока не важно). На множестве A задано отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой. Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф!

То, что мы сначала назвали "точками", следует называть вершинами графа, а то, что называли "связками" - рёбрами графа.

Теория графов не учитывает конкретную природу множеств A и B . Существует большое количество самых разных конкретных задач, при решении которых можно временно забыть о специфическом содержании множеств и их элементов. Эта специфика никак не сказывается на ходе решения задачи, независимо от её трудности! Например, при решении вопроса о том, можно ли из точки a добраться до точки e , двигаясь только по соединяющим точки линиям, неважно, имеем ли мы дело с людьми, городами, числами и т.д. Но, когда задача решена, мы получаем решение, верное для любого содержания, которое было смоделировано в виде графа. Не удивительно поэтому, что теория графов - один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с собеседником и вопросы любви, и вопросы музыки или спорта, и вопросы решения различных задач, причем делает это без всякого перехода (переключения), без которого в подобных случаях не обойтись человеку.

А теперь строгие математические определения графа.

Определение 1. Графом называется система объектов произвольной природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.

Определение 2. Пусть V – (непустое) множество вершин, элементы v ∈V – вершины. Граф G = G (V ) с множеством вершин V есть некоторое cемейство пар вида: e = (a , b ) , где a ,b ∈V , указывающих, какие вершины остаются соединёнными. Каждая пара e = (a , b ) - ребро графа. Множество U - множество рёбер e графа. Вершины a и b – концевые точки ребра e .

Графы как структура данных. Широким применением теории графов в компьютерных науках и информационных технологиях обусловлено добавлением к вышеизложенным определениям понятия графа как структуры данных. В компьютерных науках и информационных технологиях граф определяется как нелинейная структура данных. Что же тогда - линейная структура данных и чем от них отличаются графы? Линейные структуры данных характеризуются тем, что связывают элементы отношениями типа "простого соседства". Линейными структурами данных являются, например, массивы, таблицы, списки, очереди, стеки, строки. В противоположность им нелинейные структуры данных - такие, в которых элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порождённые и подобные. Итак, граф - нелинейная структура данных.

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

Основные понятия теории графов

Понятие инцидентности необходимо и при составлении алгоритмов решения многих практических задач с графами. Например, можно ознакомиться с программной реализацией обхода в глубину графа, представленного матрицей инцидентности . Идея проста: можно двигаться лишь через вершины, соединённые рёбрами. А уж если рёбрам приписаны какие-то значения ("весы", чаще всего в виде чисел, такие графы называются взвешенными или помеченными), то можно решать сложные прикладные задачи, некоторые из которых упомянуты в завершающем параграфе этого урока.

Классические задачи теории графов и их решения

Один из первых опубликованных примеров работ по теории графов и применения графов - работа о "задаче с Кёнигсбергскими мостами" (1736 г.), автором которой является выдающийся математик 18-го века Леонард Эйлер. В задаче даны река, острова, которые омываются этой рекой, и несколько мостов. Вопрос задачи: возможно ли, выйдя из некоторого пункта, пройти каждый мост только по одному разу и вернуться в начальный пункт? (рисунок ниже)

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

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

По устоявшейся традиции эйлеровым графом называется граф, в котором можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер. Задача средней трудности на эйлеровы графы - в материале "Основные виды графов ".

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

Кэли в 1858 г., занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры насыщенных углеводородов, с данным числом атомов углерода. Кэли прежде всего сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось сразу решить эту задачу, и он стал изменять её формулировку таким образом, чтобы можно было решить новую задачу о перечислении:

• корневых деревьев (в которых выделена одна из вершин);
• всех деревьев;
• деревьев, у которых степени вершин не превышают 4;
• деревьев, у которых степени вершин равны 1 и 4 (постановка задачи из химии).

Задачи с графами для закрепления основных понятий

Пример 1. Пусть A - множество чисел 1, 2, 3 : A = {1, 2, 3} . Построить граф для отображения отношения "

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

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

Пример 2. Пусть A - множество чисел 2, 4, 6, 14 : A = {2, 4, 6, 14} . Постоить граф для отображения отношения "делится нацело на" на этом множестве.

Решение. В этом примере часть рёбер будут иметь направление, а некоторые не будут, то есть строим смешанный граф . Перечислим отношения на множестве: 4 делится нацело на 2, 6 делится нацело на 2, 14 делится нацело на 2, и ещё каждое число из этого множества делится нацело на само себя. Это отношение, то есть когда число делится нацело на само себя, будем отображать в виде рёбер, которые соединяют вершину саму с собой. Такие рёбра называются петлями . В данном случае нет необходимости давать направление петле. Таким образом, в нашем примере три обычных направленных ребра и четыре петли. Получаем следующий граф:

Пример 3. Пусть даны множества A = {α, β, γ} и B = {a, b, c} . Построить граф для отображения отношения "декартово произведение множеств".

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

Пример 4. В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений "Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3, О5, О6", "Пётр работает с объектом О8".

Решение. Граф, отображающий данные отношения, будет так же двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Однако, в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рёбрам направления может показаться "математической тупостью". Но всё же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф:

И вновь к примерам с числами.

Пример 5. Пусть задано множество C = {2, 3, 5, 6, 15, 18} . Построить граф, реализующий отношение, определяющее все пары чисел a и b из множества C , у которых при делении второго элемента на первый получаем частное, которое является целым числом больше 1.

Решение. Граф, отображающий данные отношения, будет ориентированным, так как в условии есть упоминание о втором и первом элементе, то есть, ребро будет направлено от первого элемента ко второму. Из этого однозначно понятно, какой элемент является перым, а какой вторым. Ещё добавим терминологии: ориентированные рёбра принято называть дугами. В нашем графе будет 7 дуг: e 1 = (3, 15) , e 2 = (3, 18) , e 3 = (5, 15) , e 4 = (3, 6) , e 5 = (2, 18) , e 6 = (6, 18) , e 7 = (2, 6) . В этом примере рёбра (дуги) графа просто пронумерованы, но порядковые номера - не единственное, что можно приписать дуге. Дуге можно приписать также весы означающие, например, стоимость пересылки груза из одного пункта в другой. Но с весами дуг мы познакомимся позже и подробнее. Итак, получаем следующий ориентированный граф:

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

Пример 6. На кусочке шахматной доски размером 3 Х 3 размещены два белых коня и два чёрных коня так, как показано на рисунке ниже.

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

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

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

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

Пример 7. Задача о волке, козе и капусте. На одном берегу реки находятся человек (Ч), лодка, волк (В), коза (Кз) и капуста (Кп). В лодке одновременно могут находиться человек и не более одного из перевозимых объектов. Человек должен перевезти на другой берег все объекты, соблюдая условие: нельзя оставлять без присмотра волка вместе с козой и козу вместе с капустой.

Решение. В конструируемом графе вершины - конфигурации, а рёбра - отношение "связь одним плаваньем лодки" между конфигурациями. Конфигурация означает расположение объектов на первоначальном берегу и на противоположном берегу. Каждая конфигурация отображается в виде (A |B ) , где A - объекты, находящиеся на первоначальном берегу, а B - объекты, находящиеся на противоположном берегу. Первоначальная конфигурация, таким образом, - (ЧВКпКз | ) . Например, после переправки на другой берег козы конфигурация будет (ВКп |ЧКз ) . Конечная конфигурация всегда ( |ЧВКпКз ) . Теперь можем построить граф, зная уже, что означают вершины и рёбра:

Разместим вершины графа так, чтобы рёбра не пересекались, а соседними были вершины, которые связаны отношением на графе. Тогда увидеть отношения будет намного проще (для увеличения рисунка щёлкните по нему левой кнопкой мыши):

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

Теория графов и важнейшие современные прикладные задачи

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

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

Графы и задача о потоках

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

Каждая дуга графа отображает трубу. Числа над дугами (весы) - пропускная способность труб. Узлы - места соединения труб. Вода течёт по трубам только в одном направлении. Узел S - источник воды, узел T - сток. Требуется максимизировать объём воды, протекающей от источника к стоку.

Для решения задачи о потоках можно воспользоваться методом Форда-Фулкерсона. Идея метода: поиск максимального потока производится по шагам. В начале работы алгоритма поток полагается равным нулю. На каждом последующем шаге значение потока увеличивается, для чего ищется дополняющий путь, по которому поступает дополнительный поток. Эти шаги повторяются до тех пор, пока существуют дополнительные пути. Задача успешно применяется в различных распределённых системах: система электоснабжения, коммуникационная сеть, система железных дорог и других.

Графы и сетевое планирование

В задачах планирования сложных процессов, состоящих из множества работ, часть из которых выполняется параллельно, а часть последовательно, широкое применение получили взвешенные графы, известные под названием сети ПЕРТ (PERT).

PERT - Program (Project) Evaluation and Review Technique - техника оценки и анализа программ (проектов), которая используется при управлении проектами.

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

Если в сети есть дуги (a , b ) и (b , c ) , то работа, представленная дугой (a , b ) , должна быть завершена до начала выполнения работы, представленной дугой (b , c ) . Каждая вершина (v i ) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (v i ) .

В таком графе:

• одна вершина, не имеющая предшественников, определяет момент времени начала выполнения работ;
• одна вершина, не имеющая последователей, соответствует моменту времени завершения комплекса работ.

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

Весь блок "Теория графов"

Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

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

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

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

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

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

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

  Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами. Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.

• Способы представления

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

• Деревья

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

• Остовное дерево наименьшего веса

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

• Методы систематического обхода вершин графа

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

• Задача о путях во взвешенных ориентированных графах

• Изоморфизм графов

  Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин. В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.

• Топологическая сортировка

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

• Элементы цикломатики

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

ГРАФОВ ТЕОРИЯ, раздел дискретной математики, в котором изучаются свойства графов и их обобщений. Графом называется пара (V, Е), где V - множество точек, называемых вершинами, и Е - множество пар вершин, причём если порядок, в котором перечислены вершины в паре, не важен, то эта пара вершин графа называется ребром, а если важен - дугой. Граф, содержащий только рёбра, называется неориентированным графом, или просто графом, а граф, содержащий только дуги, - ориентированным графом. На рисунке 1 - неориентированный граф с вершинами а, b, с, d и рёбрами (а, b), (b, с), (с, d), (а, d), (а, с), (b, d), на рисунке 2 - ориентированный граф с вершинами а, b, с, d, е, f и дугами (а, b), (b, с), (с, d), (d, е), (е, f), (f, а).

Исторический очерк. Первые задачи графов теории были связаны с решением математических задач развлекательного характера и головоломок (смотри Комбинаторные задачи классические). Одним из первых результатов графов теории был критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах (смотри Гамильтонов цикл). С середины 19 века появляются относящиеся к графов теории работы, содержащие результаты, связанные с различными приложениями математики. Так, Г. Кирхгоф (1847) для составления полной системы уравнений для токов и напряжений в электрических сетях (смотри Кирхгофа правила) предложил представлять такую сеть графом и находить в этом графе остовные деревья, что приводит к решению задачи выделения независимых систем уравнений. Деревом называется связный граф, не содержащий циклов (рис. 3), остовное дерево графа - это его подграф, представляющий собой дерево, множество вершин которого совпадает с множеством вершин графа.

А.Кэли (1854) для подсчёта числа изомеров предельных углеводородов пришёл к задачам описания и перечисления деревьев, обладающих заданными свойствами. Термин «граф» утвердился в математике после выхода монографии немецкого математика Д. Кёнига (1936). Начиная со 2-й половины 20 века значительно расширились исследования в графов теории, в основном в силу развития дискретной математики и вычислительной техники. Задание графа равносильно заданию на элементах множества вершин V некоторого бинарного отношения. По этой причине, а также ввиду возможности наглядного представления графа в виде чертежа на плоскости, графовые модели используются при построении алгоритмов решения разнообразных задач как в математике и естествознании, так и в гуманитарных науках.

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

Особую роль при изучении графов играют матричные методы. Для графа G матрицей смежности А = A(G) = ||a ij || называется матрица, в которой a ij = 1, если в графе G вершина i связана с вершиной j ребром (или дугой в ориентированном графе) и a ij = 0 в противном случае. В первом случае говорят, что вершины i и j смежны, во втором случае - что они несмежны. Маршрутом в графе G называется последовательность ν 0 e 1 ν 1 ...ν n -1 e n ν n , состоящая попеременно из вершин и рёбер графа, в которой ребро е i соединяет вершины v i -1 и v i , i= l, ..., n; говорят, что этот маршрут связывает вершины v 0 и v n . Маршрут, в котором v 0 = v n , называется циклом. Маршрут называется цепью (соответственно, простой цепью), если все его рёбра (все его вершины) различны. При n≥ 1 элемент на месте (i, j) в матрице А n равен числу маршрутов длины n из вершины v i в вершину v j . Граф называется связным, если для любых его двух вершин существует маршрут, связывающий эти вершины. Для графа G с р вершинами и q рёбрами, в котором занумерованы как вершины, так и рёбра, рассматривается матрица инцидентности В(G), представляющая собой матрицу, состоящую из нулей и единиц с двумя единицами в каждом столбце; в столбце, соответствующем ребру, соединяющему вершины i и j, единица стоит в строках с номерами i и j. Говорят, что каждая из вершин i и j и соединяющее их ребро инцидентны, два ребра смежны, если они имеют общую инцидентную им вершину. Ранг матрицы инцидентности В(G) равен р 1 , если граф G является связным графом.

Множество собственных значений матрицы смежности графа или ориентированного графа (при этом каждое значение берётся столько раз, какова его кратность) называется спектром графа. Спектр графа с и вершинами состоит из n действительных чисел. Изучение спектра графа позволяет выяснить многие особенности его строения.

Задачи теории графов. Центральным в графов теории является раздел, изучающий структурные свойства графов. Одной из характеристик структуры графа является последовательность степеней его вершин. Степенью вершины неориентированного графа называется число инцидентных ей рёбер. Графическим разбиением чётного натурального числа n называется представление его в виде суммы р слагаемых n = ∑ p i =1 d i такое, что существует граф с р вершинами, степени которых равны d 1 ,...,d p . В графов теории известен эффективный алгоритм, позволяющий для данного упорядоченного набора чисел (d 1 ,...,d p) определить, существует ли граф с р вершинами v 1 ,...,v p , для которых последовательность степеней (d(v 1), ..., d(v p)) совпадает с этим набором. Подробно изучено другое важное структурное свойство - связность графа, а также вопросы, относящиеся к существованию в связном графе маршрутов определённого вида.

Специальным разделом структурной графов теории является факторизация графа, т. е. разложение графа G = (V, Е) на сумму факторов (подграфов) G 1 , ..., G m с некоторым заданным свойством, где G i = (V, Е i) и Е = Е 1 u...uЕ m - разбиение множества рёбер на непустые непересекающиеся подмножества. Наиболее распространённые виды факторизации: n-факторизация, где G i - однородные графы степени n (графы, степени всех вершин которых одинаковы и равны n), и древесная факторизация, где каждая компонента любого G i , i=1, ...,m, является деревом. Любой полный граф К 2 n , т. е. граф, в котором любые две вершины смежны, 1-факторизуем, но не 2-факторизуем; любой полный граф К 2 n+1 не является 1-факторизуемым, но представляется в виде суммы n факторов, являющихся циклами. Если при 1-факторизации речь идёт о возможности разбиения множества рёбер на подмножества, состоящие из попарно несмежных рёбер (при этом каждое из подмножеств есть 1-фактор), то всякое разбиение множества вершин графа на n подмножеств таких, что вершины из любых двух разных подмножеств попарно несмежны, определяет правильную раскраску графа в n цветов. Теория раскрасок графа возникла и развивалась в связи с четырёх красок задачей, которая получила решение лишь на рубеже 1970-80-х годов.

С графом G = (V, Е) естественно связывается целый ряд графов, например его подграфы, дополнительный граф, рёберный граф L(G). Рёберным для графа G с р вершинами и q рёбрами называется граф с множеством вершин Е, в котором две вершины соединены ребром тогда и только тогда, когда соответствующие рёбра смежны в G. Критерий того, что данный граф является рёберным графом, заключается в отсутствии у него подграфов, принадлежащих множеству из 9 конкретно указанных графов (с 4, 5 или 6 вершинами). Изучение специальных классов графов, выделяемых каким-либо определяющим признаком или структурным свойством, составляет одно из направлений теории графов.

Если граф задан бинарным отношением на множестве, то часто возникает вопрос о том или ином его конкретном представлении. Такого рода задачей является задача о планарности графа, т. е. о возможности представить его на плоскости рисунком, в котором нет пересечения рёбер. Наиболее известный критерий планарности даёт теорема Понтрягина - Куратовского: граф является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни полного графа К 5 , ни двудольного графа К 3,3 . Граф G = (V, Е) называется двудольным, если допускается разбиение вершин множества V на два подмножества V 1 и V 2 , состоящие из попарно несмежных вершин, такой граф обозначается K n1 , n2 , где n i - число вершин в подмножестве V i , i = 1, 2.

Значительная часть исследований в графов теории составляют перечислительные и экстремальные задачи. Отдельный класс экстремальных задач - задачи о покрытии. Основными объектами исследования в задачах о покрытии являются четыре важнейшие теоретико-графовые константы: число вершинного покрытия α 0 , число рёберного покрытия α 1 , вершинное число независимости β 0 и рёберное число независимости ß 1 . Число вершинного покрытия графа G есть минимальное число вершин в покрывающем множестве, т. е. в таком множестве вершин, для которого каждое ребро графа G инцидентно хотя бы одной вершине этого множества. Вершинное число независимости графа G есть наибольшее возможное число элементов в независимом множестве, т. е. в таком множестве вершин, в котором любые две вершины несмежны. Аналогично определяются число рёберного покрытия и рёберное число независимости. Для любого связного графа G с р > 1 вершинами α 0 + ß 0 = α 1 + ß 1 = р, а для двудольного графа ß 1 = α 0 . Значения этих констант известны лишь для некоторых графов частного вида. К задачам о покрытии тесно примыкает теория доминирования. В ней рассматриваются доминирующие множества графа G = (V, Е), то есть такие подмножества D с V, что любая вершина из VD смежна хотя бы с одной из вершин D. Важнейшей константой графа является число доминирования - наименьшее возможное число вершин в его доминирующем множестве.

Лит.: Кönig D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Берж К. Теория графов и ее применение. М., 1962; Зыков А. А. Теория конечных графов. Новосиб., 1969; Харари Ф. Теория графов. М., 1973; Басакер Р., Саати Т. Конечные графы и сети. М., 1974; Камерон П., Линт Д. Теория графов, теория кодирования и блок-схемы. М., 1980; Оре О. Теория графов. 2-е изд. М., 1980; Цветкович Д., Дуб М., Закс Х. Спектры графов. Теория и применение. К., 1984; Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М., 2000; Колчин В. Ф. Случайные графы. 2-е изд. М., 2004; Сачков В. Н. Введение в комбинаторные методы дискретной математики. 2-е изд. М., 2004.