Применение теории графов к решению задач

Сентябрь 14, 2022

Главная
Математика
Применение теории графов к решению задач

Содержание

2. Мосты через реку Прегель расположены как на рисунке. Вопрос состоит в том, можно ли, прогуливаясь по
3. D
4. На рисунке изображена решетка. Можно ли провести непрерывную линию, пересекающую точно по разу каждую сторону решетки?
5. Виды графов: Неориентированный граф Ориентированный граф Граф-дерево или дерево возможностей Граф с ребрами двух цветов
6. Неориентированные графы
7. Задача 1. В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл со всеми другими участниками соревнований
8. В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл со всеми другими участниками соревнований по одному
9. Задача 2. На лесной опушке встретились заяц, белка, лиса, волк, медведь и куница. Каждый, здороваясь, пожал
10. Задача 3. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все
11. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались
12. Задача 3. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все
13. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались
14. Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались
15. Задача 4. В первенстве класса по шашкам 5 участников: Аня, Боря, Влад, Гриша, Даша. Первенство проводится
16. Д Б В А Г Аня сыграла с Борей, Владом и Дашей; Боря сыграл, как уже
17. Задача 5. В стране алфавит 8 городов: А, Б, В, Г, Д, Е, Ж, З и
18. А Г Д В Ж З Б Е
19. Ориентированные графы
20. Задача 6. Из лагеря вышли четыре туриста: Вася, Галя, Толя и Лена. Вася идет впереди Лены,
21. Вася идет впереди Лены, Толя впереди Гали, а Лена впереди Толи. В∙ ∙Г Т∙ ∙Л
22. Задача 7. В детском лагере отдыха в одной комнате живут четыре девочки: Маша, Валя, Таня и
23. Т М М Г В В Т Г Таня старше Маши, которая моложе Гали. Таня моложе
24. Задача 8. На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и
25. Д Л Я Т К С Р Б Рябина выше лиственницы, яблоня выше клена, дуб ниже
26. Граф-дерево или дерево возможностей
27. Задача 9. В столовой на горячее можно заказать щуку, грибы и баранину, на гарнир – картофель
28. Р К Ч К Ч К Ч К Ч К Ч К Ч К Щ Г
29. Задача 10. Из наборного полотна взяли 2 карточки с цифрой 1 и 3 карточки с цифрой
30. 1 1 5 1 5 5 5 1 5 5 1 5 5 5 1 5
31. Граф с ребрами двух цветов
32. Задача 12. В одном классе учатся Иван, Петр и Сергей. Их фамилии Иванов, Петров и Сергеев.
33. Иван не Иванов, Петр не Петров, Сергей не Сергеев. Сергей живет в одном доме Петровым. Иван∙
34. Задача 13. Три друга – Алеша, Сергей и Денис – купили щенков разной породы: щенка ротвейлера,
35. Щенок Алеши темнее по окрасу, чем ротвейлер, Леси и Гриф; щенок Сергея старше Грифа, овчарки и
36. Щенок Алеши темнее по окрасу, чем ротвейлер, Леси и Гриф; щенок Сергея старше Грифа, овчарки и
38. Скачать презентацию

Слайд 2

Мосты через реку Прегель расположены как на рисунке. Вопрос состоит в

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

Слайд 3

D

Слайд 4

На рисунке изображена решетка. Можно ли провести непрерывную линию, пересекающую точно

по разу каждую сторону решетки?

Слайд 5

Виды графов:
Неориентированный граф
Ориентированный граф
Граф-дерево или дерево возможностей
Граф с ребрами

двух цветов

Слайд 6

Неориентированные графы

Слайд 7

Задача 1. В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл

со всеми другими участниками соревнований по одному разу. Сколько всего было сыграно партий?

Слайд 8

В шахматном турнире участвовали 4 человека. Каждый спортсмен сыграл со всеми

другими участниками соревнований по одному разу. Сколько всего было сыграно партий?

Слайд 9

Задача 2. На лесной опушке встретились заяц, белка, лиса, волк, медведь

и куница. Каждый, здороваясь, пожал каждому лапу. Сколько всего лапкопожатий было сделано?

Слайд 10

Задача 3. Несколько мальчиков встретились на вокзале, чтобы поехать за город

в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехало за город, если всего было10 рукопожатий?

Слайд 11

Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес.

При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехало за город, если всего было10 рукопожатий?

Слайд 12

Задача 3. Несколько мальчиков встретились на вокзале, чтобы поехать за город

Слайд 13

Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес.

Слайд 14

Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес.

Слайд 15

Задача 4. В первенстве класса по шашкам 5 участников: Аня, Боря,

Влад, Гриша, Даша. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему времени некоторые игры уже проведены: Аня сыграла с Борей, Владом и Дашей; Боря сыграл, как уже говорилось, с Аней и еще с Гришей; Влад – с Аней и Дашей, Гриша – с Борей, Даша – с Аней и Гришей. Сколько игр проведено к настоящему времени и сколько еще осталось?

Слайд 16

Д
Б
В
А
Г
Аня сыграла с Борей, Владом и Дашей; Боря сыграл, как уже

говорилось, с Аней и еще с Гришей; Влад – с Аней и Дашей, Гриша – с Борей, Даша – с Аней и Гришей.

Слайд 17

Задача 5. В стране алфавит 8 городов: А, Б, В, Г,

Д, Е, Ж, З и восемь непересекающихся дорог между городами А и Б, Е и Д, Б и Ж, З и А, В и Г, Г и Д, Ж и З, В и Е. Можно ли по этим дорогам проехать из А в Г?

Слайд 18

А
Г
Д
В
Ж
З
Б
Е

Слайд 19

Ориентированные графы

Слайд 20

Задача 6. Из лагеря вышли четыре туриста: Вася, Галя, Толя и

Лена. Вася идет впереди Лены, Толя впереди Гали, а Лена впереди Толи. В каком порядке идут дети?

Вася Лена

Толя

Галя

Слайд 21

Вася идет впереди Лены, Толя впереди Гали, а Лена впереди Толи.

В∙

∙Г

Т∙

∙Л

Слайд 22

Задача 7. В детском лагере отдыха в одной комнате живут четыре

девочки: Маша, Валя, Таня и Галя. Две из них ровесницы. Известно, что Таня старше Маши, которая моложе Гали. Таня моложе Вали, которая старше Гали. Кто ровесницы?

Слайд 23

Т
М
М
Г
В
В
Т
Г
Таня старше Маши, которая моложе Гали. Таня моложе Вали, которая старше

Гали.

Слайд 24

Задача 8. На пришкольном участке растут 8 деревьев: яблоня, тополь, береза,

рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.

Слайд 25

Д
Л
Я
Т
К
С
Р
Б
Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше

сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони.

Слайд 26

Граф-дерево или дерево возможностей

Слайд 27

Задача 9. В столовой на горячее можно заказать щуку, грибы и

баранину, на гарнир – картофель и рис, а из напитков – чай и кофе. Сколько различных вариантов обедов можно составить из указанных блюд?

Слайд 28

Р
К
Ч К Ч К Ч К Ч К Ч К

Ч К

Слайд 29

Задача 10. Из наборного полотна взяли 2 карточки с цифрой 1

и 3 карточки с цифрой 5. Сколько различных пятизначных чисел можно составить из этих карточек?

Слайд 30

1
1
5
1
5
5
5
1
5
5
1
5
5
5
1
5
1
5
5
5
5
5
1
5
1
1
1
5
5
1
5
1
1

Слайд 31

Граф с ребрами двух цветов

Слайд 32

Задача 12. В одном классе учатся Иван, Петр и Сергей. Их

фамилии Иванов, Петров и Сергеев. Установи фамилию каждого из ребят, если известно, что Иван не Иванов, Петр не Петров и Сергей не Сергеев и что Сергей живет в одном доме Петровым.

Слайд 33

Иван не Иванов, Петр не Петров, Сергей не Сергеев. Сергей живет

в одном доме Петровым.

Иван∙
Петр∙
Сергей ∙

∙ Иванов
∙ Петров
∙ Сергеев

Слайд 34

Задача 13. Три друга – Алеша, Сергей и Денис – купили

щенков разной породы: щенка ротвейлера, щенка колли и щенка овчарки. Известно, что: щенок Алеши темнее по окрасу, чем ротвейлер, Леси и Гриф; щенок Сергея старше Грифа, овчарки и ротвейлера; Джек и ротвейлер всегда гуляют вместе. У кого какой породы щенок? Назовите клички щенков.

Слайд 35