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