Комбинаторика
<<  Определение графа Элементы комбинаторики: перестановки, сочетания и размещения  >>
Задачи на графы
Задачи на графы
Задачи
Задачи
Граф по условию задачи
Граф по условию задачи
Преобразуем граф в дерево 1
Преобразуем граф в дерево 1
Преобразуем граф в дерево 2
Преобразуем граф в дерево 2
Преобразуем граф в дерево 3
Преобразуем граф в дерево 3
Решение задачи - лес
Решение задачи - лес
Задачи
Задачи
Правдолюб говорит только правду
Правдолюб говорит только правду
1
1
Решение
Решение
Задачи
Задачи
Задачи
Задачи
Граф
Граф
Задачи
Задачи
A(1,6)
A(1,6)
Дороги на графе
Дороги на графе
Время туда
Время туда
Время туда и обратно
Время туда и обратно
 
 

Презентация: «Задачи на графы». Автор: Староверов. Файл: «Задачи на графы.ppt». Размер zip-архива: 152 КБ.

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

содержание презентации «Задачи на графы.ppt»
СлайдТекст
1 Задачи на графы

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

2 Задачи

Задачи

Задача 1. Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств: учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; учитель литературы может дать один, либо второй, либо третий урок; математик готов дать либо только первый, либо только второй урок; преподаватель физкультуры согласен дать только последний урок. Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы?

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

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

1

М

И

2

Л

3

4

Ф

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

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

1

М

И

2

Л

1

М

3

И

2

1

4

Ф

Л

М

3

И

2

Л

4

Ф

3

4

Ф

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

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

1

М

И

2

Л

1

3

М

И

2

4

Ф

1

Л

М

3

И

2

Л

4

Ф

3

4

Ф

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

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

1

М

И

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. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?

9 Правдолюб говорит только правду

Правдолюб говорит только правду

Лжец всегда лжет

Дипломат либо лжет, либо нет

Рядом со мной лжец

Я дипломат

Рядом со мной правдолюб

10 1

1

2

3

Л

Д

Л

Д

Л

Д

П

11 Решение

Решение

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

12 Задачи

Задачи

Задача 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?

13 Задачи

Задачи

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

16 A(1,6)

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

Мин

«Задачи на графы»
http://900igr.net/prezentacija/algebra/zadachi-na-grafy-260568.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды