Задачи на графы |
| Комбинаторика | ||
| << Определение графа | Элементы комбинаторики: перестановки, сочетания и размещения >> |
Картинок нет |
Автор: Староверов. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока алгебры, скачайте бесплатно презентацию «Задачи на графы.ppt» со всеми картинками в zip-архиве размером 152 КБ.
Задачи на графы
содержание презентации «Задачи на графы.ppt»| Сл | Текст | Сл | Текст |
| 1 | Задачи на графы. | 11 | его ответу, рядом с ним стоит |
| 2 | Задачи. Задача 1. Необходимо составить | "лжец", что выполняется. Стоящий | |
| фрагмент расписания для одного дня с | в центре заявляет, что он | ||
| учетом следующих обстоятельств: учитель | "дипломат", и, следовательно, | ||
| истории может дать либо первый, либо | лжет (что возможно из условия), а стоящий | ||
| второй, либо третий уроки, но только один | справа также лжет. Таким образом, все | ||
| урок; учитель литературы может дать один, | условия задачи выполнены. | ||
| либо второй, либо третий урок; математик | 12 | Задачи. Задача 3. В составе экспедиции | |
| готов дать либо только первый, либо только | должно быть 6 специалистов: биолог, врач, | ||
| второй урок; преподаватель физкультуры | синоптик, гидролог, механик и радист. | ||
| согласен дать только последний урок. | Имеется 8 кандидатов, из которых и нужно | ||
| Сколько и каких вариантов расписания, | выбрать участников экспедиции; условные | ||
| удовлетворяющего всем вышеперечисленным | имена претендентов: A, B, C, D, E, F, G и | ||
| условиям одновременно, может составить | H. Обязанности биолога могут исполнять E и | ||
| завуч школы? | G, врача – A и D, синоптика – F и G, | ||
| 3 | Граф по условию задачи. 1. М. И. 2. Л. | гидролога – B и F, радиста – С и D, | |
| 3. 4. Ф. | механика – C и H. Предусмотрено, что в | ||
| 4 | Преобразуем граф в дерево 1. 1. М. И. | экспедиции каждый из них будет выполнять | |
| 2. Л. 1. М. 3. И. 2. 1. 4. Ф. Л. М. 3. И. | только одну обязанность. Кого и в какой | ||
| 2. Л. 4. Ф. 3. 4. Ф. | должности следует включить в состав | ||
| 5 | Преобразуем граф в дерево 2. 1. М. И. | экспедицию, если F не может ехать без B, D | |
| 2. Л. 1. 3. М. И. 2. 4. Ф. 1. Л. М. 3. И. | – без H и C, C не может ехать вместе с G, | ||
| 2. Л. 4. Ф. 3. 4. Ф. | A – вместе с B? | ||
| 6 | Преобразуем граф в дерево 3. 1. М. И. | 13 | Задачи. Решение. Процесс решения |
| 2. Л. 1. 3. М. И. 2. 4. Ф. 1. Л. М. 3. И. | задачи во всех подробностях мы | ||
| 2. Л. 4. Ф. 3. 4. Ф. | рассматривать не будем. Заметим только, | ||
| 7 | Решение задачи - лес. 1. 1. 1. М. М. | что задать возможный вариант решения, то | |
| М. И. 2. И. И. 2. 2. Л. Л. Л. 3. 3. 3. 4. | есть описать точный состав экспедиции, | ||
| Ф. 4. Ф. 4. Ф. | можно с помощью четного графа, в котором | ||
| 8 | Задачи. Задача 2. Из трех человек, | вершины разделены на две группы, а ребра | |
| стоящих рядом, один всегда говорит правду | могут соединять лишь вершины разных групп. | ||
| (правдолюб), другой всегда лжет (лжец), а | Применительно к задаче об экспедиции одна | ||
| третий, смотря по обстоятельствам, говорит | группа вершин есть группа из 8 кандидатов, | ||
| либо правду, либо ложь (дипломат). У | а вторая – из 6 должностей. Решение задачи | ||
| стоящего слева спросили: "Кто стоит | изображено на четном графе. | ||
| рядом с тобой?". Он ответил: | 14 | Граф. E. Б. G. D. В. A. С. F. G. B. Г. | |
| "Правдолюб". Стоящему в центре | F. Р. C. D. F. C. B. G. М. A. C. H. B. D. | ||
| задали вопрос: "Кто ты?", и он | H. B. Б – биолог; В – врач; С – синоптик; | ||
| ответил: "Я дипломат". Когда у | Г – гидролог; Р – радист; М – механик. F | ||
| стоящего справа спросили: "Кто стоит | не может ехать без B, D – без H и C, C не | ||
| рядом с тобой?", он сказал: | может ехать вместе с G, A – вместе с B? | ||
| "Лжец". Кто где стоял? | 15 | Задачи. Задача 4. В районе имеется 6 | |
| 9 | Правдолюб говорит только правду. Лжец | населенных пунктов. В одном из них | |
| всегда лжет. Дипломат либо лжет, либо нет. | необходимо открыть пункт скорой помощи, с | ||
| Рядом со мной лжец. Я дипломат. Рядом со | таким условием, чтобы расстояние от этого | ||
| мной правдолюб. | населенного пункта было минимальным для | ||
| 10 | 1. 2. 3. Л. Д. Л. Д. Л. Д. П. | всех. Известно время переезда туда и | |
| 11 | Решение. Если в данной задаче ребро | обратно для любого населенного пункта, | |
| графа будет соответствовать месту, | соединенного дорогами. | ||
| занимаемому тем или иным человеком, то нам | 16 | A(1,6). 20. 25. B(1,4). 30. 30. | |
| могут представиться следующие возможности | C(1,3). 45. 45. D(2,5). 40. 40. E(2,3). | ||
| Рассмотрим первую возможность. Если | 15. 15. F(3,6). 50. 50. G(5,6). 12. 12. | ||
| "правдолюб" стоит слева, то | H(4,5). 20. 16. I(3,4). 30. 25. Название | ||
| рядом с ним, судя по его ответу, также | дороги. Время туда. Время обратно. | ||
| стоит "правдолюб". У нас же | 17 | Дороги на графе. 1. 2. 6. 3. 5. 4. | |
| стоит "лжец". Следовательно, эта | 20,25. 15,15. 45,45. 50,50. 30,30. 12,12. | ||
| расстановка не удовлетворяет условию | 40,40. 30,25. 20,16. | ||
| задачи. Рассмотрев таким образом все | 18 | Время туда. 1. 2. 3. 4. 5. 6. 1. 0. 2. | |
| остальные возможности, мы придем к выводу, | 0. 3. 0. 4. 0. 5. 0. 6. 0. | ||
| что позиция "дипломат", | 19 | Время туда и обратно. 1. 2. 3. 4. 5. | |
| "лжец", "правдолюб" | 6. 1. 0. 2. 0. 3. 0. 4. 0. 5. 0. 6. 0. | ||
| удовлетворяет задаче. Действительно, если | 20 | . 1. 2. 3. 4. 5. 6. 1. 0. 2. 0. 3. 0. | |
| "правдолюб" стоит справа, то, по | 4. 0. 5. 0. 6. 0. Мин. | ||
| Задачи на графы.ppt | |||
Задачи на графы
«Теория графов» - Если f(е) = (x&x), то ребро называется петлей в вершине х. Определение смежности. Пусть задан абстрактный граф G(V, Е, f). G(V, Е, f) V,E – множества, отображение инциденции f: Е? V&V множества Е в V&V. Определение инцидентности. Пользователи образовательных услуг (П). В противном случае маршрут незамкнутый.
«Граф» - С берегов на острова были перекинуты мосты. Сурайа. МирАта. Карпов Иван. Задача: Аркадий, Борис. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах. Графы используются при составлении карт и генеалогических древ. Исследовать роль графов в нашей жизни. Карпов Михаил 29.10.1935.
«Формулы для перестановок, сочетаний, размещений» - Сочетания. Слово «факториал». Подарок. Формулы для подсчёта количества перестановок. Количество сочетаний. Количество размещений. Очередь. Перестановки. Количество перестановок. Размещения. Лесник.
«Комбинаторные задачи и их решения» - Школьнику о теории вероятностей. Углубление знаний учащихся. Презентации. Содержание программы. Комбинаторные задачи и их решения. Появление стохастической линии. Поурочное планирование. Пояснительная записка. Учебно-тематический план. Требования к уровню подготовки.
«Комбинаторные задачи» - Комбинаторные задачи. Из цифр 1, 5, 9 составить все трёхзначные числа без повторяющихся цифр. №2. Дерево возможных вариантов.
«Комбинаторика и её применение» - Решение. Комбинаторика вокруг нас. Опыт с листом бумаги. Истоки комбинаторики. Ученик. Области применения комбинаторики. Самостоятельная работа. Трехзначное число. Сколько четырехзначных чисел можно составить из 4 цифр. Комбинаторика и ее применение. Обед. Сколько различных комбинаций одежды имеется у Светланы.
