Контрольная работа №
1
по
теме «Базовые понятие теории графов»
1.
На этой неделе в 6«А» классе шестеро дежурных: Алина, Вика,
Евгений, Денис, Саша и Фёдор. На рисунке, приведённом ниже, дежурные – это
вершины графа. Две вершины соединены ребром в том случае, если ребята дружат
между собой. Посчитайте, сколько всего рёбер в этом графе. С какими дежурными
дружит Евгений?
2.
В одно круговом турнире по шахматам принимают участие 6 человек. В
первую неделю сыграть все свои партии успели только 2 человека. Все оставшиеся
партии будут доиграны на следующей неделе. Рассмотрим следующий граф: пусть
участники турнира – это вершины графа. Две вершины соединяются ребром, если
соответствующие участники сыграли друг с другом в первую неделю. Какие из
приведённых в таблице графов подходят под данное условие?
3.
Ученик нарисовал граф в виде клетчатой таблицы 3 × 5, изображенной на рисунке.
Узлы этой таблицы являются вершинами графа. Отрезки длины один – рёбра графа. В
получившемся графе ровно 8
вершин степени 4. Сколько
вершин степени 4 будет в
аналогичном графе, изображённом в виде таблицы 15
× 17?
4.
Один и тот же граф на плоскости можно изобразить разными
способами.
Например, графы на рисунке представляют собой один и тот же
граф.
Такие одинаковые, но по-разному нарисованные графы называют
изоморфными.
Среди приведенных в
таблице графов найдите пары изоморфных графов.
5.
В таблице даны изображения двух графов. Сопоставьте каждое
изображение с описанием перечисления множества вершин и множества рёбер.
|
1. Вершины
{𝐴, 𝐵, 𝐶,
𝐷, 𝐸}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐵𝐶,
𝐵𝐷, 𝐵𝐸}.
2. Вершины
{𝐴, 𝐵, 𝐶,
𝐷}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐴𝐷,
𝐵𝐶, 𝐶𝐷}.
3. Вершины
{𝐴, 𝐵, 𝐶,
𝐷, 𝐸}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐴𝐷,
𝐵𝐶, 𝐶𝐷}.
4. Вершины {𝐴, 𝐵, 𝐶, 𝐷,
𝐸}
{𝐴𝐵, 𝐴𝐷,
𝐵𝐷, 𝐶𝐷}.
|
и
|
рёбра
|
|
1. Вершины
{𝐴, 𝐵, 𝐶,
𝐷, 𝐸}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐵𝐶,
𝐵𝐷, 𝐵𝐸}.
2. Вершины
{𝐴, 𝐵, 𝐶,
𝐷}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐴𝐷,
𝐵𝐶, 𝐶𝐷}.
3. Вершины
{𝐴, 𝐵, 𝐶,
𝐷, 𝐸}
|
и
|
рёбра
|
|
{𝐴𝐵, 𝐴𝐷,
𝐵𝐶, 𝐶𝐷}.
4. Вершины {𝐴, 𝐵, 𝐶, 𝐷,
𝐸}
{𝐴𝐵, 𝐴𝐷,
𝐵𝐷, 𝐶𝐷}.
|
и
|
рёбра
|
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.