Теория графов - один из обширнейших разделов дискретной математики, широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, психологии, социологии, лингвистике, других областях знаний. Теория графов систематически и последовательно изучает свойства графов, о которых можно сказать, что они состоят из множеств точек и множеств линий, отображающих связи между этими точками. Основателем теории графов считается Леонард Эйлер (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 году великий математик Леонард Эйлер нашел решение головоломки, носящей название «Проблема кёнигсбергских мостов». Река Прегель, протекающая через Калининград (прежде город назывался Кенигсбергом) омывает два острова (рис. Рисунок 1Рисунок 1). Берега реки с островами были во времена Эйлера связаны мостами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем четырем участкам суши по одному разу, а конец и начало пути должны совпадать.

Рисунок 1

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

Рисунок 2

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

Спустя сто с лишним лет, в 1874 году немецкий ученый Г. Кирхгоф разработал эффективную методику определения значения силы тока в электрической цепи, используя методы и понятия, получившие позднее права гражданства в теории графов. Еще 10 лет спустя английский математик А. Кели (мать его была русской, он владел русским языком и следил за русской математической литературой; он оказался среди тех немногих математиков, которые с самого начала поняли и поддержали идеи Н.И. Лобачевского) разработал теорию деревьев для подсчета числа изомеров насыщенных углеводородов с данным числом n атомов углерода.

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

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

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

Рисунок 3

Граф на рис.Рисунок 3 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф, на котором легко увидеть возможные маршруты. Вершина М вверху- начало маршрутов. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4321  24 способа.

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

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G 1 (рис.Рисунок 4).

Рисунок 4

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

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

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

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

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

Задача 1. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?

Приведем подробное решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому вначале должен возникнуть граф, изображенный на рисунке Рисунок 5.

Рисунок 5

Из условия задачи следует, что для каждой точки из множества М существует одна и только одна тонка из множеств К, которая соответствует первой и, наобо­рот, каждой точке из множества К соответствует одна и только одна точка из множества М. Задача сводится к тому, чтобы найти это единственно возможное соответствие междуэлементами множеств М и К, т. е. к нахождению трех сплошных линий, соединяющих со­ответствующие точки множеств.

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

Рисунок 7

Таким образом, на графе этого рисунка автоматически прочитываем ответ: Белокуров - рыжий, Чернов - белокурый, Ры­жов – брюнет. Таким же приемом решаются, например, задачи 2 и 3.

Задача 2. Для Вани, Коли и Миши испечены пи­роги: один с капустой, другой с рисом, третий – с яблоками. Миша не любит пирог с яблоками и не ест с капустой. Ваня не любит пирог с капустой. Кто какой пирог ест?

Задача 3. На одном заводе работают три друга: слесарь, токарь и сварщик. Их фамилии Борисов, Ива­нов и Семенов. У слесаря нет ни братьев, ни сестер, он самый младший из друзей. Семенов, женатый на сестре Борисова, старше токаря. Назовите фамилии сле­саря, токаря и сварщика.

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

Задача 4. Три товарища – Иван, Дмитрий и Степан – преподают различные предметы (химию, биологию, физику) в школах Москвы, Ленинграда и Киева. Известно:

1. Иван работает не в Москве, а Дмитрий не в Ленинграде;

2. Москвич преподает не физику;

3. Тот, кто работает в Ленинграде, преподает химию;

4. Дмитрий преподает не биологию.

Какой предмет и в каком городе преподает каждый из товарищей?

Решение. Выделим три множества: множество имен, множество предметов и множество городов. Эле­мент каждого из множеств на рисунке 4 задан своей точкой (буквы на этом рисунке - первые буквы соот­ветствующих слов). Если две точки из разных множеств характеризуют признаки разных людей, то будем сое­динять такие точки штриховой линией. Если же две точки из разных множеств соответствуют признакам одного человека, то такие точки будем соединять попар­но сплошными линиями. Существенно, что по условию задачи для каждой точки любого множества в каждом из остальных множеств найдется одна и только одна точка, ей соответствующая.

Рисунок 8

Таким образом, граф на рисунке 8 содержит все заданные в условии элементы множеств и отношения между ними. Задача на языке графов сводится к нахождению трех «сплошных» тре­угольников с вершинами в разных множествах.

Рассмотрим граф на рисунке 8. Напрашивается штри­ховой отрезок ХД, Действительно, Л соответствует X и, одновременно, Л не соответствует Д, т. е. X не может соответствовать Д. Итак, используется типичная для такого рода задач операция на графе: если у тре­угольника с вершинами в трех разных множествах одна сторона сплошная, вторая - штриховая, то третья должна быть штриховой. Из условия задачи следует равномерность еще одной операции на графе: если какая-то точка соединена штриховыми отрезками с двумя точками во втором множестве, то ее следует со­единить с третьей точкой этого множества сплош­ным отрезком. Так проводится сплошной отрезок ДФ. Далее проводится штриховой отрезок ДМ (в тре­угольнике ДФМ сторона ДФ сплошная, а ФМ - штри­ховая), ДК сплошным (ДМ и ДЛ штриховые), Теперь соединим точки Ф и К сплошным отрезком. Если в треугольнике с вершинами в разных множествах две стороны сплошные, то третья тоже будет сплошной. Найден первый «сплошной» треугольник ДФК. Так, не возвращаясь к тексту задачи, руководствуясь лишь естественными операциями на графе, описанными выше, мы находим решение (рис. 9).

Рисунок 9

Отметим последователь­ность, в которой проводились отрезки: ХД, ДФ, ДМ, ДК, ФК, МС, ИЛ, ХИ, БМ, БС. Вершины каждого из трех полученных «сплошных» треугольников определяют ответ задачи: Иван преподает химию в Ленинграде, Дмитрий - физику в Киеве и Степан - биологию в Москве.

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

Задача 5. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке], но каждая только на одном. Они же владеют разными иностранными языками (английским, француз­ским, немецким и испанским), но каждая только одним. Известно:

