Поиск кротчайших путей по алгоритму Флойда

Министерство образования и науки Российской Федерации

1. Воронежский Институт Высоких Технологий

1. Факультет Информационных технологий

Курсовая работа

По дисциплине “Дискретная математика”

По теме: “Поиск кротчайших путей по алгоритму Флойда”

Выполнил:

Студент группы ИН-044 Саунин А.В.

Руководитель:

доцент Белецкая С.Ю.

Воронеж 2007

Содержание

Введение

1. Сведения о графах

2. Внутреннее представление графов

3. Основные понятия

4. Алгоритм Флойда

1. 5. Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин

6. Задача Флойда

7. Описание программы

Поиск кратчайших путей.

8. Листинг программы

Заключение

Список литературы

Введение

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
    Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии),также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

1. Сведения о графах

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

Большое значение в теории графов имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конеч­ным множеством вершин и ребер, как правило, пробле­ма существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение мно­гих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допусти­мых вариантов. Однако таким способом удается ре­шить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, на­ходящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока.

Результаты и методы теории графов применяются при реше­нии транспортных задач о перевозках, для нахож­дения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управ­лении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в пост­роении различных дискретных устройств, в програм­мировании и т. д.

   Граф G (рис.1) задается множеством точек (вершин) х₁, х₂,..., х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом, (рис.2).
   

Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.
    Если ребра не имеют ориентации, то граф называется неориентированным (рис 3), (двухстороннее движение).
    В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х₁ ,х₃) относится к дуге а₁.
    Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рис. 2:
    Г (х₁)={х₂, х₃}, т.е. вершины х₂ и х₃ являются конечными вершинами дуг, у которых начальной вершиной является вершина х₁.
   

На рис. 3: Г (х₁)={х₂, х₄, х₅}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.)
   Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Так, на рис. 5 последовательности дуг

а₆, а₅, а₉, а₈, а₄. (1)
а₁, а₆, а₅, а₉. (2)
а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

являются путями.
   

Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а₆ в нем используется дважды.
   Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.
   Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер ?₁, ?₂,..., ?_q, в которой каждое ребро а_q за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

?₂, ?₄, ?₈, ?₁₀, (4)
?₂, ?₇, ?₈, ?₄, ?₃, (5)
?₁₀ , ?₇ , ?₄ , ?₈ , ?₇ , ?₂. (6)

в графе, изображенном на рис. 5, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆. Иногда дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (?₁, ?₂,..., ?_q), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.



   Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости/длины), задаваемые матрицей С=[c_ij]. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины sx до заданной конечной вершины tx, при условии, что такой путь существует tR(s) (здесь R(s)-множество, достижимое из вершины s.) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi- некоторая его вершина, то, двигаясь от s к х_i, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым () весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
   Следующие задачи являются непосредственными обобщениями сформулированной выше задачи о кратчайшем пути.
1)Для заданной начальной вершины s найти кратчайшие пути между s и всеми другими вершинами х_iX.
2)Найти кратчайшие пути между всеми парами вершин.
Почти все методы, позволяющие решить задачу о кратчайшем (s-t)-пути, дают также (в процессе решения) и все кратчайшие пути от s к х_i. Таким образом, они позволяют решить задачу с небольшими дополнительными вычислительными затратами. С другой стороны, задача №1 может быть решена либо n-кратным применением алгоритма задачи №2, причем на каждом шаге в качестве начальной вершины s берутся различные вершины, либо однократным применением специального алгоритма.
Наиболее распространенные методы их решения – это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k – кратчайших путей в графе).

2. Внутреннее представление графов

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

Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.

Списки вершин и ребер

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

Списки смежности

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

