Для чего нужны графы
Для чего нужны графы
Исследовательские работы и проекты
Применение графов в различных областях жизни людей
Глава 2. Возможности применения теории графов в различных областях повседневной жизни
2.1. Применение графов в различных областях жизни людей
Как уже было сказано, графы имеют очень широкое применение: с их помощью выбирают наиболее выгодное расположение зданий, графами представлены схемы метро. Далее представлены некоторые примеры применения графов.
1. Можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов». 
Здесь позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки. (приложение 1, рис.1)
Вершинами здесь обозначены тупики, а отрезками – проходы лабиринта. (приложение 1, рис. 2)
3. Генеалогическое древо. 
Граф иерархической системы называется деревом. Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.
Обычно у дерева, представляющего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. Каждая вершина дерева (кроме корня) имеет только одного предка – обозначенный ею объект входит в один класс верхнего уровня.
Для каждой пары вершин дерева существует единственный путь, их соединяющий. Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов. (приложение 1 рис.3).
4. Блок-схема программы 
Графами являются блок – схемы программ для ЭВМ, а так же любые электрические цепи или электрическая сеть.
5. Схема цепей дежурного освещения 
Схема цепей дежурного освещения тепловоза ТЭМ2 тоже представлена в виде графа.
6. Схемы авиалиний 
Схемы авиалиний представлены в виде графов.
Он нарисован тоже в виде графа.
8. Социограммы 
Социограммы (в психологии при исследовании межличностных отношений в группах).
Она тоже представлена с помощью графа.
9. Схема железных дорог 
Схема железных дорог.
Вершины – железнодорожные станции, а рёбра – железнодорожные пути.
10. Созвездия 
Графы есть и на картах звездного неба.
(приложение 1 рис.10).
11. Химия. Теория графов позволяет точно определить и пояснить некоторые основные понятия химии: структуру, конфигурацию, конформацию, квантовомеханическое и статистико-механическое взаимодействия молекул, определять число теоретически возможных изомеров органических соединений, позволяет анализировать некоторые химические превращения, описывать химические реакции, определять некоторые свойства молекул.
12. Математика. Немало поводов для появления графов и в математике. Наиболее очевидный пример – любой многогранник в трёхмерном пространстве.
Так же графы под другими названиями проникли в учебники химии, биологии, географии, где они использованы для наглядного и экономного описания различных схем организаций, логических возможностей, классификаций, в том и только том случае, когда соответствующие круги пересекаются.
13. Физика. Одной из наиболее сложных и утомительных задач для радиолюбителей считается конструирование печатных схем.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного исследования.
Зачем студентам теория графов
Ранее я уже писал про приложения теории графов: тут и тут.
В этой статье хочу помочь коллеге в теории графов – он пожаловался в комментарии к своей статье, что:
Здесь я попытался в максимально доступной форме объяснить, как же это делать. И в первую очередь я делаю это для студентов, которые изучают данную тему и могут не понимать, зачем вообще графы нужны. Учась, я лично убедился, что для многих эта тема была «проходной» и они не извлекли из нее никакой ценной информации, а также так и не поняли, как работать с матрицами.
ИМХО для IT-студентов нужно сразу сказать, что списки (стеки, очереди) и бинарные деревья это графы. И всякие схемы, типа схемы метро, автодорог, принципиальные в электронике можно рассматривать как графы. Приложения теории графов — это фундаментальные свойства всяких подобных схем.
Для студентов историков м.б. будет полезно узнать, что фамильные деревья — это графы. И проч. др. специальности. Где только нет графов, пусть на уровне тривиального списка. Возвращаясь к IT: строка символов — граф, и число — последовательность байт — граф, и файл — граф, не говоря о БД.
Дисклеймер. Далее хочу высказать свое сугубо личное мнение, никого ни в чем, не пытаясь убедить или переубедить. Исключительно в порядке обсуждения. Т.о. я адресуюсь к читателям, уже знакомым с теорией графов. Нижеследующее — всего лишь мои предположения. Иногда я опираюсь на факты и на авторитеты (Харари, Зыков, Вирт, Адельсон –Вельский и, как ни странно, А. Дюма), но это не повод тотально засадить всех студентов за зубрежку теории графов в полном объеме.
Вернемся к историкам. Предположим, что ими собрано достаточно документов о том, что у Хуана и Хуаниты, после того, как они сочетались законным браком, было пять детей. Но Хуанита изменяла Хуану и двоих родила внебрачно. А Хуан не остался в долгу и трижды изменил Хуаните – еще двое детей. Однако вопрос: от кого из любовников родила Хуанита?: От Филиппа или от кардинала Ришелье? А может от кого-то из четырех мушкетеров – он была общительной женщиной. Такой вопрос и про Хуана: он был знаком и пользовался расположением королевы Франции, но уделял внимание и ее дамам. (А. Дюма на многих сотнях страниц описывает подобные истории).
Как видим из этого модельного примера — граф (фамильное дерево) можно описать на естественном языке. Но для наглядности его лучше нарисовать, а как будет лучше?
Можно так: 
Где черные ребра – документально подтвержденные факты, а красные – предположения.
А можно так: 
Где красные ребра имеют надпись: «+любовница 1 или + любовница 2 или + любовница 3», т.е. предположения.
Синие и зеленые ребра имеют надпись: «+Хуанита», но синие — документально подтвержденные факты, а зеленые – предположения.
Путь — это результат обхода некоторых вершин графа по правилу: переходить можно только на вершну инцидентную (т.е. связанную ребром) текущей вершине. При этом нельзя возвращаться по уже пройденному ребру.
Цикл – это путь начало, которого и конец, которого в одной и той же вершине.
Это цикл: 
И это цикл: 
Дерево – это граф без циклов.
Пример: 
Линейный список – дерево без ветвей. Т.е. только предыдущий элемент списка всегда инцидентен следующему и никакой другой.
Здесь буквы и пробел – вершины графа, а дефис “-” обозначает ребро.
Г.М. Адельсон-Вельский доказал, что время поиска по дереву зависит от высоты этого дерева. (Н.Вирт в своей знаменитой книге “Алгоритмы + структуры данных = программы” ссылается на эту работу.) Из доказательства Адельсона-Вельского следует, что наихудший случай для дерева – вырождение в линейный список, и, следовательно, превращение списка в достаточно развесистое дерево ускорит поиск.
Для иллюстрации возьмем рекурсивное определение Вирта бинарного дерева.
Рекурсивная процедура сортировки будет такая:
Функция поиска в дереве:
Как сделать развесистое дерево из отсортированного списка – отдельная проблема. Может добавлять в дерево случайным образом, а может использовать алгоритмы балансировки деревьев.
Для гуманитариев может и не нужно вникать в приведенный код. Им важно понять, что список:
Аня
Ваня
Иван Васильевич
и т.д.
не всегда оптимальное решение. Не смогут сами — попросят помочь.
Я (с коллегами) продемонстрировал быстрый поиск при размерности ок.100 лимонов химических соединений (не все реально полученные – некоторые гипотетические). Тут мы встречаемся с важной задачей теории графов – задачей установления изоморфизма двух графов.
Классическая теория графов смотрит только на топологию: какая вершина с какой связаны ребром, а геометрию рисунка не учитывает. Такой подход оказался продуктивным для обобщений и теорем. Но проблема в том, что на листе бумаги мы можем произвольно отметить n точек или кружочков по числу вершин графа, произвольно пронумеровать эти вершины и соединить их линиями, обозначающими ребра. Рисунки одного и того же графа не обязательно совпадут в своей геометрии.
Пример не похожих рисунков:
Кубан – кунеан. Это химическая реакция перехода химического вещества кубан в вещество кунеан. Можно видеть, что структурные формулы органической химии не отличаются от графов.
И этот кунеан на другом рисунке:
Математически в общем случае задача изоморфизма сводится к поиску матрицы перестановки такой, чтобы
A1= TA2P,
где A1 – матрица смежности первого графа;
A2 – матрица смежности второго графа;
P — матрица перестановки;
T – обратная ( = транспонированная, для данного случая) матрица перестановки.
На словах понятно, что если удается найти для второго графа такую нумерацию, что смежность вершин совпадает с первым (говорят “найти биекцию” — см. Википедию)
к примеру, если в одном графе есть ребро между первой и второй вершинами и в другом графе такое ребро, и так для всех ребер, то графы изоморфны – фактически это один и тот же граф.
Нужно отметить, что для некоторых типов графов задача изоморфизма решается тривиально, для других легко, но для многих требует перебора со сложностью в экспоненту. Тривиально для полных графов – это графы, у которых каждая вершина связана со всеми остальными (инцидентна всем остальным). Понятно, что для любых n вершин существует только один полный граф. Поэтому проверка на изоморфизм сводится к проверке равенства числа вершин первого графа = числу вершин второго. Аналогично для безреберного графа (где только вершины).
Легко задача изоморфизма решается для случая, когда у всех вершин разные степени. Т.к. степени уникальны, то вычисление матрицы перестановки не требуется – простая перенумерация. Каждому номеру вершины второго графа присваиваете номер вершины первого той же степени и проверяете совпадение ребер.
Но не у всех графов степени вершин уникальны. Тут появляются идеи канонической нумерации, т.е. нумерации вершин по жестким однозначным правилам, и полного инварианта графа. Инвариант это обычно (но не обязательно) число, которое не меняется от перенумерации вершин графа. Примером инварианта может служить сумма степеней вершин.
Очевидно, что у двух неизоморфных графов эти инварианты могут совпадать. (Если инварианты не совпадают, то графы точно не изоморфны).
Полные инварианты это, которые, если равны, то графы изоморфны, а если не равны, то не изоморфны. Один из полных инвариантов описан у Зыкова. Матрицу смежности можно развернуть в вектор – нужно просто добавлять в вектор строку за строкой из матрицы. Этот вектор можно рассмотреть, как двоичное число. Можно перебрав все матрицы найти минимальное и максимальное числа. Далее если такие минимальные (или максимальные) числа для двух графов совпадают, то, очевидно, что их матрицы смежности после перестановки будут равны и графы будут изоморфны. К настоящему времени не известен ни один полный инвариант, который можно вычислить без перебора.
Отметим, что изоморфизм деревьев определяется (без полного перебора) с полиномиальной сложностью. А проблема изоморфизма графов остается по-прежнему открытой.
Выше мы затронули проблему отрисовки графов или, как говорят, визуализации. Было предложено много способов (я может, раскачаюсь написать про наиболее полезные), но ни один из них не универсальный. И поэтому графы все рисуют по разному и люди и компьютеры. Я рисую на сделанном мной инструменте.
Возвращаясь к студентам, с которых начал. Думаю, что каждый понимает, что в избранной им области есть структуры. Иногда очень сложные, иногда не очень. Надеюсь мне удалось показать, что теория графов – это теория структур, и учит общим методам обращения со структурами. Может не всем студентам нужно углубляться в эти методы, но понимание общих принципов полезно всем. При этом я не призываю грузить студентов-философов матричной алгеброй – им и так хватает, им положено Платона с Аристотелем читать. Но обзорные лекции будет полезно прослушать со сдачей не сложного зачета, чтобы не прогуливали.
В начале я сказал, что хочу высказать свое сугубо личное мнение, никого не в чем не пытаясь убедить или переубедить. Исключительно в порядке обсуждения. Надеюсь на интересное обсуждение, которое обещает мне много новых знаний о преподавании теории графов для различных специальностей, и о пользе этой теории для этих специальностей.
Теория графов. Основные понятия и виды графов
Статья находится на проверке у методистов Skysmart.
Если вы заметили ошибку, сообщите об этом в онлайн-чат
(в правом нижнем углу экрана).
Теория графов
В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.
Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.
Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Давайте на примере.
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
В данном случае точки — это вершины графа, а связки — рёбра графа.
Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.
Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.
Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.
Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.
Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.
Широкое применение теории графов в компьютерных науках и информационных технологиях можно объяснить понятием графа как структуры данных. В компьютерных науках и информационных технологиях граф можно описать, как нелинейную структуру данных.
Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.
Курсы обучения математике помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.
Основные понятия теории графов
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Доказательство леммы о рукопожатиях
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.
Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.
Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
Путь и цепь в графе
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Два графа называются изоморфными, если у них поровну вершин. При этом вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие занумерованные теми же числами вершины второго графа.
Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.
Визуализация графовых моделей
Визуализация — это процесс преобразования больших и сложных видов абстрактной информации в интуитивно-понятную визуальную форму. Другими словами, когда мы рисуем то, что нам непонятно — и сразу все встает на свои места.
Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.
Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.
Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.
Виды изобразительных соглашений:
Виды графов
Виды графов можно определять по тому, как их построили или по свойствам вершин или ребер.
Ориентированные и неориентированные графы
Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.
Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы
Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».
Смешанным называют граф, в котором есть ребра хотя бы двух из упомянутых трех разновидностей (звенья, дуги, петли).
Пустой граф — это тот, что состоит только из голых вершин.
Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.
Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.
Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.
Двудольный граф
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.
Эйлеров граф
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?
Регулярный граф
Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.
Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.
Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.
Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.
Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:
Гамильтонов граф
Гамильтоновым графом называется граф, содержащий гамильтонов цикл.
Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.
Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.
Определение дерева
Деревом называется связный граф, который не содержит циклов.
Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.
Циклом называется замкнутый путь, который не проходит дважды через одну и ту же вершину.
Простым путем называется путь, в котором никакое ребро не встречается дважды.
Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:
Дерево — минимальный по числу рёбер связный граф.
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Определения дерева:
Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.
Когда изображают деревья, то часто применяют дополнительные соглашения, эстетические критерии и ограничения.
Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:
Теоремы дерева и их доказательства
В дереве с более чем одной вершиной есть висячая вершина.
Доказательство первой теоремы:
Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.
Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.
В дереве число вершин на 1 больше числа ребер.
Доказательство второй теоремы:
Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n
