Проверочная работа на тему "Графы"
материал по математике (7 класс)

Самостоятельная работа № 4 по теме «Графы»
(10–15 мин), 7 класс

Вариант 1

1. Найдите степени вершин графа, изображённого на рисунке. Начертите в тетради таблицу и заполните её.

2. В графе, показанном на рисунке к заданию 1, цепь DGEC длину 3.

а) Найдите цепь длины 4, которая соединяет вершину А с вершиной В.

б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В?

3. Можно ли соединить 8 городов дорогами так, чтобы из трёх городов выходило по три дороги, а из оставшихся пяти городов – по четыре дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.

Вариант 2

1. Найдите степени вершин графа, изображённого на рисунке. Начертите в тетради таблицу и заполните её.

2. В графе, показанном на рисунке к заданию 1, цепь АСDG длину 3.

а) Найдите цепь длины 4, которая соединяет вершину В с вершиной А.

б) Сколько в этом графе цепей длины 5, которые соединяют вершину А с вершиной В?

3. Можно ли соединить 7 городов дорогами так, чтобы из трёх городов выходило по пять дорог, а из оставшихся четырёх городов – по три дороги? Нарисуйте пример подходящего графа или объясните, почему это невозможно.

Ответы

Вариант 1.

1. 

2. а) ADGEB; б) 2. 3. Нет. Решение. Рассмотрим города и дороги как граф. В этом графе сумма степеней вершин равна 3 . 3 + 5 . 4 = 29 – нечётное число. Такой граф не существует

Вариант 2.

1. 

2. а) BEGDA; б) 3. 3. Нет, так как сумма степеней вершин равна 3 . 5 + 4 . 3 = 27 – нечётное число.