В категории материалов: 33
Показано материалов: 1-30 |
Страницы: 1 2 » |
Сортировать по:
Дате ·
Названию ·
Рейтингу ·
Комментариям ·
Загрузкам ·
Просмотрам
 Живительная красота графов заключается в их простоте —
они состоят лишь из точек и линий, соединяющих эти точки. Но
по-настоящему удивительно то, чего можно достичь с помощью анализа этих
точек и линий. |
Граф определяется множеством точек (которые также
называются вершинами, или узлами графа) и множеством ребер, или дуг
графа, которые соединяют его вершины попарно.
|
Циклы — это очень простые маршруты, проходящие через
все вершины, начальная и конечная точка которых совпадают. Примеры
циклов представлены на следующих рисунках.
|
Определив вершины графа, их можно соединить ребрами так, как показано на следующих рисунках.
|
Задача звучит так: в трех домах а, Ь, с живут три семьи, враждующие между собой. Рядом с их домами находятся три колодца е, f, g.
Один из колодцев всегда полон, два других пусты.
|
Дерево — это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на следующем рисунке:
|
Помимо генеалогических деревьев, которые даже могут
висеть в гостиной, графы используются на телевидении для представления
числа происшествий, уровня безработицы, биржевых котировок по дням и по
годам.
|
В этой главе мы приглашаем читателя подумать над
одной задачей теории графов, которая кажется очень простой. Это задача о
раскраске карт. Вы увидите, как одна занимательная задача иногда может
вызвать подлинный прорыв в науке.
|
Как выглядят карты (плоские графы), для раскраски
которых достаточно всего двух цветов? А трех цветов? Ответ на эти
вопросы нетруден, и его можно найти довольно быстро. Обратимся к теореме
о двух красках, которая гласит: «Карту можно раскрасить двумя цветами
тогда и только тогда, когда в соответствующем ей графе все вершины имеют
четную степень».
|
В 1852 году Френсис Гутри, изучая различные карты,
предположил, что их можно раскрасить в четыре цвета так, чтобы страны с
общими границами имели разные цвета.
|
Раскраска вершин V(С) графа G множеством цветов С состоит в присвоении каждой вершине графа цвета из множества С таким образом, что смежные вершины будут окрашены в разные цвета.
|
Представьте себе добросовестного почтальона, которому
нужно обойти все улицы, где проживают адресаты писем. Оптимальным для
него будет такой маршрут, при котором ему придется пройти по каждой
улице ровно один раз.
|
Представьте себе добросовестного почтальона, которому
нужно обойти все улицы, где проживают адресаты писем. Оптимальным для
него будет такой маршрут, при котором ему придется пройти по каждой
улице ровно один раз.
|
Рассмотрим следующую задачу. Можно ли найти такой
путь в связном графе, который бы проходил через все вершины графа только
один раз, причем начальная и конечная вершины при этом совпадали? Такие
пути называют гамильтоновыми циклами.
|
В предыдущем разделе мы говорили о гамильтоновых
циклах — путях, которые содержат каждую вершину графа ровно один раз,
причем начальная и конечная вершина этих путей совпадают.
|
Во множестве реальных ситуаций используются не
обыкновенные графы, а орграфы, то есть ориентированные графы. В этих
графах к ребрам добавляются стрелки, указывающие направление.
|
С начала Второй мировой войны начал формироваться
широкий спектр методов оптимизации планирования. После того как СССР
запустил в космос первый спутник, в США началась работа над различными
крупными проектами, начиная от баллистической ракеты «Поларис»,
размещаемой на подводных лодках, и заканчивая высадкой человека на Луну.
|
Многие свойства фигур, которые изучаются в геометрии,
зависят от их параметров: величин углов, расстояний, перпендикулярности
прямых, площади фигур, объема тел и так далее. |
Рассмотрим выпуклый п-угольник с вершинами V, V2,..., Vn и ребрами V1V2,..., V2V3,...,Vn-1Vn, VnV1. |
Теперь мы знаем ограничения на число граней С и число вершин V выпуклого многогранника. Число ребер А полностью зависит от С и V. Попробуем исключить А из формулы Эйлера. |
Попробуйте представить себе выпуклый многогранник, у
которого нет ни одной грани в форме треугольника, четырехугольника или
пятиугольника. Очевидно, что такого выпуклого многогранника не
существует. |
Если вы не привыкли следовать правилам, то возможно,
что вы задавались вопросом, существуют ли фигуры без повторяющихся
элементов. Например, существует ли многогранник, все стороны которого
являются различными многоугольниками: один треугольник, один
четырехугольник, один пятиугольник и так далее. |
Помимо формулы Эйлера и ее удивительных следствий,
существует множество других областей геометрии, где теория графов
представляет особый интерес. Далее мы приведем несколько примеров. |
В этой книге мы уже рассказали о многих способах
применения графов. В этой последней главе мы вкратце расскажем о том,
где еще используются графы. Вы увидите, что они применяются не только в
картах, маршрутах и генеалогических деревьях. |
Графы представляют особый интерес при изучении
структуры молекул. Сложную структуру молекулы или изомера удобно
представить в виде простого графа, что помогает понять связи между
атомами молекулы. |
Теория графов играет ключевую роль в различных этапах
архитектурных проектов. После того как определены части проекта и перед
тем как перейти от эскизов к чертежам, будет крайне полезно построить
граф взаимосвязей предварительно определенных элементов проекта. |
Кристофер Александер — известный американский
архитектор и преподаватель, который в 70-е годы XX века развил идею о
том, как графы, компьютерные программы и вычислительные мощности помогут
рационализировать урбанистику и анализ архитектурных проектов. |
Графы также находят применение в социологии,
антропологии, географии, экономике, теории коммуникации, социальной
психологии и многих других сферах, где анализируются социальные сети:
элементы социальной структуры представляются в виде узлов графа, а отношения между ними — в виде ребер, соединяющих вершины графа. |
В нашем сложном мире одним из важнейших вопросов
является необходимость качественного планирования расписаний с целью
оптимизации временных затрат. Все, что окружает нас, подчиняется
принципу «время — деньги». |
Существует множество игр, в которых нужно построить
определенный граф или же с помощью графа определить, существует ли
выигрышная стратегия. В качестве примера и в завершение нашей книги мы
расскажем о некоторых таких играх. |
|
