Для чего нужны графы

Зачем студентам теория графов

Ранее я уже писал про приложения теории графов: тут и тут.

В этой статье хочу помочь коллеге в теории графов – он пожаловался в комментарии к своей статье, что:

Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф, и число — последовательность байт — граф, и файл — граф, не говоря о БД.

Дисклеймер. Далее хочу высказать свое сугубо личное мнение, никого ни в чем, не пытаясь убедить или переубедить. Исключительно в порядке обсуждения. Т.о. я адресуюсь к читателям, уже знакомым с теорией графов. Нижеследующее — всего лишь мои предположения. Иногда я опираюсь на факты и на авторитеты (Харари, Зыков, Вирт, Адельсон –Вельский и, как ни странно, А. Дюма), но это не повод тотально засадить всех студентов за зубрежку теории графов в полном объеме.

Вернемся к историкам. Предположим, что ими собрано достаточно документов о том, что у Хуана и Хуаниты, после того, как они сочетались законным браком, было пять детей. Но Хуанита изменяла Хуану и двоих родила внебрачно. А Хуан не остался в долгу и трижды изменил Хуаните – еще двое детей. Однако вопрос: от кого из любовников родила Хуанита?: От Филиппа или от кардинала Ришелье? А может от кого-то из четырех мушкетеров – он была общительной женщиной. Такой вопрос и про Хуана: он был знаком и пользовался расположением королевы Франции, но уделял внимание и ее дамам. (А. Дюма на многих сотнях страниц описывает подобные истории).

Как видим из этого модельного примера — граф (фамильное дерево) можно описать на естественном языке. Но для наглядности его лучше нарисовать, а как будет лучше?
Можно так:

Где черные ребра – документально подтвержденные факты, а красные – предположения.
А можно так:

Где красные ребра имеют надпись: «+любовница 1 или + любовница 2 или + любовница 3», т.е. предположения.
Синие и зеленые ребра имеют надпись: «+Хуанита», но синие — документально подтвержденные факты, а зеленые – предположения.

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

Цикл – это путь начало, которого и конец, которого в одной и той же вершине.

Это цикл:

И это цикл:

Дерево – это граф без циклов.
Пример:

Линейный список – дерево без ветвей. Т.е. только предыдущий элемент списка всегда инцидентен следующему и никакой другой.

Пример:
т-о-л-ь-к-о- -п-р-е-д-ы-д-у-щ-и-й- -э-л-е-м-е-н-т- -с-п-и-с-к-а- -в-с-е-г-д-а- -и-н-ц-и-д-е-н-т-е-н- -с-л-е-д-у-ю-щ-е-м-у

Здесь буквы и пробел – вершины графа, а дефис “-” обозначает ребро.

Г.М. Адельсон-Вельский доказал, что время поиска по дереву зависит от высоты этого дерева. (Н.Вирт в своей знаменитой книге “Алгоритмы + структуры данных = программы” ссылается на эту работу.) Из доказательства Адельсона-Вельского следует, что наихудший случай для дерева – вырождение в линейный список, и, следовательно, превращение списка в достаточно развесистое дерево ускорит поиск.

Для иллюстрации возьмем рекурсивное определение Вирта бинарного дерева.

Рекурсивная процедура сортировки будет такая:

Функция поиска в дереве:

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

Для гуманитариев может и не нужно вникать в приведенный код. Им важно понять, что список:

Аня
Ваня
Иван Васильевич
и т.д.

не всегда оптимальное решение. Не смогут сами — попросят помочь.

Я (с коллегами) продемонстрировал быстрый поиск при размерности ок.100 лимонов химических соединений (не все реально полученные – некоторые гипотетические). Тут мы встречаемся с важной задачей теории графов – задачей установления изоморфизма двух графов.

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

Пример не похожих рисунков:

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

И этот кунеан на другом рисунке:

Математически в общем случае задача изоморфизма сводится к поиску матрицы перестановки такой, чтобы
A₁= TA₂P,
где A₁ – матрица смежности первого графа;
A₂ – матрица смежности второго графа;
P — матрица перестановки;
T – обратная ( = транспонированная, для данного случая) матрица перестановки.

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

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

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

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

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

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

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

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

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

