Графы. Основные понятия и определения
Определения и теоремы теории графов, подграфы. Операции над графами и степени их вершин. Цепи, циклы и компоненты. Применение теории графов в школьном курсе математики, в задачах управления дорожным движением, химии, биологии, физике. Графы и информация.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 22.06.2014 |
| Размер файла | 136,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оглавление
- Введение
- Глава 1. Основные теоремы теории графов
- 1.1 Основные определения
- 1.2 Подграфы
- 1.3 Операции над графами
- 1.4 Цепи, циклы, компоненты
- 1.5 Степени вершин графа
- Глава 2. Приложение теории графов в различных областях науки и техники
- 2.1 Применение теории графов в школьном курсе математики
- 2.2 Применение теории графов в задачах управления дорожным движением
- 2.3 Графы и информация
- 2.4 Графы и химия
- 2.5 Графы и биология
- 2.6 Графы и физика
- Заключение
- Список использованной литературы
- Введение
- Теория графов как раздел математики зародилась в XVIII веке и прошла путь от простого способа решения головоломок до серьезной научной теории, находящей своё применение в различных отраслях современной науки. Автору данной работы показалось интересным рассмотреть начала теории графов и задачи, которые можно решать с помощью этой теории. Так как графы являются весьма удобным инструментом для построения математических моделей, то они могут быть использованы для решения различных типов задач. На сегодняшний день актуальность теории графов возросла: она нашла широкое применение в программировании, и на её основе базируются многие алгоритмы.
- В представленной работе будут исследованы различные способы применения теории графов в решении задач, начиная от старинной головоломки (задача о трех домах и трех колодцах) и кончая компьютерной задачей (задача о соединении городов). Особое внимание уделено не только подборке задач, их доказательствам, но и наличию как строгих математических, так и словесных определений, чтобы не нагружать читателя лишней информацией. Также все задачи иллюстрированы для наглядности и лучшего понимания читателем процесса их решения. Стоит также заметить, что теория графов требует творческого подхода, что доказывается наличием интересных задач, решаемых с помощью графов (задача о кенигсбергских мостах, задача на нахождение правильного пути).
- Выше описанные факты подчеркивают актуальность выбранной темы курсовой работы, а именно: “Графы. Основные понятия и определения”.
- Цель курсовой работы: Раскрыть основные понятия и операции выполняемые над графами.
- Для достижения поставленной цели следует решить ряд задач, а именно:
- · Раскрыть понятия графа;
- · Дать характеристику операция выполняемыми над графами;
- · Раскрыть методы применения графов в различных областях науки.
- Глава 1. Основные теоремы теории графов
- 1.1 Основные определения
- теорема теория граф применение
- Пусть -- непустое множество, -- множество всех его двухэлементных подмножеств. Пара , где -- произвольное подмножество множества , называется графом (неориентированным графом). Рассматриваются только конечные графы, т. е. множество предполагается конечным. Элементы множества называются вершинами графа, а элементы множества -- ребрами. Итак, граф -- это конечное множество вершин и множество ребер, . Множества вершин и ребер графа обозначаются и соответственно. Вершины и ребра графа называются его элементами. Число вершин графа называется его порядком. Если и , то называют - графом.
- Две вершины и графа смежны, если множество является ребром, и не смежны в противном случае. Если -- ребро, то вершины и называют его концами. В этой ситуации говорят также, что ребро соединяет вершины и . Такое ребро обозначается символом . Два ребра называются смежными, если они имеют общий конец.
- Вершина и ребро называются инцидентными, если является концом ребра (т. е. ), и не инцидентными в противном случае. Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.
- Множество всех вершин графа , смежных с некоторой вершиной , называется окружением вершины и обозначается через или просто .
- Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии -- ребрам. В качестве иллюстрации рассмотрим граф на рис. 1.1. Это (5, 6)-граф, , . Вершины 1 и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро инцидентны, .
Размещено на http://www.allbest.ru/
- Рассмотрим графы специального вида, часто используемые в дальнейшем. Граф G называется полным, если любые две его вершины смежны, т. е.
- .
- Полный граф порядка обозначается символом , число ребер в нем равно, очевидно, . На рис. 1.2 изображены графы для . Граф называется пустым, если в нем нет ребер. Пустой граф порядка обозначается через .
Размещено на http://www.allbest.ru/
- На рис. 1.3 показаны простые циклы () и простые цепи (). Очевидно, что , а . На рис. 1.4 приведены два изображения простого цикла и граф Петерсена, котрый получается соединением двух таких циклов.
Размещено на http://www.allbest.ru/
- На рис. 1.5 изображены колеса (). Заметим, что
- И
- .
Размещено на http://www.allbest.ru/
- Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из и из вершин, обозначается символом . При получаем звезду . Очевидно, что
- ,
- .
- На рис. 1.6 изображены звезда и полный двудольный граф .
Размещено на http://www.allbest.ru/
- Заметим, что одна из долей двудольного графа может быть пустой. Так, -- двудольный граф с одной пустой долей, можно трактовать как двудольный граф с двумя одновершинными долями или как двудольный граф, одна из долей которого содержит две вершины, а другая является пустым множеством. Аналогично двудольным определяется -дольный и полный -дольный графы для . На рис. 1.7 приведен трехдольный граф.
- Легко подсчитать число всех графов с фиксированным множеством вершин . Эти графы различаются своими ребрами, и потому их число равно количеству подмножеств в , т. е. , где . Однако эти графы не всегда следует различать. Как в применениях теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребрами). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно не различать. Оформим эти соображения в виде следующего определения.
- Пусть и -- графы, а -- взаимно однозначное отображение (биекция). Если для любых вершин и графа их образы и смежны в тогда и только тогда, когда и смежны в , то эта биекция называется изоморфизмом графа на граф . Если такой изоморфизм существует, то мы пишем (тогда и ) и говорим, что графы и изоморфны.
- Например, два графа, представленные на рис. 1.8, и полный двудольный граф на рис. 1.6 попарно изоморфны (почему?), а графы на рис. 1.9 не изоморфны (почему?). Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным.
Размещено на http://www.allbest.ru/
- Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, множество всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять, т. е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия «граф».
- В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помеченный граф». Граф порядка называется помеченным, если его вершинам присвоены некоторые метки, например, номера . Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин -- с множеством чисел , определим равенство помеченных графов и одного и того же порядка: тогда, когда . На рис. 1.10 изображены три разных помеченных графа.
Размещено на http://www.allbest.ru/
- При необходимости подчеркнуть, что рассматриваемые графы различаются лишь с точностью до изоморфизма, говорят: «абстрактный граф». Строго говоря, абстрактный (или непомеченный) граф -- это класс изоморфных графов.
- Для произвольного графа следующим образом определяется дополнительный граф (или дополнение) : , и любые две несовпадающие вершины смежны в тогда и только тогда, когда они не смежны в (рис. 1.11).
Размещено на http://www.allbest.ru/
- Очевидно, что и , если . Из определения следует, что сумма числа ребер -вершинных графов и равна числу ребер в полном графе , т. е.
- .
- Граф, изоморфный своему дополнению, называется самодополнительным. Например, , и -- самодополнительные графы.
- Иногда приведенное выше определение графа оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром. Так возникает понятие «мультиграф». Мультиграф -- это пара , где -- непустое множество вершин, а -- семейство подмножеств множества (ребер). Употребление термина «семейство» вместо «множество» означает, что элементы множества могут в повторяться, т. е. допускаются кратные ребра.
- Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще петли, т. е. ребра, соединяющие вершину саму с собой. Псевдограф -- это пара , где -- непустое множество вершин, а -- некоторое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На рис. 1.12 изображены мультиграф и псевдограф.
Размещено на http://www.allbest.ru/
- Изучаются также ориентированные графы. Тогда множество двухэлементных подмножеств заменяется декартовым квадратом , состоящим из упорядоченных пар элементов множества . Итак, ориентированный граф (или орграф) -- это пара , где -- множество вершин, -- множество ориентированных ребер, которые называются дугами, . Если -- дуга, то вершины и называются ее началом и концом соответственно. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (см. рис. 1.13). Аналогично определяется ориентированный мультиграф (см. рис. 1.14). Рассматриваются также смешанные графы, у которых есть и дуги, и неориентированные ребра.
Размещено на http://www.allbest.ru/
- Для всех этих видов графов естественно вводится понятие изоморфизма как биекции между множествами вершин, сохраняющей смежность, кратности ребер, петли и направления дуг.
- Графы в смысле нашего первого определения называются еще простыми (или обыкновенными). Хотя часто для теории несущественно, какие из этих видов графов (простые, мульти- или псевдо-) рассматриваются, однако здесь в основном будут рассматриваться простые графы. Ради сокращения речи термин «граф» употребляется и в других ситуациях (например, вместо «мультиграф» или «ориентированный граф»), но подобные случаи либо специально оговариваются, либо ясны из контекста.
- 1.2 Подграфы
- Граф называется подграфом (или частью) графа , если и . Если -- подграф графа , то говорят, что содержится в . Подграф называется основным подграфом, если . Если множество вершин подграфа есть , а множество его ребер совпадает с множеством всех ребер графа , оба конца которых принадлежат , то называется подграфом, порожденным (или индуцированным) множеством , и обозначается через .
- На рис. 2.1 изображены граф и три его подграфа , и , среди которых является основным, а -- порожденным.
Размещено на http://www.allbest.ru/
- Важный класс подграфов составляют подграфы, полученные в результате удаления вершин. Пусть -- вершина графа . Граф
- получается из графа в результате удаления вершины и всех инцидентных ей ребер. Очевидно, что
- .
- 1.3 Операции над графами
- Удаление вершины или ребра, а также переход к подграфу -- это операции, с помощью которых можно из имеющегося графа получать другие графы с меньшим числом элементов. Известны также операции, позволяющие, наоборот, получать из имеющихся графов «большие» графы. Такова, например, операция добавления ребра: если вершины и графа не смежны, то можно определить граф , где
- .
- Он получается из графа добавлением нового ребра .
Размещено на http://www.allbest.ru/
- Одной из наиболее важных является операция объединения. Граф называется объединением (или наложением графов и , если и (рис. 3.1). В этой ситуации пишут . Объединение называется дизъюнктным, если . Аналогично определяются объединение и дизъюнктное объединение любого множества графов, причем в последнем случае никакие два из объединяемых графов не должны иметь общих вершин.
- Еще одна операция -- отождествление (или cлияние) вершин. Пусть и -- две вершины графа и
- К графу присоединим новую вершину , соединив ее ребром с каждой из вершин, входящих в объединение окружений вершин и в графе . Говорят, что построенный граф получается из графа отождествлением вершин и .
Размещено на http://www.allbest.ru/
- Стягивание ребра означает отождествление смежных вершин и . На рис. 3.2 показаны граф и граф, полученный из стягиванием ребра .
- Граф называется стягиваемым к графу , если получается из в результате некоторой последовательности стягиваний ребер. Легко видеть, например, что граф Петерсена (рис. 1.4 справа) стягиваем к . Очевидно, что любой непустой связный граф, отличный от , стягиваем к . Но уже не любой связный граф стягивается к графу . Например, простая цепь не стягивается к .
- 1.4 Цепи, циклы, компоненты
- Чередующаяся последовательность
(1)
вершин и ребер графа, такая что
(),
называется маршрутом, соединяющим вершины и (или -маршрутом). Очевидно, что маршрут (1) можно задать последовательностью его вершин, а также последовательностью его ребер.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если . Циклическая цепь называется циклом, а циклическая простая цепь -- простым циклом. Число ребер в маршруте (1) называется его длиной. Простой цикл длины называется -циклом, 3-цикл часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.
Очевидно, что любую цепь графа можно рассматривать как его подграф.
Обратимся, например, к графу, изображенному на рис. 4.1. В нем (1,2) и (1, 2, 4, 7) являются простыми цепями; (1, 2, 4, 7, 8, 4) -- цепь, не являющаяся простой; (1, 2, 4, 7, 8, 4, 2) -- маршрут, не являющийся цепью; (1, 2, 4, 1) -- простой цикл. Обхват этого графа равен 3.
Размещено на http://www.allbest.ru/
Для ориентированного графа вводится понятие ориентированного маршрута -- это последовательность вида (1), в которой
).
Аналогом цепи в этой ситуации служит путь (ориентированная цепь). Вершина называется достижимой из вершины , если существует -путь.
Ясно, что при произвольный -маршрут, не являющийся простой цепью, превращается в простую -цепь после устранения «лишних кусков».
Утверждение 4.1. а) при всякий -маршрут содержит простую -цепь; б) всякий цикл содержит простой цикл; в) объединение двух несовпадающих простых -цепей содержит простой цикл; г) если и -- два несовпадающих простых цикла, имеющих общее ребро , то граф также содержит простой цикл.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Учитывая утверждение 4.1, можно в этом определении заменить маршрут цепью или простой цепью. Очевидно следующее
Утверждение 4.2. Для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины и каждой другой вершины существовал -маршрут.
Всякий максимальный связный подграф графа называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, т. е. не содержащийся в связном подграфе с большим числом элементов.
Теорема 4.3. Каждый граф представляется в виде дизъюнктного объединения своих связных компонент. Разложение графа на связные компоненты определено однозначно.
Пусть -- произвольный граф. На множестве определим бинарное отношение , положив для вершин и , если или в графе существует -маршрут. Очевидно, что это отношение есть эквивалентность. Следовательно, мы получим разбиение множества на классы, отнеся в один класс все вершины, эквивалентные друг другу. Пусть -- такое разбиение. Очевидно, что порожденные подграфы и только они являются компонентами графа и - дизъюнктное объединение.
Полезно следующее
Утверждение 4.4. Для любого графа либо он сам, либо его дополнение является связным.
Пусть -- несвязный граф, -- множество вершин какой-либо компоненты связности, . Тогда для любых и в дополнительном графе есть ребро . Следовательно, произвольная вершина из соединена с маршрутом длины 1, а произвольная вершина из (отличная от ) соединена с маршрутом длины не более чем 2. Теперь из утверждения 4.2 вытекает, что связан.
С помощью предыдущего утверждения некоторые проблемы (например, проблема изоморфизма) сводятся к случаю связных графов. Полезна также и следующая
Утверждение 4.5. Пусть -- связный граф, . Тогда: если ребро принадлежит какому-либо циклу графа , то граф связен; если ребро не входит ни в какой цикл, то граф имеет ровно две компоненты.
1) Пусть ребро принадлежит циклу графа . Заменив в каждой -цепи, содержащей , подцепь на -цепь , получим -маршрут, не содержащий ребра . Следовательно, в графе любые две несовпадающие вершины соединены маршрутом, не проходящим через . Но тогда и граф связен.
2) Пусть ребро не входит ни в какой цикл графа . Тогда, очевидно, вершины и принадлежат разным компонентам, например, и соответственно , графа . Для произвольной вершины в существует -маршрут. Если ребро в этот маршрут не входит, . В противном случае .
Ниже число ребер и число компонент графа обозначаются через и соответственно. Вспомним, что число ребер в произвольном графе порядка не больше числа ребер в полном графе , равного . Но сколько ребер может быть в графе порядка с фиксированным числом компонент? На этот вопрос отвечает следующая
Теорема 4.6. Если для -вершинного графа G, то
причем обе эти оценки для достижимы.
Вначале рассмотрим верхнюю оценку. Пусть -- граф порядка с компонентами и максимальным для таких графов числом ребер. Тогда каждая его компонента является полным графом. Пусть, далее, и -- две компоненты. Предположим, что каждая из этих компонент имеет больше чем одну вершину, т. е. . Пусть -- вершина из второй компоненты. Удалив из графа все ребра, инцидентные вершине , и соединив ребром с каждой вершиной из первой компоненты, получим новый граф порядка с тем же числом компонент и большим числом ребер. Последнее невозможно в силу выбора , стало быть, только одна из компонент может иметь порядок, больший 1. Он равен , и потому
Перейдем к доказательству неравенства . Оно очевидно при , так как тогда . Воспользуемся индукцией по . Пусть и пусть для графов с меньшим, чем , числом ребер соответствующее неравенство верно. Рассмотрим граф , где . Согласно утверждению 4.5 число компонент этого графа равно или . Число ребер в нем равно . По индуктивному предположению в обоих случаях
Следовательно,
.
Дизъюнктное объединение
,
где обозначает любой связный граф c ребрами (графы, называемые деревьями и изучаемые далее), реализует равенство
.
Из первой части приведенного доказательства вытекает
Следствие 4.7. При фиксированных и среди графов порядка с
существует только один граф, а именно,
,
с максимальным числом ребер.
1.5 Степени вершин графа
Степенью вершины графа называется число инцидентных ей ребер, т. е. число вершин в ее окружении. Будем обозначать степень вершины через (или ). Тем самым
.
Максимальная и минимальная степени вершин графа обозначаются символами и соответственно:
, .
Список степеней вершин графа называется его степенной последовательностью. Порядок членов в этой последовательности роли не играет.
Вершина степени 0 называется изолированной, вершина степени 1 -- концевой (или висячей). Ребро, инцидентное концевой вершине, также называется концевым.
Рассмотрим сумму степеней всех вершин графа. Каждое ребро вносит в эту сумму 2, поэтому верно
Утверждение 5.1 («лемма о рукопожатиях»). Сумма степеней всех вершин графа -- четное число, равное удвоенному числу ребер:
Возможная интерпретация этой леммы такова: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала).
Следствие 5.2. В любом графе число вершин нечетной степени четно.
Понятие степени вершины и лемма о рукопожатиях cохраняются для мульти- и псевдографов. При этом каждая петля вносит в степень соответствующей вершины двойку.
Граф называется регулярным (или однородным), если степени всех его вершин равны; степенью регулярного графа называется степень его вершин. Степень регулярного графа обозначается через .
Последовательность целых неотрицательных чисел ниже называется -последовательностью и обозначается одной буквой . Произвольная -последовательность называется графической, если существует граф, степенная последовательность которого совпадает с . Этот граф называется реализацией последовательности . Очевидно, что порядок членов в графической -последовательности несуществен, а каждый ее член удовлетворяет неравенствам . Часто удобно эти последовательности считать невозрастаюшими. Согласно лемме о рукопожатиях сумма всех членов графической последовательности является четным числом.
Назовем -последовательность правильной, если выполняются два следующих условия:
1) ,
2) -- четное число.
Без ограничения общности графическую последовательность можно всегда считать правильной.
Рассмотрим последовательность . Существуют ровно пять графов (не обязательно связных), являющихся реализациями последовательности . Они имеют следующие компоненты: 1) , и 2) , и 3) и 4) и 5) и .
В общем случае графическая последовательность имеет много реализаций и их число определить сложно.
Итак, графическую последовательность всегда можно считать правильной. Кроме того, в ней должны быть равные члены (если длина ее ), поскольку не существует графа, степени всех вершин которого попарно различны (почему
Однако указанные условия отнюдь не являются достаточными для графичности последовательности. Очевидно, например, что последовательность не является графической, хотя и удовлетворяет упомянутым условиям. Известно несколько критериев графичности последовательности. Мы укажем один из них.
Теорема 5.3 (П. Эрдёш, Т. Галлаи, 1960 г.). Правильная -последовательность является графической тогда и только тогда, когда для каждого верно неравенство
При тестировании последовательности с помощью этого критерия нет необходимости проверять все неравенств. Обозначим . Тогда верно
Утверждение 5.4. Если правильная -последовательность удовлетворяет каждому из неравенств критерия Эрдеша-Галлаи при , то она удовлетворяет и каждому из оставшихся неравенств.
Глава 2. Приложение теории графов в различных областях науки и техники
2.1 Применение теории графов в школьном курсе математики
В данной главе будут рассмотрены задачи, которые используются в школе на уроках математики.
Условно их можно классифицировать, подразделив на несколько групп:
ь Задачи о мостах.
ь Логические задачи
ь Задачи о "правильном" раскрашивании карт
ь Задачи на построение уникурсальных графов
Рассмотрим несколько типичных примеров решения задач каждого вида.
Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Поэтому в данном параграфе мы не будем подробно останавливаться разборе этого типа задач.
Основой применения графов для решения логических задач служит выявление и последовательное исключение возможностей, заданных в условии. Это выявление логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.
Задача 1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?
Решение: Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.
Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.
Задача 2. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?
Решение: Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
Иными словами, суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа.
Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы - ребрами, а окружающий страны Мировой океан - бесконечной гранью.
Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют "правильно" раскрашенной.
Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Этому вопросу уделяется большое внимание в популярной литературе, и здесь мы не будем останавливаться на его рассмотрении.
Задачи на проведение эйлеровых линий без повторений и без отрыва карандаша от бумаги являются одним из математических развлечений. При решении подобных задач необходимо помнить следующее положение. Для того, чтобы на графе имелась цепь, соединяющая АА и ВВ, содержащая все его ребра в точности по одному разу, необходимо и достаточно, чтобы АА и ВВ были единственными нечетными вершинами, т. е. вершинами с нечетной степенью.
2.2 Применение теории графов в задачах управления дорожным движением
Тенденция создания больших городов и регионов с высокой концентрацией населения характерна для всех промышленных стран, поэтому основная масса автомобилей сосредотачивается в пределах городских территорий, вызывая огромные трудности в организации дорожного движения и обеспечении его безопасности. Основными негативными последствиями интенсивной автомобилизации, характерными для многих городов являются: резкое снижение скорости движения, острый дефицит городских площадей для организации кратковременной и длительной стоянки автомобилей, транспортный шум, загрязнение окружающей Среды и, наконец, рост количества дорожно-транспортных происшествий [1].
Постоянное усложнение дорожно-транспортных условий требует непрерывного совершенствования методов и средств управления движением. Автоматизация управления дорожным движением занимает одно из ведущих мест в комплексе мероприятий, направленных на решение задачи обеспечения нормального функционирования современного города в условиях повышенной автомобилизации [3].
Автоматизированная система управления дорожным движением -- это комплекс технических и программных средств, управляемых человеком и компьютером. Основные задачи современной автоматизированной системы -- сбор, хранение и обработка информации о транспортных потоках, состоянии улично-дорожной сети (УДС) и оптимизированное управление дорожным движением [4].
Автоматизированную систему управления дорожным движением, по специфике решаемых задач можно разделить на уровни.
«Информационный уровень -- сбор и хранение информации об УДС города с дислокацией технических средств организации дорожного движения (ТСОДД) (дорожные знаки, светофоры), разметки и элементов инженерного обустройства дороги. Операционный уровень -- обработка оперативных данных о состоянии УДС, технических средствах организации дорожного движения, аварийности и др.
«Управленческий уровень -- решение задач контроля правильности установки новых ТСОДД, координированного управления, оптимизации управления транспортными потоками и т.п.
Задачи управленческого уровня наиболее трудно поддаются формализации. К ним можно отнести задачи оптимизации управления транспортными потоками на УДС города в условиях постоянно изменяющихся дорожно-транспортных условий: нахождение всевозможных путей между различными пунктами назначения;
«нахождение кратчайшего пути между пунктами УДС;» определение безопасного маршрута прохождения транспортного потока.
Математическая модель, лежащая в основе автоматизированной системы, может быть построена с применением различных теорий. Например, с использованием принципов объектно-ориентированного программирования. В основе такого подхода лежит принцип описания физических объектов различной природы и взаимодействий между ними [2].
Объектом управления в разработанной системе является транспортный поток N, движущийся по улично-дорожной сети S. Сформулируем задачу управления потоком следующим образом: необходимо организовать движение транспортного потока N таким образом, чтобы выполнялись следующие условия:
1. максимальная безопасность движения;
2. максимальная пропускная способность перекрестков.
Построим функцию управления F: ( Ni, Si, U ) ( Nj, Si+1 ), т.е. имея поток Ni на участке схемы Si и воздействуя на него управляющим органом U, получим другой поток Nj на следующем участке Si+1.
Другой метод построения модели УДС -- это применение теории графов.
Вершиной графа является внешняя граница перекрестка. Ребро показывает направление движение транспортного потока от одной границы перекрестка до другой. Если движение транспорта в каком-либо направлении запрещено, то вершины не соединяются [4]. Таким образом, УДС можно представить ориентированным графом. Этот граф является циклическим, т.к. существует хотя бы один путь, в котором начальная вершина совпадает с конечной, и при этом данный путь содержит минимум одно ребро. Другими словами, всегда существует путь, по которому можно, выехав из начального пункта, вернуться обратно.
Рассмотрение УДС, как последовательности участков и перекрестков, позволило представить улично-дорожную сеть, как простой циклический ориентированный граф. Дополнительно этот граф является связным, т.к. для любых двух точек УДС, существует путь из одной в другую.
Опишем модель УДС в терминах теории графов:
G = (V, E),
где V- конечное множество, E -- бинарное отношение на V, т.е. подмножество множества VxV. Множество E является множеством вершин, а его элемент -- вершиной, а множество V является множеством ребер (участков УДС), а его элемент -- ребром [6].
Указанная модель позволяет формализовать некоторые понятия предметной области. Точки начала и конца участка ( ), представляют собой смежные вершины и пересечение участков есть инцидентность ребер и вершины, представляющей начало заданного участка. Уровень сложности перекрестка можно определить суммарной степенью вершин, ограничивающих этот перекресток. Степенью вершины является суммарное количество инцидентных ей ребер. Путь из одной точки УДС в другую, представляется, как путь из вершины u в вершину v и определяется, как последовательность вершин (v0, v1, …,vk), в которой v0=u, vk=v и (vi-1,vi) E для всех i=1,2,…, k. Таким образом, проезд из одной точки в другую по k участкам дороги можно представить, как путь длины k, состоящий из k ребер. Задача нахождения путей между различными точками УДС, сводится к следующему математическому описанию.
Для заданных G = (V, E), u, v V, требуется найти вершины (v0, v1, …,vk) V и ребра (vi-1,vi) E, для всех i=1,2,…, k, где v0 =u, а vk= v. Если такой путь существует, то будем говорить, что вершина v достижима из u по пути p. Запишем это как объект «участок» имеет имманентные свойства, такие как протяженность, ширина проезжей части, полосность и т.д. С другой стороны, рассмотрение транспортного потока, движущегося по этому участку, приводит к появлению дополнительных свойств, являющихся характеристиками этого потока: интенсивность, плотность потока и средняя скорость движения.
С математической точки зрения любые из имманентных свойств объекта можно представить как вес ребра. Появление этой характеристики превращает граф во взвешенный.
Одной из задач управления дорожным движением является задача о нахождении кратчайшего пути между заданными точками. В этой задаче дан ориентированный взвешенный граф G = (V, E), с вещественной весовой функцией w: E R, w (u, v) -- вес ребра (u, v), а R -- множество вещественных значений весовой функции. Вес пути p = (v0, v1, …,vk) определим как сумму весов ребер, входящих в этот путь.
Кратчайший путь из u в v -- это любой путь p из u в v, для которого.
В качестве веса можно брать не только длину участка, но и время, интенсивность движения на участке и другие величины, являющимися критериями оптимальности и обладающие свойством аддитивности. Использование в качестве весовых функций различных характеристик участков УДС приводит к разбиению основной задачи управления дорожным движением на подзадачи с различными критериями оптимальности.
Существует множество алгоритмов и методов решения, приведенных выше задач, такие как поиск в ширину, поиск в глубину, метод Форда-Фолкерсона для нахождения максимального потока в сети, алгоритм Беллмана-Форда для получения путей на графе. Особое внимание при выборе методов решения поставленных задач уделяется их быстро действию, а также форматам хранения исходных данных.
2.3 Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.
Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.
Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.
2.4 Графы и химия
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
CnH2n+2
Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны.
Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее обобщения рассмотрел Д. Пойа.
2.5 Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов - размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.
Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
2.6 Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку из какого-либо диэлектрика (изолирующего материала), на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы и другие), их пересечение в других местах вызовет замыкание электрической цепи.
В ходе решения этой задачи необходимо вычертить плоский граф, с вершинами в указанных точках.
Итак, из всего вышесказанного неопровержимо следует практическая ценность теории графов, доказательство которой и являлось целью данного параграфа.
Заключение
Перечисленные методики применения графов доказывают тот факт, что теория графов позволяет создавать точные математические модели реальных объектов и ситуаций, с которыми довольно легко и просто оперировать. Стоит заметить, что условия приведенных в работе задач, являются жизненными ситуациями, а не сухими математическими формулировками, что отражает актуальность рассмотренной нами темы. На примере рассмотренных в работе методик можно сделать следующие выводы:
ь теория графов может быть использована как любопытный инструмент для решения различных задач-головоломок;
ь теория графов позволяет быстро и изящно решать задачи, которые весьма трудно решить другими методами;
ь теория графов находит многочисленные применения в различных практических вопросах;
ь теория графов позволяет решить не только одну отдельно взятую задачу, но и находить методы решения целого класса задач (это свойтсво графов используется в программировании, где существует целый класс алгоритмов).
Список использованной литературы
1. Автомобильные перевозки и организация дорожного движения: Справочник. Пер. с англ. / В. У. Рэнкин, П. Клафи, С. Халюерт и др. -- М.: Транспорт, 2001. -- 592 с.
2. Бадд Т. Объектно-ориентированное программирование в действии / Пер. с англ. -- СПб.: 2007. -- 464 с.
3. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;
4. Гарднер М. "Математические головоломки и развлечения", М. "Мир", 2001;
5. Клинковштейн Г. И. Организация дорожного движения. -- М.: Транспорт, 2005. -- 192 с.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2011. -- 960 с.
7. Кременец Ю. А. Технические средства организации дорожного движения. -- М.: Транспорт, 2009. -- 255 с.
8. Михеева Т. И., Михеев С. В. Модели наследования в системе управления дорожным движением // «Информационные технологии» 2011 г.
9. "Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");
10. Оре О. "Графы и их применения", М. "Мир", 1965;
Размещено на Allbest.ru
...Подобные документы
Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Основные понятия, связанные с графом. Решение задачи Эйлера о семи кёнигсбергских мостах. Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Применение теории графов к решению задач по математике; степени вершин и подсчёт рёбер.
курсовая работа [713,8 K], добавлен 16.05.2016Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
реферат [106,0 K], добавлен 27.11.2008Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Сущность теории графов и ее применение на современном этапе в различных отраслях науки и техники, особенно в экономике и социологии. Понятие дерева, его разновидности, характерные свойства. Операции, совершаемые над графами и возможности их реализации.
контрольная работа [1,6 M], добавлен 08.12.2009Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа [725,8 K], добавлен 15.12.2008Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
курсовая работа [649,2 K], добавлен 18.01.2014Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015Основополагающие понятия теории графов и теории групп. Определение эквивалентности, порождаемой группой подстановок, и доказательство леммы Бернсайда о числе классов такой эквивалентности. Сущность перечня конфигурации, доказательство теоремы Пойа.
курсовая работа [682,9 K], добавлен 20.05.2013Типы бинарных отношений. Изображение графов в виде схемы. Цикл в графе, совпадение его начальной и конечной вершины. Понятие достижимости в теории графов, их математические свойства. Частично упорядоченное множество как один из типов бинарного отношения.
контрольная работа [116,5 K], добавлен 04.09.2010Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
лабораторная работа [42,2 K], добавлен 11.03.2012Примеры решения задач по заданию графов. Определение основных характеристик графа: диаметра, радиуса, эксцентриситета каждой вершины. Вычисление вершинного и реберного хроматического числа. Упорядоченность матричным способом и построение функции.
контрольная работа [224,6 K], добавлен 05.07.2014История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012
