samigyllin

10.01.2023 00:22 •  Информатика

Тест №19 Модели на графах 1. Если граф является деревом, могут ли в нем быть циклы?
Выберите один из 3 вариантов ответа:
a)[ ]Иногда могут
b)[ ]Никогда не будет
c)[ ]Всегда будут
2. Что такое граф?
Выберите один из 3 вариантов ответа:
a)[ ]Группа объектов со связями между ними.
b)[ ]Информационная модель, применяемая для описания объектов с
одинаковыми наборами свойств.
c)[ ]Линия, применяемая для наглядного изображения зависимости одной
величины от другой.
3. Вопрос:
Петя, Саша, Коля и Ваня играют в прятки. Они спрятались так что, Петя
видит Ваню и Колю, Саша видит Петю, а Коля видит Ваню и Сашу.
Постройте по данному условию граф.
Какое минимальное количество дуг необходимо убрать у графа чтобы он
стал деревом?
Запишите число:

4. Вопрос:
На рисунке изображен граф, в котором указаны цены перевозки тонны
груза между деревнями. Каким является этот граф?
Изображение:
Выберите несколько из 4 вариантов ответа:
a)[ ]Ориентированным
b)[ ]Неориентированным
c)[ ]Невзвешенным
d)[ ]Взвешенным
5. Установите соответствие понятий и определений.
Укажите соответствие для всех 3 вариантов ответа:
Направленная линия, соединяющая
вершины графа.
Петля
Линия выходящая из некоторой
вершины и в нее же входящая.

Ребро
Ненаправленная линия, соединяющая
вершины графа.

Дуга
6. Вопрос:
На рисунке изображен граф водопровода. Этот граф является ...
Изображение:
Выберите несколько из 6 вариантов ответа:
a)[ ]Взвешенным
b)[ ]Неориентированным
c)[ ]Ориентированным
d)[ ]Деревом
e)[ ]Сетью
f)[ ]Не взвешенным
7. Вопрос:
В графе, есть вершины A, B, C, D и дуги AB, BC, BD, CA, DA, DC. Какую
дугу можно убрать, не разомкнув при этом не одного цикла?
Запишите ответ (заглавными латинскими буквами):

8. Выберите верные утверждения.
Выберите несколько из 4 вариантов ответа:
a)[ ]Вершины неориентированного графа соединены дугами.
b)[ ]Если линия выходит из некоторой вершины и входит в нее же, эта линия
называется петлей.
c)[ ]Цикл - это цепь, в которой начальная и конечная вершины совпадают.
d)[ ]Дуга - это ненаправленная линия, которая соединяет вершины графа.
9. Установите соответствие между понятиями и определениями.
Укажите соответствие для всех 3 вариантов ответа:
Граф содержащий циклы

Сеть
Путь по вершинам графа, который
включает любое ребро не меньше
одного раза

Цепь
Граф с иерархической системой

Дерево
10. Вопрос:
Петя, Саша, Коля и Ваня играют в прятки. Они спрятались так что, Петя
видит Ваню и Колю, Саша видит Петю, а Коля видит Ваню и Сашу.
Постройте по данному условию граф. Сколько циклов он содержит?
Запишите число: