Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский Государственный инженерно-экономический университет»

Филиал в г. Чебоксары

Факультет финансов и бухгалтерского учета

Кафедры финансов и банковского дела

Реферат

по дисциплине «Математика»

На тему: «Орграфы, теория и применение»

Выполнила:

Студентка группы 32-08

Рассанова Мария

Научный руководитель:

Качевский

Дмитрий Николаевич

Чебоксары 2009

Содержание

Введение

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

·  Связность

·  Дополнительные определения

·  Применение орграфов

Глава 2. Теория графов

·  Определения

·  Способы задания графов

·  Связность

·  Планарность

·  Матричное представление графов

·  Орграфы и соединимость

·  Орграф и его конденсация

·  Ориентированная двойственность и бесконтурные орграфы

·  Слабый функциональный орграф

Заключение

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

ВВЕДЕНИЕ

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

Наиболее известные работы в этой области принадлежат Кристофидесу Н., Басакеру Р.Д., Харари Ф., Бержу К., Дейкстре Э., Флойду Р., Замбицкому Д.К., Оре О., Саати Т., Фалкерсону Д.Р., Форду Л.Р.

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

В работах Ерусалимского Я.М., Басанговой Е.О., Логвинова С.Ю., Скороходова В.А., Петросяна А.Г. описаны различные виды ограничений на достижимость. Так, Ерусалимским Я.М. и Басанговой Е.О. рассмотрено несколько видов достижимости на частично-ориентированных графах, на которых присутствуют ориентированные и неориентированные ребра. Введено понятие смешанной цепи, на дуги и звенья которой накладываются различные условия, в зависимости от вида ограничений. ............