ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ. - Теория Графов - Математика - Каталог статей

Главная » Статьи » Математика » Теория Графов

ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ.

ЗАДАЧИ НА ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ. В данном параграфе будут рассмотрены некоторые задачи, при решении которых используется теория графов. Они считаются классическими. Задача 4.1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств: 1. учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; 2. учитель литературы может дать один, либо второй, либо третий урок; 3. математик готов дать либо только первый, либо только второй урок; 4. преподаватель физкультуры согласен дать только последний урок. Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы? Решение. Без сомнения, эту задачу можно решить путем обыкновенного перебора всех возможных вариантов, но решение будет наиболее простым, если вычертить граф в виде дерева. Требуемый граф изображен на рисунке 4.1. На нем выделены три возможных варианта расписания уроков. (РИСУНОК 4.1) Данная задача является классическим примером удачного использования теории графов. В настоящее время существует программа "Расписание 3.0" компьютерной фирмы ЛинTex, в которой она решена с использованием современных технологий. Рассмотрим еще одну задачу, решением которой также является граф. Задача 4.2. В составе экспедиции должно быть 6 специалистов: биолог, врач, синоптик, гидролог, механик и радист. Имеется 8 кандидатов, из которых и нужно выбрать участников экспедиции; условные имена претендентов: A, B, C, D, E, F, G и H. Обязанности биолога могут исполнять E и G, врача – A и D, синоптика – F и G, гидролога – B и F, радиста – С и D, механика – C и H. Предусмотрено, что в экспедиции каждый из них будет выполнять только одну обязанность. Кого и в какой должности следует включить в состав экспедицию, если F не может ехать без B, D – без H и C, C не может ехать вместе с G, A – вместе с B ? Решение. Процесс решения задачи во всех подробностях мы рассматривать не будем. Заметим только, что задать возможный вариант решения, то есть описать точный состав экспедиции, можно с помощью четного графа, в котором вершины разделены на две группы, а ребра могут соединять лишь вершины разных групп. Применительно к задаче об экспедиции одна группа вершин есть группа из 8 кандидатов, а вторая – из 6 должностей. Задача 4.3. Планета имеет форму выпуклого многогранника, причем в его вершинах расположены города, а каждое ребро является дорогой. Две дороги закрыты на ремонт. Докажите, что из любого города можно проехать в любой другой по оставшимся дорогам. Решение. Пусть A и B – данные города. Докажем сначала, что из A в B можно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую, не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются). Пусть A' и B' – проекции точек A и B, а M' и N' – крайние точки проекции многогранника (в точки M' и N' проецируются вершины M и N). Если идти из вершины A так, что в проекции движение будет происходить по направлению от M' к N' , то, в конце концов, мы обязательно попадем в вершину N. Аналогично из вершины B можно пройти в N. Таким образом, можно проехать из A в B (через N). Если полученный путь из A и B проходит через закрытую дорогу, то есть еще два объезда по граням, для которых это ребро является общим. Вторая закрытая дорога не может находиться сразу на двух этих объездах. Значит, из города A в город B можно проехать, по крайней мере, одним путем. Итак, в данном параграфе рассмотрены некоторые задачи, для решения которых применяется теория графов. В §5 мы приведем условия и решения задач школьного курса математики.
1 2 3 4 5 Категория: Теория Графов \| Добавил: alexlat (25.04.2012)
Просмотров: 5766 \| Рейтинг: 0.0/0