Теория графов. Термины и определения в картинках
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках.
Самый объёмный модуль на курсе «Алгоритмы и структуры данных» посвящён теории графов.
Граф — это топологичекая модель, которая состоит из множества вершин и множества соединяющих их рёбер. При этом значение имеет только сам факт, какая вершина с какой соединена.
Например, граф на рисунке состоит из 8 вершин и 8 рёбер.
Очень многие задачи могут быть решены используя богатую библиотеку алгоритмов теории графов. Для этого достаточно лишь принять объекты за вершины, а связь между ними — за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам: нахождение маршрута от одного объекта к другому, поиск связанных компонент, вычисление кратчайших путей, поиск сети максимального потока и многое другое.
В этой статье мы познакомимся с основными терминами и определениями теории графов. На курсе “Алгоритмы и Структуры данных” в компании Отус “Теория графов” изучается в самом объёмном модуле из 6 вебинаров, где мы изучаем десяток самых популярных алгоритмов.
Вершина — точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро — неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге — не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность — вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру.
Смежность вершин — две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер — два ребра называются смежными, если они инцедентны одной вершине.
Говоря проще — две вершины смежные, если они соединены ребром, два ребра смежные — если они соединены вершиной.
Петля — ребро, инцидентное одной вершине. Ребро, которое замыкается на одной вершине.
Псевдограф — граф с петлями. С такими графами не очень удобно работать, потому что переходя по петле мы остаёмся в той же самой вершине, поэтому у него есть своё название.
Кратные рёбра — рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.
Мультиграф — граф с кратными рёбрами.
Псевдомультиграф — граф с петлями и кратными рёбрами.
Степень вершины — это количество рёбер, инцидентных указанной вершине. По-другому — количество рёбер, исходящих из вершины. Петля увеливает степень вершины на 2.
Изолированная вершина — вершина с нулевой степенью.
Висячая вершина — вершина со степенью 1.
Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа.
Идея подграфов используется во многих алгоритмах, например, сначала создаётся подграф их всех вершин без рёбер, а потом дополняется выбранными рёбрами.
Полный граф — это граф, в котором каждые две вершины соединены одним ребром.
Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N — каждый новый участник должен пожать руку всем присутствующим. Сумму нужно разделить на два, так как в этом случае каждое рукопожатие посчитается дважды: N * (N — 1) / 2.
Регулярный граф — граф, в котором степени всех вершин одинаковые.
Двудольный граф — если все вершины графа можно разделить на два множества таким образом, что каждое ребро соединяет вершины из разных множеств, то такой граф называется двудольным. Например, клиент-серверное приложение содержит множество запросов (рёбер) между клиентом и сервером, но нет запросов внутри клиента или внутри сервера.
Планарный граф. Если граф можно разместить на плоскости таким образом, чтобы рёбра не пересекались, то он называется “планарным графом” или “плоским графом”.
Если это невозможно сделать, то граф называется “непланарным”.
Минимальные непланарные графы — это полный граф К5 из 5 вершин и полный двудольный граф К3,3 из 3+3 вершин (известная задача о 3 соседях и 3 колодцах). Если какой-либо граф в качестве подграфа содержит К5 или К3,3, то он является непланарным.
Путь или Маршрут — это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути — количество рёбер в пути.
Цепь — маршрут без повторяющихся рёбер.
Простая цепь — цепь без повторяющихся вершин.
Цикл или Контур — цепь, в котором последняя вершина совпадает с первой.
Длина цикла — количество рёбер в цикле.
Самый короткий цикл — это петля.
Цикл Эйлера — цикл, проходящий по каждому ребру ровно один раз. Эйлер доказал, что такой цикл существует тогда, и только тогда, когда все вершины в связанном графе имеют чётную степень.
Цикл Гамильтона — цикл, проходящий через все вершины графа по одному разу. Другими словами — это простой цикл, в который входят все вершины графа.
Взвешенный граф — граф, в котором у каждого ребра и/или каждой вершины есть “вес” — некоторое число, которое может обозначать длину пути, его стоимость и т. п. Для взвешенного графа составляются различные алгоритмы оптимизации, например поиск кратчайшего пути.
Пока ещё не придуман алгоритм, который за полиномиальное время нашёл бы кратчайший цикл Гамильтона в полном нагруженном графе, однако есть несколько приближённых алгоритмов, которые за приемлимое время находят если не кратчайший, то очень короткий цикл, эти алгоритмы мы также рассматриваем на курсе Отуса — “Алгоритмы и структуры данных”.
Связный граф — граф, в котором существует путь между любыми двумия вершинами.
Дерево — связный граф без циклов.
Между любыми двумя вершинами дерева существует единственный путь.
Деревья часто используются для организации иерархической структуры данных, например, при создании двоичных деревьев поиска или кучи, в этом случае одну вершину дерева называют корнем.
Лес — граф, в котором несколько деревьев.
Ориентированный граф или Орграф — граф, котором рёбра имеют направления.
Дуга — направленные рёбра в ориентированном графе.
Полустепень захода вершины — количество дуг, заходящих в эту вершину.
Исток — вершина с нулевой полустепенью захода.
Полустепень исхода вершины — количество дуг, исходящих из этой вершины
Сток — вершина с нулевой полустепенью исхода.
Компонента связности — множество таких вершин графа, что между любыми двумя вершинами существует маршрут.
Компонента сильной связности — максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам.
Компонента слабой связности — максимальное множество вершин орграфа, между любыми двумя вершинами которого существует путь по дугам без учёта направления (по дугам можно двигаться в любом направлении).
Мост — ребро, при удалении которого, количество связанных компонент графа увеличивается.
Это только основные термины и определения теории графов, которые мы рассматриваем на первом вебинаре модуля “Теория графов”. Цель статьи — дать наглядное и понятное представление об этих терминах, для чего и были нарисованы эти картинки.
Источник
Сущность теории графов область применения способ представления
ГРАФЫ И ОБЛАСТИ ИХ ПРИМЕНЕНИЯ
Автор работы награжден дипломом победителя II степени
«В математике следует помнить не формулы, а процесс мышления…»
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Поэтому тематика данной работы достаточно актуальна.
Цель исследовательской работы: выяснить особенности применения теории графов в различных областях знаний и при решении логических задач.
Цель определила следующие задачи:
познакомиться с историей теории графов;
изучить основные понятия теории графов и основные характеристики графов;
показать практическое применение теории графов в различных областях знаний;
рассмотреть способы решения задач с помощью графов и составить собственные задачи.
Объект исследования: сфера деятельности человека на предмет применения метода графов.
Предмет исследования: раздел математики «Теория графов».
Гипотеза. Мы предполагаем, что изучение теории графов может помочь учащимся решать логические задачи по математике, что определит их дальнейшие интересы.
Методы исследовательской работы:
В ходе нашего исследования были использованы такие методы, как:
1) Работа с различными источниками информации.
2) Описание, сбор, систематизация материала.
3) Наблюдение, анализ и сравнение.
4) Составление задач.
Новизна работы заключается в авторском составлении задач по теме исследования и нахождении практического использования теории графов в современном мире.
Теоретическая и практическая значимость данной работы определяется тем, что результаты могут быть использованы на информатике, математике, геометрии, черчении и классных часах, а также для широкого круга читателей, заинтересованных данной темой. Исследовательская работа имеет выраженную практическую направленность, так как в работе автором представлены многочисленные примеры применения графов во многих областях знаний, составлены свои задачи. Данный материал можно использовать на факультативных занятиях по математике.
ГЛАВА I. ТЕОРЕТИЧЕСКИЙ ОБЗОР МАТЕРИАЛА ПО ТЕМЕ ИССЛЕДОВАНИЯ
Теория графов. Основные понятия
В математике «граф» можно изобразить в виде картинки, которая представляет собой некоторое количество точек, соединенных линиями. «Граф» происходит от латинского слова «графио» – пишу, как и известный дворянский титул.
В математике определение графа дается так:
Термин «граф» в математике определяется следующим образом:
Граф– это конечное множество точек – вершин, которые могут быть соединены линиями – ребрами.
В качестве примеров графов могут выступать чертежи многоугольников, электросхемы, схематичное изображение авиалиний, метро, дорог и т.п. Генеалогическое дерево также является графом, где вершинами служат члены рода, а родственные связи выступают в качестве ребер графа.
Схема Санкт-Петербургского метро
Рис. 1 Примеры графов
Число ребер, которое принадлежит одной вершине, называется степенью вершины графа. Если степень вершины нечетное число, вершина называется – нечетной. Если степень вершины число четное, то и вершина называется четной.
Рис. 2 Вершина графа
Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами.
Полный граф – это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.
Если в графе выбрать такой путь, когда начальная и конечная точка совпадают, то такой путь называется циклом графа. Если прохождение через каждую вершину графа происходит не более одного раза, то цикл называется простым.
Если в графе каждые две вершины связаны ребром, то это связанный граф. Граф называется несвязанным, если в нем есть хотя бы одна пара несвязанных вершин.
Если граф связанный, но не содержит циклов, то такой граф называетсядеревом.
Характеристики графов
Путь графа– это такая последовательность, в которой каждые два соседних ребра, имеющих одну общую вершину, встречаются только один раз.
Длина кратчайшей цепи из вершин a и b называется расстоянием между вершинами a и b.
Вершина а называется центром графа, если расстояние между вершиной а и любой другой вершиной является наименьшим и из возможных. Такое расстояние есть радиус графа.
Максимально возможное расстояние между двумя любыми вершинами графа называется диаметром графа.
Раскраска графов и применение.
Если внимательно посмотреть на географическую карту, то можно увидеть железные или шоссейные дороги, которые являются графами. Кроме этого на катре есть граф, который состоит из границ между странами (районами, областями).
В 1852 году английскому студенту Френсису Гутри поставили задачу раскрасить карту Великобритани, выделив каждое графство отдельным цветом. Из-за небольшого выбора красок Гутри использовал их повторно. Он подбирал цвета так, чтобы те графства, которые имеют общий участок границы, обязательно окрашивались в разные цвета. Возник вопрос, какое наименьшее количество красок необходимо для раскрашивания различных карт. Френсис Гутри предположил, хотя и не смог доказать, что четырех цветов будет достаточно. Эта проблема бурно обсуждалась в студенческих кругах, но позже была забыта.
Только в 1879 году данная задача была опубликована в первом томе «Трудов Королевского географического общества» известным английским математиком Артуром Кэли. Так она получила широкую известность.
«Проблема четырех красок» вызывала все больший интерес, но так и не была решена, даже выдающимися математиками. В 1890 году английским математиком Перси Хивудом было доказано, что для раскрашивания любой карты будет достаточно пяти красок. А только 1968 году смогли доказать, что для раскрашивания карты, на которой изображено меньше сорока стран, будет достаточно 4 цветов.
В 1976 году эта задача была решена при использовании компьютера двумя американскими математиками Кеннетом Аппелем и Вольфгантом Хакеном. Для ее решения все карты были поделены на 2000 типов. Для компьютера была создана программа, которая исследовала все типы с целью выяления таких карт, для раскрашивания которых будет недостаточно четырех красок. Только три типа карт компьютер исследовать не смог, поэтому математики изучали их самостоятельно. В результате было установлено, что для раскрашивания всех 2000 типов карт будет достаточно 4 красок. Им было объявлено о решении проблемы четырех красок. В этот день почтовое отделение при университете, в котором работали Аппель и Хакен на всех марках ставило штемпель со словами: «Четырех красок достаточно».
Можно представить задачу о четырех красках несколько иначе.
Для этого рассмотрим произвольную карту, представив ее виде графа: столицы государств являются вершинами графа, а ребра графа связывают те вершины (столицы), государства которых имеют общую границу. Для получения такого графа формулируется следующая задача – необходимо раскрасить граф с помощью четырех цветов так, чтобы вершины, имеющие общее ребро были раскрашены разными цветами.
Эйлеровы и Гамильтоновы графы
В 1859 году английским математиком Уильямом Гамильтоном была выпущена в продажу головоломка – деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира – Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики.
Гамильтоновым циклом называется граф, путь которого является простым циклом, который проходит через все вершины графа по одному разу.
На реке Прегель расположен город Калининград (бывший Кенигсберг). Река омывала два острова, которые между собой и с берегами были соединены мостами. Старых мостов сейчас уже нет. Память о них осталась только на карте города.
Однажды один житель города спросил у своего знакомого, можно ли пройти по всем мостам, побывать на каждом только один раз и вернуться к тому месту откуда началась прогулка. Эта задача заинтересовала многих горожан, но решить ее никто не смог. Этот вопрос вызвал заинтересованность ученных многих стран. Решение проблемы получил математик Леонард Эйлер. Кроме этого он сформулировал общий подход к решению таких задач. Для этого он превратил карту в граф. Вершинами этого графа стала суша, а ребрами – мосты, ее соединяющие.
При решении задачи про мосты Кенигсберга Эйлеру удалось сформулировать свойства графов.
Начертить граф, начав движение с одной вершины и окончив в той же вершине одним росчерком (дважды не проводя по одной и той же линии и не отрывая карандаша от бумаги) возможно в том случае, если все вершины графа четные.
Если есть граф с двумя нечетными вершинами, то его вершины тоже можно соединить одним росчерком. Для этого нужно начать с одной, а закончить на другой любой нечетной вершине.
Если есть граф с числом нечетных вершин больше двух, то граф невозможно начертить одним росчерком.
Если применять эти свойства на задачу о мостах, то можно увидеть, что все вершины исследуемого графа нечетные, значит, этот граф нельзя соединить одним росчерком, т.е. невозможно пройти по всем мостам один раз и закончить путь в том месте, где он был начат.
Если граф имеет цикл (не обязательно простой), содержащий все рѐбра графа по одному разу, то такой цикл называется Эйлеровым циклом. Эйлерова цепь (путь, цикл, контур) — цепь (путь, цикл, контур), содержащая все рѐбра (дуги) графа по одному разу.
ГЛАВА II. ОПИСАНИЕ ИССЛЕДОВАНИЯ И ЕГО РЕЗУЛЬТАТЫ
2.1. Этапы проведения исследования
Для проверки гипотезы исследование включало три этапа (таблица 1):
Источник
