Обзор литературы icon

Обзор литературы



НазваниеОбзор литературы
Дата17.10.2016
Размер
ТипОбзор

Обзор литературы


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

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

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

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


В математической литературе, посвященной теме «Графы», также в содержании рассматриваются следующие теоретические вопросы:

определяются все основные понятия теории графов: вершины, ребра, понятие гомеоморфизма и планарности графов, связность, свойства графов (эти вопросы освещаются в каждой книге списка литературы);

  1. история возникновения теории графов (задача о Кенигсбергских мостах, впервые описанная Леонардом Эйлером);

  2. частные виды графов (маршруты, цепи, циклы, деревья, простые графы и мультиграфы, планарные графы, двудольные графы);

  3. операции над графами (объединение, произведение, композиция).

В книгах, предназначенных для изучения в вузах вопросы теории графов рассматриваются наряду с вопросами об изоморфизме графов и инвариантах графов; исследуется возможность матричного представления графов; характеризуется вопрос о трансвесалях и паросочетаниях [1].

Так как цель нашего исследования была определена следующим образом: «Используя теорию графов научиться решать практические и прикладные задачи», то особо остановимся на характеристике направлений возможностей применения теории графов для решения задач практики и задач, появляющихся в естественных дисциплинах. Для этого мы используем работы О. Оре [2], О.И. Мельникова [3].

Наиболее подробно и ясно для школьников приложения теории графов охарактеризованы в работе О. Оре [2]. В ней описаны следующие задачи:

- о составлении расписания игр команд по футболу;

- о составлении карты дорог, соединяющих населенные пункты;

- об изображении фигур без отрыва ручки от листа бумаги единым росчерком (об уникурсальных кривых);

- о соединении городов;

- о назначении на должности;

- об одностороннем движении;

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

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

- задача кратчайшего пути;

- задача минимизации дерева расстояний;

- задача максимального потока в сети;

- задача управления комплексом взаимосвязанных работ и др.

Связывая графы с прикладными задачами мы можем легко решать задачи из области химии (задачи о возможных структурах насыщенных /предельных углеводородов), информатики (задачи о построении оптимального кода), биологии (теории ветвящихся процессов, таких как размножение бактерий), физики (конструирование печатных схем) [4].

Обзор литературы по данному вопросу позволил сделать ряд выводов:

1) теория графов – эффективный аппарат для решения практических и прикладных задач. Умение применять эту теорию даёт возможность решать нестандартные задачи оригинальным и в то же время простым и удобным способом;

2) благодаря применению теории графов открывается широкая возможность использования оригинальных, но в то же время очень простых способов решения задач олимпиадного и занимательного уровня;

3) теория графов может служить методом решения некоторых типов прикладных и практических задач, встречающихся в современной школьной практике, которые в рассматриваемой литературе охарактеризованы недостаточно;

4) в проанализированных работах не рассматривается вопрос о возможностях применения компьютерных технологий для решения задач теории графов.


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

  1. М.В. Мещеряков «Избранные лекции по дискретной математике. Часть I. Комбинаторика и графы», Саранск: Изд-во Мордов. ун-та, 2003.

  2. О. Оре «Графы и их применение», Москва: Издательство «Мир», 1965.

  3. О.И. Мельников «Занимательные задачи по теории графов», Мн.: «ТетраСистемс»,2001.

  4. Интернет ресурс: http://tarefer.ru/works/50/100251/index.html



Похожие:

Обзор литературы icon2. Определение понятй способности, одарённость, талант. Структура таланта
...
Обзор литературы iconТема «Организация развивающей, познавательной, исследовательской среды в образовательном учреждении» Из опыта работы
Теоретическая часть. Обзор изученных источников информации (педагогической литературы, Интернет-источников, нормативных документов...
Обзор литературы icon«История отечественного государства и права». Планы семинаров и список учебной литературы для студентов 3 курса параллельного обучения по специальности «Юриспруденция» Учебная литература
Владимирский –Буданов М. Ф. Обзор истории русского права. Ростов-на-Дону. М.,1995
Обзор литературы icon«История отечественного государства и права». Планы семинаров и список учебной литературы для студентов 1 курса дневного обучения по специальности «Юриспруденция» Учебная литература
Владимирский –Буданов М. Ф. Обзор истории русского права. Ростов-на-Дону. М.,1995
Обзор литературы icon«История отечественного государства и права». Планы семинаров и список учебной литературы для студентов дневного ускоренного обучения ( двиот) по специальности «Юриспруденция» Учебная литература
Владимирский –Буданов М. Ф. Обзор истории русского права. Ростов-на-Дону. М.,1995
Обзор литературы iconОбзор литературы 7
Дипломный проект посвящен разработке системы передачи данных из ультразвуковой медицинской диагностической установки, а также получением...
Обзор литературы icon2. Обзор литературы по данному вопросу
Речь важнейшая творческая психическая функция человека, область проявления, присущая всем людям, способность к позна­нию, самоорганизации,...
Обзор литературы iconДети с общим недоразвитием речи. Обзор литературы
Общее недоразвитие речи (онр) — различные сложные речевые расстройства, при которых нарушено формирование всех компонентов речевой...
Обзор литературы icon1. Теоретический обзор литературы по проблеме факторов успешной учебной деятельности младших школьников
Влияние учителя младших классов на формирование успешной учебной деятельности
Обзор литературы iconМетодическая папка по курсу «История древней русской литературы» преподаватель: Царева В. П
Основные этапы изучения древнерусской литературы. Ученые-медиевисты, характеристика 2-3 работ, проблема периодизации русской средневековой...
Разместите ссылку на наш сайт:
Справочники, творчество


База данных защищена авторским правом ©dmee.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
контакты