1. девушка, которая играет на гитаре, говорит по-испански;

2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;

3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;

4. девушка, которая говорит по-немецки, не играет на виолончели;

5. Женя знает французский язык, но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

Условию задачи соответствует граф, изображенный на рисунке 10.

Рисунок 10

Обозначения и принцип решения здесь такие же, как и в задаче 4. Проведем последовательно следующие сплошные отрезки: КС, ВЖ, ВФ, АК (рис.11).

Рисунок 11

Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечи­вают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.

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

Задача 6. В шахматном турнире принимали уча­стие 6 партнеров разных профессий: токарь, слесарь, инженер, учитель, врач и шофер. Известно:

1. в первом туре Андреев играл с врачом, учитель с Борисовым, а Григорьев с Евдокимовым;

2. во втором туре Дмитриев играл с токарем, а врач с Борисовым;

3. в третьем туре Евдокимов играл с инженером;

4. по окончании турнира места распределились так - Борисов I место, Григорьев и инженер поделили II и III места, Дмитриев занял IV Место, а Золотарев и слесарь поделили пятое и шестое места.

Какие профессии имели Григорьев, Дмитриев и Евдо­кимов?

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:

Правило Эйлера:

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

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

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

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

Сформулированная в середине 19 в. проблема четырех красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: Верно ли, что хроматическое число любого плоского графа меньше либо равно четырёх? Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ.

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

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

История возникновения теории графов. 1

Правило Эйлера. 1

Литература

1. Белов Теория Графов, Москва, «Наука», 1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат , 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука , 1990.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ , 1992.

6. Оре О. Теория графов. – М.: Наука , 1980.

7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика

1736 год, г.Кёнигсберг. Через город протекает река Прегеля. В городе - семь мостов, расположенных так, как показано на рисунке выше. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.

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

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

Виды графов:

1. Ориентированный граф (кратко орграф ) - рёбрам которого присвоено направление.

2. Неориентированный граф - это граф , в котором нет направления линий.

3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).

Решение задач с помощью графов:

Задача 1.

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

Задача 2.

На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Решение:

Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.

