Применение графов в экономике

Содержание

Введение

1. Рассмотреть общие представления о графах

1.1 Исторические сведения

1.2 Понятия теории графов

1.3 Основные определения

2. Виды графов

2.1 Примеры графов

2.2 Матричное задание графов. Матрицы смежности и инцидентности

2.3 Связность. Компоненты связности

3. Задачи решаемые с помощью графов

3.1 Задача коммивояжера

3.2 Задача о четырех красках

3.3 Задача о домиках и колодцах

Заключение

Список использованной литературы

Введение

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

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

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

Учитывая вопрос актуальности данной работы нами была поставлена цель - исследовать применение графов в экономике

Объектом исследования является графы.

Предметом - экономика.

Для достижения цели нами сформулированы следующие задачи:

1. Рассмотреть общие представления о графах

2. Дать характеристику различным видам графа

3. Изучить применение графов в экономике.

4. Подвести итоги и сделать выводы.

1. Общее представление о графах

1.1 Исторические сведения

Введения термина «граф» приписывается известному венгерскому математику Д.Кенигу (1884-1944) автору одной из первых книг по теории графов (1936г.) Однако имеются и более ранние работы (статьи как самого Кенига , так и других авторов), где используется это название.

Теория графов - раздел дискретной математики, рассматривающий множества с заданными на них отношениями между элементами. Объекты такого рода могут быть наглядно представлены в виде рисунков, состоящих из точек, кружочков или иных фигур, соединенных линиями. При этом точки соответствуют элементам множества. А линии отражают связи (отношения) между ними. Подобные рисунки обычно и называют графами, хотя соответствующее понятие шире, а рисунок лишь одна из форм представления графа.

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

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

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

Л.Эйлер (1707-1783) - великий швейцарский, немецкий и российский математик.

У.Гамильтон (1805-1865) - ирландский математик, физик и механик.

А.Кэли (1821-1895) - английский математик который исследовал деревья в связи с химическими структурными формулами.

Г.Киргхоф (1824-1887)- выдающийся немецкий физик

Р.Прим (1921) американский математик, чьё имя носит один из алгоритмов построения кратчайшего остова графа.

1.2 Понятия теории графов

Пусть дано множество Х, которое состоит из элементов, называемых точками. Дан закон, позволяющий установить соотношение Т между каждым элементом множества Х и некоторыми из его подмножеств. Обозначим через Тх некое подмножество множества Х, отвечающее элементу х множества Х. Две математические величины - «множество Х» и «соответствие Т» - определяют граф G, обозначаемый как G = (X, T). Элементы множества Х будем изображать точками, и называть вершинами графа. Соотношения Т будем изображать отрезками (иногда ориентированными), соединяющими элемент с элементами подмножества Тх, и называть ребрами или дугами графа. Граф G называется конечным, если число его вершин конечно. На рис.1 показан граф, определяемый множеством

X = {x0, x1, x2, x3, x4, x5}.



Рисунок 1. Граф определяемый множеством вершин

Рисунок 2 Нуль граф

Рисунок 3 Граф, определяемый множеством вершин Х = {a, b, c, d}

Соотношение Т характеризуется следующими равенствами:

Tx0 = {x0, x1, x2, x3, x4, x5}

Tx1 = {x0, x2}

Tx2 = {x0, x1, x3}

Tx3 = {x0, x2, x4}

Tx4 = {x0, x3}

Tx5 = {x0}

Пара вершин xi, xj образует ребро, если, либо точка xi принадлежит подмножеству Txj, либо xj принадлежит подмножеству Txi. Если всякая пара этих точек упорядочена, то такая пара определяет дугу графа и граф называется ориентированным (рис1.в). Две точки xi, xj называются смежными, если они определяют ребро или дугу графа. Две различные дуги являются смежными, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Если начальная и конечная точки пути совпадают, образуется контур. Длинна пути (контура) - это число дуг, которые его образуют. Петлей называется контур единичной длинны; петля связывает точку саму с собой. Граф называется связным, если для каждой пары вершин существует соединяющая их цепь (рис.1, в).

Граф называется полным, если любая пара его вершин соединена ребром.

Рисунок 4. а) Пример полного графа б) Изоморфный ему граф

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

1.3 Основные определения

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

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

Граф называется ориентированным, если указано направление дуг



Рисунок 5. Ориентированный граф неориентированным, если такое направление не указано

Рисунок 6. Неориентированный граф

Примером неориентированного графа является карта дорог

Граф называется петлей, если его начало и конец совпадают.



Рисунок 7. Граф петля

Например дуги а2 и а5 являются петлями

Ориентированный граф называется сильно связанным или сильным, если для любых двух различных вершин xt и xf существует, по крайней мере, один путь, соединяющий xt и xf .

Рисунок 8. Сильно связный граф



Рисунок 9. Не связный граф

Граф, который не является связанным, может быть разбит на конечное число связных графов, называемых компонентами, или частями

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

Рисунок 10. Пути и маршруты графа.

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

Подграфом Ga графа G называется граф, в который входит лишь часть вершин графа G вместе с дугами их соединяющими.

Частным графом Gb графа называется граф, в который входит лишь часть дуг графа G вместе с вершинами их соединяющими. Карта шоссейных дорог это граф. Дороги Саратовской области это подграф, а главные дороги - это частный граф .

Пусть дан граф G=(X,A). Остовным подграфом Gp графа называется граф(X, Ap) для которого Ap A. Таким образом остовый подграф имеет тоже самое множество вершин, что и граф G, но множество дуг подграфа Gp является подмножеством множества дуг исходного графа.

Рисунок 11. а) Граф, б)Остовной граф, в) Порожденный граф, г) Подграф.

2. Виды графов

2.1 Примеры графов. Операции над графами

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v1, v2, если оно соединяет эти вершины и наоборот, каждая из вершин v1, v2 инцидентна ребру е.

Рассмотрим графическое представление графов таблица 1.

Таблица 1. Графическое представление графов

№	Элементы графов	Геометрические элементы
1.	х Х - вершина	- точка в пространстве
2.	(vi, vj) V (vi, vj) V	- направленный отрезок, ориентированное ребро
3.	(vi, vj) V (vi, vj) V	- отрезок, неориентированное ребро
4.	(vi, vi) V	- замкнутый отрезок, петля

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

Рассмотрим некоторые важные типы графов.

Определение. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают N

Заметим, что у вполне несвязного графа все вершины изолированы

Определение. Простой граф, в котором любые две вершины смежны, называется полным. Полный граф обозначают K

Заметим, что для полного графа выполняется равенство

,

где m - число ребер, n - число вершин графа.

Определение. Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n.

Регулярные графы степени 3 называются кубическими (или трехвалентными).

Известным примером кубического графа является граф Петерсона

Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и ребрами пяти правильных многогранников - Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.На рисунке 6 приведен граф, соответствующий кубу.

Определение. Допустим, что множество вершин графа G можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-нибудь вершиной из V2, тогда данный граф называется двудольным.

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

Определение. Если в двудольном графе каждая вершина из V1 соединена с каждой вершиной из V2, то граф называется полным двудольным.

Заметим, что граф Кm. n имеет ровно m + n вершин и mn ребер.

Определение. Объединением графов

называется граф

Определение. Пересечением графов

,

где ,

называется граф

Определение. Соединением графов G1 и G2 является новый граф, у которого

V=V1V2

а множеством ребер являются все ребра первого и второго графа и ребра, соединяющие между собой каждую вершину первого графа с первой вершиной второго графа.

Определение. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

Очевидно, что всякий несвязный граф можно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой связности графа.

Определение. Связный регулярный граф степени 2 называется циклическим графом. Обозначается Сn .

Определение. Соединение графов N1 и Cn-1 (n3) называется колесом с n вершинами. Обозначается Wn (рисунок 10)

Определение. Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

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

Определение. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа.

2.2 Матричное задание графов. Матрицы смежности, инцидентности

