Графы в задачах

2 БАЛЛА

7. Основные понятия

Установите соответствие между термином и его описанием.

3 БАЛЛА

8. Задача о друзьях

В классе 9 человек. Может ли быть так, что у каждого ровно 5 друзей в этом классе? Ответ обоснуйте с помощью теории графов.

2 БАЛЛА

9. Лишний набор

Выберите набор чисел, который НЕ может быть последовательностью степеней вершин простого графа.

1. (2, 2, 2)
2. (1, 1, 1, 1)
3. (3, 3, 3, 3)
4. (2, 2, 1)

2 БАЛЛА

10. Ребра полного графа

Найдите количество ребер в полном графе $K_6$ (в котором каждая из 6 вершин соединена с каждой другой). Запишите расчет.

1 БАЛЛ

1. Подсчет ребер графа

В графе 8 вершин, и степень каждой вершины равна 4. Вычислите количество ребер в этом графе.

1 БАЛЛ

2. Понятие связного графа

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

• Граф, в котором между любыми двумя вершинами существует путь.
• Граф, в котором количество ребер на единицу меньше количества вершин.
• Граф, в котором каждая вершина соединена со всеми остальными вершинами.
• Граф, не содержащий ни одного цикла.

1 БАЛЛ

3. Основные элементы

Заполните пропуски в определении графа.

Граф состоит из множества точек, называемых , и множества линий, соединяющих эти точки, которые называются .

2 БАЛЛА

4. Турнирная таблица

В турнире участвуют 5 команд. Каждая команда должна сыграть с каждой по одному матчу. Сколько всего матчей будет сыграно в турнире? Решите задачу, представив её в виде полного графа.

2 БАЛЛА

5. Проверка степеней вершин

Может ли существовать простой граф с 5 вершинами, степени которых равны 4, 4, 4, 4, 2?

• Да, такой граф существует, так как сумма степеней четна и степени не превышают $n-1$.
• Нет, так как в графе с 5 вершинами не может быть четырех вершин степени 4.
• Нет, так как сумма степеней вершин должна быть нечетной.
• Да, но только если в графе есть хотя бы одна петля.

2 БАЛЛА

6. Свойства деревьев

Заполните пропуски в утверждениях о свойствах деревьев.

Связный граф, не содержащий циклов, называется . Если в таком графе 12 вершин, то количество ребер в нем равно .

3 БАЛЛА

7. Связность и степени

Рассмотрите граф, изображенный ниже. Вершины A, B, C, D образуют цикл, а вершина E соединена только с вершиной C.
1) Является ли граф связным?
2) Чему равна степень вершины C?

3 БАЛЛА

8. Свойства графов

Выберите ложное утверждение о дереве с $n$ вершинами.

• В дереве с $n$ вершинами количество ребер всегда равно $n$.
• Между любыми двумя вершинами дерева существует ровно один путь.
• Удаление любого ребра из дерева делает его несвязным.
• В дереве отсутствуют циклы.

4 БАЛЛА

9. Количественные характеристики

Заполните пропуски в формулах для произвольного простого графа с $n$ вершинами.

Максимально возможное число ребер в простом графе равно . Если граф имеет $k$ компонент связности, то минимально возможное число ребер в нем равно .

5 БАЛЛОВ

10. Лемма о рукопожатиях в турнире

В шахматном турнире участвуют 15 человек. Может ли случиться так, что каждый из них к середине турнира сыграл ровно по 3 партии? Обоснуйте ответ.

1 БАЛЛ

1. Понятие связности

Выберите верное определение связного графа.

• Граф, в котором между любыми двумя вершинами существует путь.
• Граф, в котором каждая вершина соединена ребром со всеми остальными вершинами.
• Граф, в котором отсутствуют циклы и петли.
• Граф, количество ребер в котором на единицу меньше количества вершин.

2 БАЛЛА

2. Визуальная проверка связности

Рассмотрите изображение графа. Является ли он связным? Ответ обоснуйте, указав количество компонент связности.

2 БАЛЛА

3. Матрица смежности

Заполните матрицу смежности для неориентированного графа с вершинами $A,B,C,D$, если известно, что в графе есть ребра: $(A,B),(B,C),(C,D),(D,A)$. Самопетли отсутствуют.

1 БАЛЛ

4. Лемма о рукопожатиях

В графе 6 вершин, степени которых равны 3, 2, 2, 2, 1, 4. Вычислите общее количество ребер в этом графе.

2 БАЛЛА

5. Элементы графа

Заполните пропуски в определениях элементов графа.

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

2 БАЛЛА

6. Типы графов

Установите соответствие между названием типа графа и его определяющим свойством.

3 БАЛЛА

7. Кратчайший путь

На рисунке изображена схема дорог между городами A, B, C, D, E. Числа над ребрами — длина дорог в км. Найдите длину кратчайшего пути из города A в город E.

2 БАЛЛА

8. Свойства связности

Определите истинность утверждений о свойствах связных графов.

1. В связном графе с $n$ вершинами всегда не менее $n-1$ ребер.ИстинаЛожь
2. Полный граф с 4 вершинами имеет ровно 6 ребер.ИстинаЛожь
3. Если в графе есть хотя бы одна вершина степени 0, то при $n>1$ такой граф несвязен.ИстинаЛожь
4. Любое дерево является связным графом.ИстинаЛожь
5. Степень вершины графа — это количество циклов, в которые она входит.ИстинаЛожь

3 БАЛЛА

9. Задача о рукопожатиях

Пять человек встретились и обменялись рукопожатиями. Известно, что каждый пожал руку ровно двоим. Изобразите это условие в виде графа (вершины — люди, ребра — рукопожатия). Может ли такой граф быть связным? Если да, приведите пример структуры.

1 БАЛЛ

10. Классификация графов

Выберите из списка описание графа, который ОБЯЗАТЕЛЬНО является несвязным.

1. Дерево с 10 вершинами
2. Полный граф $K_5$
3. Граф, состоящий из двух изолированных циклов
4. Граф, содержащий гамильтонов путь