Комбинаторика и ее применение

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

                 Комбинаторика и ее применение

 

Гипотеза:

           Используются задачи из раздела математики

             комбинаторики в геоинформационных системах ?

 

Теория графов — раздел дискретной математике, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов

Изображение графов на плоскости

 

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

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

 

 

Применение Теории Графов в ГИС

Как теория графов влияет на наше передвижение.

Геоинформационная система (ГИС) — система сбора, хранения, анализа и графической визуализации  пространственных (географических) данных и связанной с ними информацией о необходимых объектах.

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

 

Применение

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

Представление данных

Данные в ГИС описывают реальные объекты, такие как дороги, здания, водоемы, лесные массивы. Реальные объекты можно разделить на две абстрактные категории: дискретные (дома, территориальные зоны) и непрерывные (рельеф, уровень осадков, среднегодовая температура). Для представления этих двух категорий объектов используются векторные и растровые данные.

1. Растровые данные

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

2. Векторные данные

Наиболее распространенными типами векторных объектов являются:

• Точки

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

 И др.

Чтобы увидеть применение теории графов, рассмотрим  Задачу о кёнигсбергских мостах— старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кенигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

 

История

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

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

 

Решение задачи по Леонарду Эйлеру

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

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

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

   

  

Упрощённая схема мостов Кёнигсберга                   Граф кёнигсбергских мостов

 

Дальнейшая история мостов Кёнигсберга

 

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                               Задача

 

NN опаздывает в школу. Он (а) знает только 2 дороги до школы № 700 , которая находиться на 9 линии д.6.Она может пойти:

1. Через 9 линию В.О.
2. Через 6-7 линию В.О. (пешеходная зона)

Какой путь короче ,и по какому пути ей (ему) стоит пойти ,чтобы дойти до школы за меньшее время ?

 

 

 

 

 

 

                                       Реальный пример.

 Мы собирались  на собеседование. Так как оно  проходило не на В.О. , а на  ст.м. Сенная пл/Спасская , мы использовали Google Map. Нам высветилось 3 пути.  Благодаря  этому   ,мы узнали какой  путь займет меньше всего времени. В этом примере ,мы как раз и видим как Теория графов проявляется, в геоинформационных системах.

 

 

 

 

 

                                               Метро.

 

 Сейчас  очень много программ , позволяющих  найти самый короткий путь  до места X.

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

1. на какой станции делать пересадку
2. в какие вагону выгоднее заходить для вас

 

 

 

 

 

                                                         Делаем вывод.

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

Google Map.Яндекс Метро. GPRS.

Все эти приложения построение на этой теории и без этих приложений мы уже не можем.

Теория графов- важная составляющая XXI века.