Матрицы смежности

Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин).

Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее "дорогой" операцией при использовании динамических массивов является добавление элемента, поскольку в худшем случае для этого требуется выделить новый блок памяти увеличенного размера, скопировать содержимое старого блока памяти в новый и освободить старый блок, причем, по крайней мере, этап копирования имеет сложность O(n). В то же время, в среднем операция добавления вершин (ребер) в AGraph выполняется более эффективно. Это достигается за счет того, что при увеличении размера динамического массива (вектора) в библиотеке Vectors память выделяется сразу для нескольких элементов, поэтому в большинстве случаев операция добавления элемента не требует фактического изменения размера вектора.

3. Основные понятия.

Граф без циклов называется ациклическим или лесом.

Связный ациклический граф называется деревом.

Если G-лес, то каждая его компонента является деревом.

Остов графа – это дерево, являющееся остовным подграфом.

Остовной подграф – это подграф, множество вершин которого совпадает с множеством вершин графа.

Любой связный граф имеет остов. Обратно, если граф имеет остов, то он – связный.

Если граф имеет циклы, то, последовательно удаляя ребра из циклов до получения ациклического подграфа, получим остов. Причем, удаление ребра из цикла графа не нарушает его связности, т.к. такие ребра не являются мостами.

Ребро x и вершина v называются покрывающими друг друга, если они инцидентны. Множество вершин, покрывающих все ребра, называется вершинным покрытием графа. Множество ребер, покрывающих все вершины, называется реберным покрытием графа. Представляет интерес наименьшие по числу вершин и ребер покрытия. Если ребрам графа приписаны веса, то можно ставить вопрос о реберном покрытии, имеющем наименьший суммарный вес.

Постановка задачи.

Пусть G=(V,X)-связный взвешенный граф. Обозначим c_ij=c(v_i,v_j) вес ребра {v_i,v_j}. Требуется найти остов, имеющий наименьшую сумму весов ребер. Пример.

Алгоритм решения.

1. Включить в остов одну произвольную вершину w. Пример.

2. Рассмотреть все вершины v_j, еще не принадлежащие остову. Если вершина v_j не смежна вершине w, принадлежащей остову, то она получает метку [0;М], где М- бесконечно большое число. Если вершина v_j имеет смежную вершину w,которая принадлежит остову, то вершина получает метку [a ;b ], где a=номер вершины w; b = c(w,v_j); Пример.

3. Из всех вершин, не принадлежащих еще остову, выбираем вершину V* с минимальным значением b и включаем ее в остов вместе с ребром (v,V*), где v- вершина, номер которой совпадает со значением метки a вершины V*.Пример.

4. Если число вершин, принадлежащих остову, равно числу вершин графа, то кратчайший остов найден, задача решена. Пример. Иначе – перход к шагу 5. Пример.

5. Корректируем метки вершин v_j, которые еще не принадлежат остову и смежны вершине V*:

если b _j > c(V*,v_j),

то b _j = c(V*,v_j)

a _j = V*,

если b _j <= c(V*,v_j), то метка вершины не изменяется.

После окончания помечивания – переход к пункту 3. Пример.

Пример.

Задание.



Пункт 1.



Пункт 2.



Пункт 3.



Пункт 4.



Пункт 5.



Результат.



4. Алгоритм Флойда

Присвоить c_ij=0 для всех i=1,2,...,n и c_ij=, если в графе отсутствует дуга (x_i x_j).
    Присвоение начальных значений.
    Шаг 1. присвоить k=0;
    Шаг 2. k=k+1.
    Шаг 3. Для всех i<>k, таких, что c_ik<>, и для всех j<>k, таких, что c_ik<>,
