-
Появление Теории Графов
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. -
Задача о семи Кёнигсберских мостах
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя». -
Использование Теории графов в математике
В 1847 году Кирх Гоф разработал теорию деревьев для решения совместной системы линейных алгебраических уравнений, позволяющюю найти значение силы тока в каждом проводнике (дуге) и в каждом контуре рассматриваемой электрической цепи. Будучи физиком по образованию, он подходил к решению задач как математик. Кирх Гоф показал что для решения системы уравнений не обязательно рассматривать в отдельности каждый цикл графа электрической цепи -
Гипотеза четырех красок
Гипотеза Четырех красок имеет интересную историю, но в ее появлении имеется много непонятного. Формулировка задачи и исторической статьи Мея: “Предполагается, что любую карту на плоскости или поверхности шара можно раскрасить только четырьмя красками таким образом, чтобы никакие две смежные страны не были одного и того же цвета. Каждая страна должна состоять из одной связной области, а смежными называются страны, которые имеют общую границу в виде линии . -
Использование теории графов в химии
Кэлли в 1857 году, занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемый деревьями. Он стремился перечислить изомеры предельных (насыщенных) углеводородов с данным числом n атомов углерода. -
Использование Теории графов в психологиии
В 1936 году психолог Левин высказал предположение, что “жизненное пространство” индивидуума можно представить с помощью планарной карты. На такой карте области представляют разлиные типы деятельности человека, например, то, что он делает на работе, дома, или же его хобби. -
Алгоритм Данцига
Алгоритм Данцига — алгоритм для нахождения кратчайших путей ко всем вершинам планарного направленного графа. Назван в честь американского математика Джорджа Данцига. Алгоритм близок к алгоритму Флойда, отличается от него только другим порядком исполнения одних и тех же операций.
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B0%D0%BD%D1%86%D0%B8%D0%B3%D0%B0 -
Алгоритм Дейкстры
Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS. -
Алгоритм Флойда
Алгоритм Флойда (алгоритм Флойда–Уоршелла) — алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Алгоритм работает за \Theta(n^3) времени и использует \Theta(n^2) памяти. Разработан в 1962 году. -
Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом. Алгоритм маршрутизации RIP (алгоритм Беллмана-Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.
