Реферат на тему: Теория Графов. Мадрахимова Виола 1-курс 100а приняла

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


Задача 1. Необходимо составить фрагмент расписания для одного дня с
учетом следующих обстоятельств:
1. учитель истории может дать либо первый, либо второй,
либо третий уроки, но только один урок;
2. учитель литературы может дать один, либо второй, либо третий урок;
3. математик готов дать либо только первый, либо только второй урок;
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?
Решение Вершины графа могут соединяться не только линиями, но и стрелками. Такие члены экспедиции, которые не могут ехать без других, причем в определенном графе ребра называются ориентированными. В данном графе черными стрелками указаны члены, которые не могут ехать друг без друга, а розовыми стрелками(A-B, C-G) – члены экспедиции, которые не могут ехать совместно
В результате решения задачи получили следующий состав экспедиции:
Радист – С, врач – D, гидролог – В, синоптик – F, биолог – Е, механик – Н.

Задача 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 можно проехать, по крайней мере и, т. е. вершинами с нечетной степенью.