Задачи на графы Задачи



Дата08.03.2018
өлшемі445 b.
#60564
түріЗадача


Задачи на графы


Задачи

  • Задача 1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств:

  • учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок;

  • учитель литературы может дать один, либо второй, либо третий урок;

  • математик готов дать либо только первый, либо только второй урок;

  • преподаватель физкультуры согласен дать только последний урок.

  • Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?



Граф по условию задачи



Преобразуем граф в дерево 1



Преобразуем граф в дерево 2



Преобразуем граф в дерево 3



Решение задачи - лес



Задачи

  • Задача 2. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?







Решение

  • Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности

  • Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены



Задачи

  • Задача 3. В составе экспедиции должно быть 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. В районе имеется 6 населенных пунктов. В одном из них необходимо открыть пункт скорой помощи, с таким условием, чтобы расстояние от этого населенного пункта было минимальным для всех. Известно время переезда туда и обратно для любого населенного пункта, соединенного дорогами.





Дороги на графе



Время туда



Время туда и обратно







Достарыңызбен бөлісу:




©stom.tilimen.org 2022
әкімшілігінің қараңыз

    Басты бет