Семинар ДООМ Материалы для курса Графы

Коннова Елена Генриевна Руководитель команд Альтаир 062

Форсаж 063

Материалы для оценивания усвоения содержания курса Семинар ДООМ Элективный курс Графы

I. Список практических работ по курсу «Графы»

Построение транспортных или географических графов

1. Схема движения троллейбусного (или другого вида) транспорта с решением задачи о кратчайшем маршруте.

2. План города (района) с указанием расстояний и разработка маршрутов с учетом различных критериев.

3. Схема водных ресурсов с указанием их судоходности и расстояний и разработка маршрутов с учетом различных критериев.

Задачи о прохождении графа «одним росчерком» и др.

1. Составление авторских задач, решаемых с помощью теории графов, выполнение рисунков графов в различных графических редакторах и оформление работы в виде презентации или брошюры.

Построение генеалогического дерева или схемы систематики

1. Генеалогическое семейное дерево учащегося.

2. Генеалогическое дерево царского рода.

3. Генеалогическое дерево (родословная) домашнего животного.

4. Схема систематики растений, насекомых, животных и т.п.

5. Схема систематики механизмов, наук, СМИ и т.п.

II. Тест для проверки усвоения теоретического материала курса 1. Сколько ребер в графе 1?

2. Сколько вершин в графе 1?

3. Укажите кратность вершины В графа 1.

4. Сколько четных вершин в графе 1? Укажите их.

5. Может ли в графе быть три нечетных вершины?

6. Сумма степеней графа 24. Сколько ребер в этом графе?

7. Полный ли граф 2?

8. Сколько ребер в полном графе с 10 вершинами?

9. Существует ли эйлеров цикл в графе 3?

10. Назовите два цикла в графе 3.

11. Найдите эйлеров путь в графе 3.

12. Назовите связные графы на рис. 4

13. Назовите деревья на рис. 4

14. Сколько компонент связности у графа 4в?

15. В дереве 15 вершин. Сколько в нем ребер?

16. Граф является деревом. Может ли в нем быть цикл?

17. Граф является деревом, среди его вершин есть А и В. Сколько может существовать путей из А в В?

18. Назовите мосты в графе 5.

19. Сколько граней в графе 5?

20. Укажите длину пути из А в К через Д.

Ответы к тесту

• 1 8
• 2 6
• 3 3
• 4 2(E,D)
• 5 Нет
• 6 12
• 7 Нет
• 8 45
• 9 Нет
• 10 АКДСВА, АFКА
• 11 ABCDEFAKFKD
• 12 4а,4б
• 13 4б
• 14 2
• 15 14
• 16 Нет
• 17 1
• 18 АВ, СЕ
• 19 3
• 20 5