Введение в теорию графов

4 УТВЕРЖДЕНИЯ · 1 БАЛЛ

1. Верно или неверно?

Проверьте утверждения об основных элементах графа, опираясь на определения вершины, ребра и степени.

1. Вершина графа — это точка, обозначающая объект.ИстинаЛожь
2. Одно ребро может соединять сразу три различные вершины.ИстинаЛожь
3. Степень вершины — это количество рёбер, которые из неё выходят.ИстинаЛожь
4. В графе не может существовать вершины, у которой нет ни одного ребра.ИстинаЛожь

1 ВЫБОР · 1 БАЛЛ

2. Количество рёбер

Дан граф, в котором вершины — это города $A,B,C,D$. Рёбра соединяют пары: $(A,B),(B,C),(C,D),(D,A)$. Сколько всего рёбер в этом графе?

• $3$
• $4$
• $5$
• $8$

КРАТКИЙ ОТВЕТ · 1 БАЛЛ

3. Сумма степеней

В графе $5$ вершин. Известно, что из каждой вершины выходит ровно по $2$ ребра. Найдите общее количество рёбер в этом графе.

ПОРЯДОК · 2 БАЛЛА

4. Построение пути

Упорядочьте вершины так, чтобы получился путь из вершины $A$ в вершину $E$, если в графе существуют только следующие рёбра: $(A,B),(B,C),(C,D),(D,E)$.

1. Вершина $C$
2. Вершина $E$
3. Вершина $A$
4. Вершина $D$
5. Вершина $B$

4 УТВЕРЖДЕНИЯ · 2 БАЛЛА

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

Оцените истинность утверждений о связности графов и чётности степеней их вершин.

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