Рабочий лист Теория графов

Вероятность и статистика

Фамилия Имя __________________________ Класс _____ Дата __________

Теория Графов. Графы и деревья

Задание 1 Отметьте все связанные графы

3

2

5

4

1

Ответ:

Задание 2 На рисунке изображен граф

а) Сколько у него ребер?

б) Сколько у него вершин?

в) Назовите вершину с наибольшей степенью

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 3 Задача о соревнованиях

В турнире по шахматам участвуют 7 команд. Каждая команда играет с каждой другой командой по одной партии.

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

Нарисуй граф

Решение :

Кол-во Вершин -

Степень одной вершины -

Кол-во игр

Ответ:

Задание 4 Даны пять графов с 7 вершинами, некоторые из которых одинаковые. Найдите уникальный граф.

2

4

1

3

Ответ:

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 5 Задача о дорогах

В стране Путевии 30 городов. В каждый город ведут 4 дороги из других городов этой страны.

Сколько всего дорог в Путевии?

Решение :

Кол-во Вершин -

Степень одной вершины -

Сумма степеней вершин равна -

Тогда рёбер -

Ответ:

Задание 6 Нарисуйте

Полный граф с 6 вершинами

Любой граф с 2-мя циклами

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 7 Задача о планетах

В Солнечной системе существует космическое сообщение между

8 планетами. Ракеты летают по следующим маршрутам:

Марс — Сатурн

Венера — Земля

Земля — Нептун

Меркурий — Венера

Сатурн — Уран

Уран — Нептун

Юпитер — Сатурн

Нептун — Марс

Можно ли добраться с планеты Меркурий до планеты Марс?

Решение :

Составь путь:

Ответ:

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 8 Задача о количестве путей

Есть схема дорог, связывающих города A, B, C и D. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D

Решение :

Ответ:

Задание 9 Задача о компьютерах

Можно ли соединить проводами 125 компьютеров так, чтобы каждый компьютер был соединён ровно с 15 компьютерами?

Решение :

Ответ:

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 10

В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Числа, стоящие на пересечениях строк и столбцов означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите схему, соответствующую таблице.

А

А

В

В

1

С

С

1

4

4

D

D

Е

E

1

1

3

3

2

2

Фамилия Имя __________________________ Класс _____ Дата __________

Задание 11

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H, проходящих через город B?

Ответ:

Задание 12

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

Ответ:

Ответы

Задание 1

2, 4, 5

а) ребер - 11

б) вершин - 8

в) вершина с наибольшей степенью - С

Задание 2

Задание 3

21 партия

Задание 4

2

Задание 5

60 дорог

Задание 6

полный граф

граф с 2-мя циклами

1

2

Задание 7

Меркурий → Венера

Венера → Земля

Земля → Нептун

Нептун → Марс

Да, добраться можно

Из А в B - 2 пути

Из В С - 3 пути

Из С в D - 3 пути

Всего: 2 * 3 * 3 = 18 путей

Задание 8

Задание 9

Кол-во вершин 125

Степень каждой вершины равна 15

Сумма степеней вершин равна 125 ×15 = 1875

Получилось нечетное число

При делении 1875 на 2 получается не целое число

Ответ: НЕТ

1