История комбинаторики и машинное представление графов

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

всех вершин связной компоненты графа, содержащей вершину , причем каждая вершина просматривается в точности один раз. Вычислительная сложность поиска в ширину также имеет порядок , так как каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа. Оба вида поиска в графе — в глубину и в ширину могут быть использованы для нахождения пути между фиксированными вершинами и . Достаточно начать поиск в графе с вершины и вести его до момента посещения вершины . Преимуществом поиска в глубину является тот факт, что в момент посещения вершины стек содержит последовательность вершин, определяющую путь из в . Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является соседом верхнего элемента в стеке. Однако недостатком поиска в глубину является то, что полученный таким образом путь в общем случае не будет кратчайшим путем из в .

      От  этого недостатка свободен метод  нахождения пути, основанный на поиске в ширину. Модифицируем процедуру , заменяя строки 7-9 на 

     Рис. 2.6: Нумерация вершин графа на рис. 2.5 (в скобках), соответствующая очередности, в которой они просматриваются  в процессе поиска в ширину. По окончании работы модифицированной таким образом процедуры таблица содержит для каждой просмотренной вершины вершину , из которой мы попали в . Отметим, что кратчайший путь из в обозначается последовательностью вершин ,где для и является первым индексом , для которого . Действительно, в очереди помещены сначала вершины, находящиеся на расстоянии 0 от (т.е. сама вершина ), затем поочередно все новые вершины, достижимые из , т.е. вершины, находящиеся на расстоянии 1 от , и т.д. Под расстоянием здесь мы понимаем длину кратчайшего пути. Предположим теперь, что мы уже рассмотрели все вершины, находящиеся на расстоянии, не превосходящем , от , что очередь содержит все вершины, находящиеся от на расстоянии , и только эти вершины и что таблица правильно определяет кратчайший путь от каждой, уже просмотренной вершины до способом, описанным выше. Использовав каждую вершину , находящуюся в очереди, наша процедура просматривает некоторые новые вершины, и каждая такая новая вершина находится, очевидно, на расстоянии от ,причем, определяя , мы продлеваем кратчайший путь от до до кратчайшего пути от до . После использования всех вершин из очереди, находящихся на расстоянии от , она (очередь), очевидно, содержит множество вершин, находящихся на расстоянии от , и легко заметить, что условие индукции выполняется и для расстояния На рис. 2.6 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в глубину. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

7. Заключение 

    Сейчас  на наших глазах изменяется соотношение  дискретной и классической математики. На протяжении двух с половиной столетий основную роль в изучении природы  играл математический анализ – дифференциальное и интегральное исчисления, дифференциальные уравнения математической физики, вариационное исчисление и т.д. Процессы, имевшие  атомистическую природу, заменялись непрерывными, что бы можно было применять к  ним развитый аппарат математики непрерывного. Дискретная математика была Золушкой, красота которой затмевалась  блеском влиятельных и сильных  сестер.

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

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

8. Список  использованной литературы
1. В.Липский Комбинаторика для программистов Москва мир 1988
2. Введение в комбинаторные методы дискретной математики. Сачков В.Н.-М Наука Главная редакция физико-математической литературы, 1982.-384с.
3. Введение в комбинаторные методы дискретной математики 2-е изд., испр. и доп М.: МЦНМО, 2004.—424 с.: ил
4. Н.Я. Виленкин Популярная комбинаторика Издательство «Наука» 1975
5. http://ru.wikipedia.org