Тест №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. Вопрос: Петя, Саша, Коля и Ваня играют в прятки. Они спрятались так что, Петя видит Ваню и Колю, Саша видит Петю, а Коля видит Ваню и Сашу. Постройте по данному условию граф. Сколько циклов он содержит? Запишите число:

1. Если граф является деревом, то он не может содержать циклы. Доказательство этого утверждения можно привести следующим образом:

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

Ответ: b)[ ]Никогда не будет

2. Граф - это группа объектов со связями между ними. Граф представляет из себя совокупность вершин и ребер, где вершины представляют объекты, а ребра представляют связи между этими объектами.

Ответ: a)[ ]Группа объектов со связями между ними.

3. Построим граф на основе данного условия:

Петя
|
Ваня
/ \
Коля Саша

Для того чтобы граф стал деревом, нужно убрать одну дугу. В данном случае мы можем, например, убрать дугу между Ваней и Колей.

Ответ: 1

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

Ответ: d)[ ]Взвешенным

5. Соответствие понятий и определений:

- Направленная линия, соединяющая вершины графа: Дуга
- Петля: Линия выходящая из некоторой вершины и в нее же входящая.
- Ребро: Ненаправленная линия, соединяющая вершины графа.

6. По изображению графа водопровода можно понять, что он является неориентированным, так как его ребра не имеют стрелок или направлений.

Ответ: b)[ ]Неориентированным

7. Чтобы убрать дугу, не разомкнув ни одного цикла, нужно убрать ту дугу, для которой существует альтернативный путь, который поддерживает связность графа. В данном случае мы можем убрать дугу BD.

Ответ: BD

8. Верные утверждения:
- Вершины неориентированного графа соединены ребрами.
- Если линия выходит из некоторой вершины и входит в нее же, эта линия называется петлей.
- Цикл - это цепь, в которой начальная и конечная вершины совпадают.

Ответ: a), b), c)

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

10. Построим граф на основе данного условия:

Петя
|
Ваня
/ \
Коля Саша

Граф содержит два цикла: Петя-Ваня-Коля-Петя и Саша-Петя-Ваня-Саша.

Ответ: 2