Пусть D = (V, Х) - орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Определение. Матрицей инцидентности орграфа D называется (nm) -матрица B(D)=[bij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть

G = (V, X) - граф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (nm) -матрица B(G)=[bij], у которой

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

Построить матрицы смежности и инцидентности для графа G = (V, X)

Решение

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

.

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

Рисунок. Матрица инцидентности имеет вид

Напомним, что в строках указываются вершины, в столбцах - ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.

2.3 Связность. Компоненты связности

Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь из v в w(маршрут, соединяющий v, w).

Дадим более удобное определение связных графов.

Определение. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w. Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).

Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере, одна достижима из другой.

Определение. Если граф не является связным, то он называется несвязным.

Определение. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.

В дальнейшем количество компонент связности графа будем обозначать k.

Данный граф не является связным: k = 3.

Данный граф является связным: k = 0.

Теорема. Пусть G - простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам

Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.

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

Определение. Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющейся.

Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.

Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.

Определение. Разрез, состоящий из одного ребра, называется мостом (перешейком).

3. Задачи решаемые с помощью графов

3.1 Задача Коммивояжера

Коммивояжер должен объездить n городов. Для того чтобы сократить расходы, он хочет построить такой маршрут, чтобы объездить все города точно по одному разу и вернуться в исходный с минимумом затрат.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {cij}, где cij ?0 - длинна (или цена) дуги (i, j),

.

Под маршрутом коммивояжера z будем понимать цикл i1, i2,…, in, i1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z - множество всех возможных маршрутов. Начальная вершина i1 - фиксирована. Требуется найти маршрут z0 Z, такой, что l(z0)= min l(z), z Z.

Решение задачи

Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу ц длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е.

ц(Z)? ц (), ц(Z) ? ц ().

Сравнивая нижние границы ц () и ц (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

3.2 Задача о четырех красках

Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом рисунок 22. С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно - объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

3.3 Задача о домиках и колодцах

Задача: Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу. Дорожки не могут проходить через колодцы и домики рисунок 22



Рисунок. Задача о домиках и колодцах.

Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году, которая является одной из основных в теории графов. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство

В - Р + Г = 1, (*)

где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).

Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ рисунок 23



Действительно, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем

В - (Р + 1) + (Г+1) = В - Р + Г.

Пользуясь этим свойством, проведем диагонали, разбивающие входящие многоугольники на треугольники, и для полученного разбиения покажем выполнимость соотношения (*) рисунок 24

Для этого будем последовательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:

для удаления треугольника ABC требуется снять два ребра, в нашем случае AB и BC;

для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.

В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:

(В - 1) - (Р + 2) + (Г -1) = В - Р + Г.

Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого разбиения В = 3, Р = 3, Г = 1 и, следовательно,

B - Р + Г= 1.

Значит, равенство (*) имеет место и для исходного разбиения, откуда окончательно получаем, что для данного разбиения многоугольника справедливо соотношение (*).

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

Приступим теперь к решению задачи о трех домиках и трех колодцах.

Решение. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3 (рис. 1). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера

В - Р + Г= 1.

Добавим к рассматриваемым граням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид

В - Р + Г = 2,

причем В = 6 и Р = 9.

Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5*4)/2 = 10, что противоречит условию, по которому их число равно 9.

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

Заключение

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

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

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

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

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

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

Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН, 1994, 172 с.

Вентцель Е.С., Овчаров Л.А. Теория вероятностей. - М.: Наука, 1969, 367 с.

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

Гнеденко Б.В. Курс теории вероятностей. - М.: Наука, 1988, 448 с.

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

Зубков А.М., Севастьянов Б.А., Чистяков В.П. - Сборник задач по теории вероятностей. - М.: Наука, 1989, 320 с.

Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ, 1995, 24 с.

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

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

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

Нефедов В.H., Осипова В.А. Куpс дискpетной математики. - М.: МАИ, 1992, 264 с.

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

Нечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990, 515 с.

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

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

Писсанецки С. Технология разреженных матриц. - М.: Мир, 1988, 412 с.

Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977, 352 с.

Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992, 176 с.

Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992, 32 с.