Для чего нужны графы

Код баннера:

Исследовательские работы и проекты

Применение графов в различных областях жизни людей

Глава 2. Возможности применения теории графов в различных областях повседневной жизни

2.1. Применение графов в различных областях жизни людей

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

1. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов».

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

2. Лабиринт.

Исследовать лабиринт — это найти путь в этом графе.

Вершинами здесь обозначены тупики, а отрезками – проходы лабиринта. (приложение 1, рис. 2)

3. Генеалогическое древо.

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

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

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

4. Блок-схема программы

Графами являются блок – схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.

5. Схема цепей дежурного освещения

Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.

6. Схемы авиалиний

Схемы авиалиний представлены в виде графов.

7. Участок московского Метрополитена.

Один из участков московского Метрополитена.

Он нарисован тоже в виде графа.

8. Социограммы

Социограммы (в психологии при исследовании межличностных отношений в группах).

Она тоже представлена с помощью графа.

9. Схема железных дорог

Схема железных дорог.

Вершины – железнодорожные станции, а рёбра – железнодорожные пути.

10. Созвездия

Графы есть и на картах звездного неба.

(приложение 1 рис.10).

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

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

12. Математика. Немало поводов для появления графов и в математике. Наиболее очевидный пример – любой многогранник в трёхмерном пространстве.

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

Еще один способ образования графов из геометрических объектов иллюстрирует рисунком 12. Слева показаны шесть кругов на плоскости, а справа — граф, в котором каждая вершина соответствует одному из этих кругов и две вершины соединены ребром.

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

13. Физика. Одной из наиболее сложных и утомительных задач для радиолюбителей считается конструирование печатных схем.

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

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

Теория графов в кратком и практичном изложении

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

Несмотря на то, что область теории графов глубока и увлекательна, данная статья включит в себя следующие общие разделы, касающиеся именно программистов:

• Мышление на основе графов/узлов и подходы к решению задач поиска.
• Реализация графа с помощью ООП.
• Различные представления графов: списки и матрицы смежности.
• Типы графов и их реализации: (не)ориентированные, (не)взвешенные графы, а также (а)циклические графы.
• Алгоритм Дейкстры, его слабые места и альтернативы.
• Области применения теории графов.
• Ключевые моменты.

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

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

У вас имеется висячий замок с двумя колесиками, на которых изображены цифры, инициализированные как 00. Каждым движением вы можете прокручивать одно из колесиков вверх или вниз на один шаг. Поскольку они круглые, то при прокрутке 0 вверх получаем 1, а при прокрутке вниз — 9. Существуют “мертвые комбинации”, набрав значение которых, мы заблокируем замок навсегда. Нужно найти минимальное число движений, необходимых для достижения целевой комбинации, не заблокировав замок, если такое вообще возможно.

Мертвые комбинации: [10, 90, 12], целевая: 11.

Сначала мы создаем “корень” или “голову” графа, которые необходимы в сценариях, где нам нужно генерировать граф по мере продвижения. Им будет ‘00’, иначе называемый корневым кейсом, от которого пойдет дальнейшее ветвление.

Четырьмя соседями узла ‘00’ будут ‘01’, ‘10’, ‘90’ и ‘09’, соответствующие различным комбинациям перемещаемых вверх и вниз колесиков. Теперь в нашем графе есть уже пять узлов и четыре ребра.

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

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

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

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

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

Например, каждый элемент приведенного ниже графа можно представить в коде как отдельный Node . Все они соединены друг с другом через своих Neighbors (соседей). Если мы вызовем, например, NodeA.Neighbors[1].Neighbors[1].Value , то в ответ получим 2. Так произойдет, потому что второй индекс соседей Node A — это Node C, а второй индекс соседей Node C — это Node B, чье значение 2. Такой вид простой связи позволяет легко выполнять обход графа.

Направленный граф или граф, в котором ребра идут только в одном направлении, легко реализовать с помощью такого построения. Например, если однонаправленное ребро будет соединять Node A с Node B, соседом Node A будет Node B, но у самого Node B соседей не будет. Иначе говоря, соседи указывают только на исходящие ребра. При этом в направленном графе по-прежнему могут присутствовать узлы с двунаправленными ребрами.

Если поставить задачу обойти граф по соседям и закончить в Node С или Node F, то мы застрянем, потому что у этих узлов нет соседей, а значит и исходящих направлений.

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

В этом примере v объявляет существующие узлы, а E объявляет ребро, ведущее от одного узла к другому ( AC означает A → C ). Поскольку это компактная и простая нотация, графы зачастую представляют именно таким способом.

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

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

Например, внутри завершенного циклического графа A→B→C→D→A является четырехцикловым графом, а E→F→G→E трехцикловым. Менее очевидным будет другой четырехцикловый граф B→E→F→G→B.

Конкретные виды циклов внутри циклических графов или другие компоненты внутри графов, в которых каждый узел соединен с каждым другим узлом, называются компонентой сильной связности. Например, E→F→G→E — это компонента сильной связности, потому что каждый из узлов [E, F, G> имеет путь к другому независимо от направления. B→E→F→G→B также является сильно связанной компонентой. С другой стороны, A→B→C→D→A не является таковым, потому что в нем нет связи между компонентами B и D.

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

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

Как вариант кратчайшим путем от S→E будет S→D→F→E, для чего потребуется пройти всего три ребра. Тем не менее этот маршрут пролегает по очень узенькой и людной улице. В качестве альтернативы можно рассмотреть путь S→A→B→C→E, который проходит уже через четыре ребра, но большая часть пути представлена шоссе, и итоговые затраты снижены. Когда в граф добавляются примечания расстояния и затрат, он становится взвешенным.

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

Зачастую графы будут также представлены в виде матрицы, известной как “матрица смежности”. Она уже не так компактна, как список смежности, но может представлять взвешенные графы более естественно. В матрице каждый ряд и столбец представляют узел, а ячейка, расположенная в (x, y), представляет ребро y→x (или наоборот, все зависит от нотации). Если ребра нет, значением будет 0. Если есть, значение будет представлять затраты этого ребра.

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

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

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

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

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

Рассмотрите в качестве примера сеть узлов, где обход каждой связи подразумевает одинаковые затраты. Алгоритм Дейкстры, имеющий небольшие вариации в зависимости от реализации, будет производить поиск по всем легким узлам, пока не достигнет конечного узла E . Это все равно, что вылить ведро воды в месте расположения узла S в надежде, что в итоге она достигнет целевого узла.

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

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

Для чего нужны графы

• Главная
• ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ

ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ

Автор работы награжден дипломом победителя II степени

«В математике следует помнить не формулы, а процесс мышления…»

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

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

Цель определила следующие задачи:

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

изучить основные понятия теории графов и основные характеристики графов;

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

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

Объект исследования: сфера деятельности человека на предмет применения метода графов.

Предмет исследования: раздел математики «Теория графов».

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

Методы исследовательской работы:

В ходе нашего исследования были использованы такие методы, как:

1) Работа с различными источниками информации.

2) Описание, сбор, систематизация материала.

3) Наблюдение, анализ и сравнение.

4) Составление задач.

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

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

ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ

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

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

В математике определение графа дается так:

Термин «граф» в математике определяется следующим образом:

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

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

Схема Санкт-Петербургского метро

Рис. 1 Примеры графов

Число ребер, которое принадлежит одной вершине, называется степенью вершины графа. Если степень вершины нечетное число, вершина называется – нечетной. Если степень вершины число четное, то и вершина называется четной.

Рис. 2 Вершина графа

Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами.

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

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

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

Если граф связанный, но не содержит циклов, то такой граф называетсядеревом.

Характеристики графов

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

Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.

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

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

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

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

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

Только в 1879 году данная задача была опубликована в первом томе «Трудов Королевского географического общества» известным английским математиком Артуром Кэли. Так она получила широкую известность.

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

В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».

Можно представить задачу о четырех красках несколько иначе.

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

Эйлеровы и Гамильтоновы графы

В 1859 году английским математиком Уильямом Гамильтоном была выпущена в продажу головоломка – деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира – Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики.

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

На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.

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

При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.

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

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

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

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

Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом. Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.