Контрольная работа №1 по теме "Базовые понятия теории графов"

Контрольная работа № 1

по теме «Базовые понятие теории графов»

1.                   На этой неделе в 6«А» классе шестеро дежурных: Алина, Вика, Евгений, Денис, Саша и Фёдор. На рисунке, приведённом ниже, дежурные – это вершины графа. Две вершины соединены ребром в том случае, если ребята дружат между собой. Посчитайте, сколько всего рёбер в этом графе. С какими дежурными дружит Евгений?

 

2.                   В одно круговом турнире по шахматам принимают участие 6 человек. В

первую неделю сыграть все свои партии успели только 2 человека. Все оставшиеся партии будут доиграны на следующей неделе. Рассмотрим следующий граф: пусть участники турнира – это вершины графа. Две вершины соединяются ребром, если соответствующие участники сыграли друг с другом в первую неделю. Какие из приведённых в таблице графов подходят под данное условие?

1.
2.
3.
4.
5.

3.                   Ученик нарисовал граф в виде клетчатой таблицы 3 × 5, изображенной на рисунке. Узлы этой таблицы являются вершинами графа. Отрезки длины один – рёбра графа. В получившемся графе ровно 8 вершин степени 4. Сколько вершин степени 4 будет в аналогичном графе, изображённом в виде таблицы 15 × 17?

 

4.                   Один и тот же граф на плоскости можно изобразить разными способами.

Например, графы на рисунке представляют собой один и тот же граф.

 

Такие одинаковые, но по-разному нарисованные графы называют изоморфными.

Среди приведенных в таблице графов найдите пары изоморфных графов.

1.
2.
3.
4.
5.
6.

5.                   В таблице даны изображения двух графов. Сопоставьте каждое изображение с описанием перечисления множества вершин и множества рёбер.

	1.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}	и	рёбра
	{𝐴𝐵, 𝐵𝐶, 𝐵𝐷, 𝐵𝐸}. 2.           Вершины      {𝐴, 𝐵, 𝐶, 𝐷}	и	рёбра
	{𝐴𝐵, 𝐴𝐷, 𝐵𝐶, 𝐶𝐷}. 3.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}	и	рёбра
	{𝐴𝐵, 𝐴𝐷, 𝐵𝐶, 𝐶𝐷}. 4.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} {𝐴𝐵, 𝐴𝐷, 𝐵𝐷, 𝐶𝐷}.	и	рёбра
	1.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}	и	рёбра
	{𝐴𝐵, 𝐵𝐶, 𝐵𝐷, 𝐵𝐸}. 2.           Вершины      {𝐴, 𝐵, 𝐶, 𝐷}	и	рёбра
	{𝐴𝐵, 𝐴𝐷, 𝐵𝐶, 𝐶𝐷}. 3.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}	и	рёбра
	{𝐴𝐵, 𝐴𝐷, 𝐵𝐶, 𝐶𝐷}. 4.           Вершины       {𝐴, 𝐵, 𝐶, 𝐷, 𝐸} {𝐴𝐵, 𝐴𝐷, 𝐵𝐷, 𝐶𝐷}.	и	рёбра