Задача 3.

У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо?

Решение:

Ниже представлен разбор задач.

Учебное издание

Ююкин Николай Алексеевич

ЛР № . Подписано в печать

Уч. Изд. л.. , .

Воронежский государственный технический университет

394026 Воронеж, Московский просп. 14

СПРАВОЧНИК МАГНИТНОГО ДИСКА

Кафедра высшей математики и физико-математического моделирования

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Воронеж 2004

ВВЕДЕНИЕ

Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;

090106 - Информационная безопасность телекоммуникационных систем.

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

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

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

в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла

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

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

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

Достижению данной цели служат следующие задачи:

изучить максимально широкий круг понятий теории графов;

получить навыки решения учебных и практических задач;

овладеть методами оптимизации;

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

Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении общепрофессиональных и специальных дисциплин.

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

1.1. Задачи теории графов.

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

Первые задачи теории графов были связаны с решением развлекательных задач и головоломок.

Первая задача . Задача о Кенигсбергских мостах была поставлена и решена Эйлером в 1786 году. Город располагался на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами, как показано на рисунке.

Возникал вопрос: можно ли выйдя из дома, вернуться обратно, проходя по каждому мосту ровно один раз?

Вторая задача . Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

Требуется провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Задача была

решена Понтрягиным и независимо от него Куратовским в

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

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

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

Графом G= (V,E ) называется совокупность двух множеств - непустого множества вершин V и множества неупорядоченных и упорядоченных пар вершин E . В дальнейшем будут рассматриваться конечные графы , т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называется ребром , а упорядоченная - дугой .

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

ственны геометрические свойства ребер (длина, кривизна), а также взаимное расположение вершин на плоскости.

Вершины, которые не принадлежат ни одному ребру (дуге) называются изолированными. Вершины, соединенные ребром или дугой называются смежными . Ребро (дуга) и любая из его двух вершин называются инцидентными .

Говорят, что ребро (u,v ) соединяет вершины u и v , а дуга (u,v) начинается в вершине u и заканчивается в вершине v , при этом u называется началом , а v – концом этой дуги.

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

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

Граф, состоящий из одной изолированной вершины (K 1 ), называется тривиальным .

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

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

1.3. Степени вершин графа.

Степенью (валентностью) (обозначение d (v ) или deg (v )) вершины v простого графа G называется число ребер или дуг инцидентных данной вершине v . При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равны k , то граф называется регулярным (однородным) степени k . Если степень вершины равна 0 , то она является изолированной . Если степень вершины равна 1 , то вершина называется концевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v назы-

вается полустепенью исхода										(v ), а входящих – полустепе-
нью захода d							(v ), При этом справедливо соотношение d (v )=
		(v )+			(v ).

Теорема Эйлера : Сумма степеней вершин графа равна

удвоенному количеству ребер, т.е.

d (vi )

			(v )

Где n – число вершин; m – число

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

1.4. Изоморфизм графов.

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

метками (номерами). Граф считается полностью заданным в строгом смысле , если нумерация его вершин и ребер фиксирована. При этом графы G 1 и G 2 называются равными (обозначение G 1 = G 2 ) , , если их множества вершин и ребер совпадают. Два графа или псевдографа G 1 = (V 1 ,E 1 ) и G 2 = (V 2 ,E 2 ) называют-

	изоморфными (обозначение G				если существуют
	взаимно однозначных отображения: 1)				: V 1 V 2
: E 1 E 2 такие, что для любых двух вершин u , v в графе
	справедливо соотношение ((u , v )) ((u ), (v )) .
	Два простых графа (без петель и кратных ребер) G 1					и G 2

оказываются изоморфными, если существуют взаимно одно-

значное отображение

: V 1 V 2

Такое что

(u , v ) ((u ), (v )) .

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

Рефлексивности -

G 1 ,

причем биекция

ставляет собой тождественную функцию.

Симметричности.

с биекцией

с биекцией

Транзитивности.

G 1 G 2

биекцией

1 ,а

с биекцией

то G G

с биекцией

2 (1 ) .