с_ij= [min[c_ij, (c_ik+ c_kj)]. (9)
    Проверка на окончание.
    Шаг 4. Если k=n, то матрица [с_ij] дает длины всех кратчайших путей.
    Остановка. Иначе перейти к шагу 2.
   На практике часто требуется найти не только кратчайший путь, но также второй, третий и т. д. кратчайшие пути в графе. Располагая этими результатами, можно решить, какой путь выбрать в качестве наилучшего. Для решения этой задачи нужно воспользоваться методом Йена (1971г.). Для которого: t-k-й кратчайший путь от s к t, где -соответственно 2-я, 3-я,…, qk-я вершины k-го кратчайшего пути. P_i^k- "отклонение от пути P^k-1 в точке i" т. е. P_i^k -кратчайший из путей, совпадающих с P_i^k-1 от s до i-й вершины, а затем идущий к вершине, отличной от (i+1)-х вершин тех (ранее уже построенных) кратчайших путей Pⁱ (j=1,2,…,k-1), которые имеют те же самые начальные подпути от s к i-й вершине, не проходящему ни через одну из вершин s, x₂^k-1, x₃^k-1,..., x_i^k-1участвующих в формировании первой части пути P_i^k. Отсюда следует, что путь P_i^k будет являться простой цепью (путь, в котором каждая вершина используется не более одного раза.).
   Первый подпуть s, x₂^k, x₃^k,..., x_i^k (совпадающий с s, x₂^k-1, x₃^k-1,..., x_i^k-1) пути P_i^k называется его корнем и обозначается R_i^k, а второй подпуть x_i^k,...,t пути P_i^k называется ответвлением и обозначается через S_i^k.
   Алгоритм начинает работу с нахождения P¹ с помощью алгоритма Дейкстры. Этот путь помещается в список L₀ (который должен содержать k-е кратчайшие пути). В общем случае для нахождения P^k нужно уже иметь кратчайшие пути P¹,P², P^k-1.

1. 5. Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин

Процедура находит пути минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент w_{i j} равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.

Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W[i,j]- симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

D⁰=W

d^m+1[i,j]=min{d^m[i,j], d^m[i,(m+1)] + d^m[(m+1),j]}, где i<>j; d^m+1[i,i]=0.

преобразование проделывается для m=1..n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное d^m[i,m]+d^m[m,i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i, если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

Заметим, что если граф неориентированный, то W а также все матрицы получаемые в результате преобразований симметричны и следовательно достаточно вычислять только элементы расположенные выше главной диагонали.

6. Задача Флойда

Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.    Инициализация:    1. Построим матрицу D⁰ размерности |V| x |V|, элементы которой определяются по правилу:

1. d_ii⁰= 0;

2. d_ij⁰= Weight(v_i, v_j), где i<>j, если в графе существует ребро (дуга) (v_i, v_j);

3. d_ij⁰= бесконечность , где i<>j, если нет ребра (дуги) (v_i, v_j).

2. m:=0.    Основная часть:    1. Построим матрицу D^m+1 по D^m, вычисляя ее элементы следующим образом:
d_ij^m+1=min{d_ij^m, d_i(m+1)^m + d_(m+1)j^m}, где i<>j; d_ii^m+1=0 (*).
Если d_im^m + d_mi^m < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину v_i; ВЫХОД.    2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D^|V| равны длинам кратчайших путей между соответствующими вершинами; Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов p_ij=i. Каждый раз, когда на шаге (1) значение d_ij^m+1 будет уменьшаться в соответствии с (*) (т.е. когда d_i(m+1)^m + d_(m+1)j^mij^m), выполним присваивание p_ij:=p_(m+1)j. В конце работы алгоритма матрица P будет определять кратчайшие пути между всеми парами вершин: значение p_ij будет равно номеру предпоследней вершины в пути между i и j (либо p_ij=i, если путь не существует).    Примечаниe: если граф - неориентированный, то все матрицы D^m являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали.

7. Описание программы

Поиск кратчайших путей.

Описание алгоритма:
Над матрицей A (NxN) выполняется n итераций. После k-ой итерации, A[i,j] содержит значение наименьшей длинны путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k.
На k-ой итерации для вычисления матрицы A, используется слудующая формула:
Ak[i,j] = min (Ak-1[i,j], Ak-1[i,k]+ Ak-1[k,j]).
Сложность алгоритма
Время выполнения программы, имеетпорядок O(n3), так как в ней нет практически ничего, кроче 3 вложенных друг в друга циклов.
Сохранение маршрутов.
Что бы сохранять маршруты, от одной вершины кдругой, следует, ввести еще одну матрицу, в которой каждому элементу P[I,j]присваивать вершину K (номер), полученную при нахождении наименьшего значения a[I,j].

8. Листинг программы

Program Algoritm_Floyda;

Const
NN=100;
Type
Graph = array[1..nn,1..nn] of longint; {граф задан матрицей смежности}
Var
n:integer;
Procedure Floyd (var a:graph; c:graph; var p:graph);
var i,j,k:integer;
begin
for i:=1 to n do
for j:=1 to n do begin a[i,j]:=c[i,j]; p[i,j]:=0; end;
for i:=1 to n do a[i,i]:=0;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
If (a[i,k]+a[k,j] begin
a[i,j]:=a[i,k]+a[k,j];
p[i,j]:=k;
end;
end;

procedure ReadGraph(var a:graph);
var
i,j:integer;
begin
write('n= ');readln(n);
For i:=1 to n do for j:=1 to n do
begin write('G',i,',',j,'= ');readln(a[i,j]); end;
writeln;
end;

procedure ReadFileGraph(var a:graph);
var
i,j:integer; filename:string; f:text;
begin
Write('Enter file name:'); readln(filename);
Assign (f,filename); reset(f);
Readln(f,N);
For i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f);
end;

var
a,c,p:graph;
i,j:integer;
begin
{ ReadGraph( c );}
ReadFileGraph( c );
floyd(a,c,p);
writeln('---------------------------');
for i:=1 to n do {
begin
for j:=1 to n do write(a[i,j]:3);
writeln
end;
writeln('---------------------------');
for i:=1 to n do
begin
for j:=1 to n do write(p[i,j]:3);
writeln
end;
readln;
end.

В программе C-граф, заданный матрицей смежности.
A- матрица содержащая кратчайшие пути.
P - матрица, сохраняющая маршруты

Заключение

Графы в большой степени сохраняют своё наглядное, геометрическое содержание как системы точек, соединённых линиями. Ознакомление с новым материалом на основе этих данных не даст им запутаться в незнакомых понятиях и позволит хорошо усвоить и применять на практике полученные знания. Будет способствовать усвоению данного курса и то, что основы теории графов связаны с изучаемыми в средней школе математическими и естественнонаучными предметами. Это даёт возможность, кроме получения новых знаний, глубже и лучше освоить и понять другие предметы школьной программы. Процесс обучения современного человека не заканчивается в школе или вузе. Он становится непрерывным. Системы непрерывного образования – это насущная потребность каждого человека. Поэтому уже в настоящее время возникла необходимость не только в общем обучении, но и в дистанционном, на основе современных компьютерных технологий (как ознакомление с ними, так и непосредственное их использование в решении поставленных задач ). Благодаря наличию дидактических свойств компьютерные телекоммуникации являются исключительно современными и перспективными для использования в сфере образования. В современном интегрированном сообществе учащиеся уже не могут учиться изолированно, ограничиваясь традиционными, достаточно замкнутым социумом: учителя, друзья, семья.

Список литературы

1. Белов Теория Графов, Москва, «Наука»,1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.

2. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

3. Оре О. Теория графов. – М.: Наука, 1980.

4. Ж.-Л. Лорьер. Системы искусственного интеллекта. – М.: Мир, 1991.

5. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1978.

10. http://www.vbstreets.ru/default.asp?page=library&type=old&id=volna
11. http://www.devel.vcity.ru/library.tmpl?05344_article_id=8
12. http://www.ergeal.ru/txt/archive/cs/discra/index.htm
13. http://www.algolist.manual.ru/links/
14. http://www.caravan.ru/~alexch/graphs
15. http://www.encycl.yandex.ru/