Теорія графів | Тест з інформатики

Запитання 1

Відмітьте твердження, на які можна ствердно відповісти (тобто, однозначно "так"), виходячи із зображеного на малюнку графа.

варіанти відповідей

Граф є повним

Граф є транзитивним

Граф є однозвязним

Граф є орієнтованим

Граф є навантаженим

У графі є кратні ребра

У графі немає ізольованих вершин

У графі є висячі вершини

Запитання 2

Відмітьте твердження, на які можна ствердно відповісти (тобто, однозначно "так"), виходячи із зображеного на малюнку графа.

варіанти відповідей

Граф є повним

Граф є однозв'язним

Граф є навантаженим

У графі немає ізольованих вершин

Граф є транзитивним

Граф є орієнтованим

У графі є кратні ребра

У графі є ізольовані точки

Запитання 3

Який степінь ізольованої точки?

варіанти відповідей

0

1

2

співпадає з кількістю вершин у графі

Запитання 4

Яка кількість ребер у повного графа з 8-ма вершинами?

варіанти відповідей

28

12

20

8

16

неможливо однозначно визначити

Запитання 5

Який степінь "висячої" вершини в графі ?

варіанти відповідей

0

1

2

співпадає із кількістю вершин у графі

Запитання 6

Яка кількість ребер в нуль-графі з 8-ма вершинами

варіанти відповідей

0

8

28

12

16

неможливо однозначно визначити

Запитання 7

Чи може граф одночасно бути навантаженим та орієнтованим?

варіанти відповідей

Так

Ні

Запитання 8

Відомо, що в графі деяке ребро сполучає дві вершини. Відмітьте првильні твіредження.

варіанти відповідей

Ребро ІНЦИДЕНТНЕ вершинам, які сполучає

Ребро СУМІЖНЕ вершинам, які сполучає

Вершини СУМІЖНІ ребру, що їх сполучає

Вершини ІНЦИДЕНТНі ребру, що їх сполучає

Вершини СУМІЖНІ між собою

Запитання 9

Граф, всі вершини якого можна відвідати, проходячи по кожному із ребер по одному разу, повернувншись при цьому в початкову точку, називають

варіанти відповідей

повним

ейлеровим

гамільтоновим

замкненим

циклічним

Запитання 10

На малюнку зображено деякий граф. Який вигляд має його ТРЕТІЙ РЯДОЧОК (нумерація в матриці починається з одиниці, номер рядка в матриці співпадає з номером вершини в графі) в матриці суміжності?

варіанти відповідей

(0; 0; 0; 0; 12; 0; 3)

(1; 0; 0; 0; 0; 7; 0)

(0; 0; 0; 0; 0; 0; 10)

(6; 0; 0; 0; 0; 0; 0)

Немає правильної відповіді

Запитання 11

На малюнку зображено деякий граф. Який вигляд має його ТРЕТІЙ СТОВПЧИК (нумерація в матриці починається з одиниці, номер рядка в матриці співпадає з номером вершини в графі) в матриці суміжності?

варіанти відповідей

(0; 0; 0; 0; 12; 0; 3)

(0; 0; 0; 0; 0; 0; 10)

(1; 0; 0; 0; 0; 7; 0)

(6; 0; 0; 0; 0; 0; 0)

Немає правильної відповіді

Запитання 12

Якими способами можна представляти математичну графа з N вершин та M ребер?

варіанти відповідей

Матриця суміжності ( Розмірність матриці N*N, наявність ребра між вершинами з номерами i та j - записувати 1 або вага в елемент a[i,j]; відсутність - 0)

Список суміжності (інцидентності): структура даних, яка для кожної вершини графа зберігає список суміжних з нею вершин. Список являє собою масив покажчиків, i-ий елемент якого містить вказівник на список вершин, суміжних з i-ою вершиною.

У вигляді зображення в *.bpm - файлі

Матриця суміжності. Розмірність матриці M*M, наявність ребра між вершинами з номерами i та j - записувати число 1 або вагу ребра в елемент a[i,j]; відсутність - 0.

Запитання 13

Чи існує поняття "степені" для вершини в орієнтованому графі?

варіанти відповідей

Так, це сума всіх ребер, які виходять з даної вершини та входять до неї

Так, але розрізняють "степінь вхідних ребер" та "степінь вихідних"

Ні, для орієнтованого графа дане визначанння є некоректним

Запитання 14

Чи симетрична відносно головної діагоналі матриця суміжності у графі, зображеному на малюнку?

варіанти відповідей

Так

Ні

Запитання 15

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності навантаженого графа)

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейкстри

алгоритм Флойда-Уоршалла

Запитання 16

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності невантаженого графа

queue - черга вершин, що обробляються

visible - список "побачених" вершин)

варіанти відповідей

пошук в глибину

алгоритм Дейкстри

пошук в ширину

алгоритм Флойда-Уоршалла

Запитання 17

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності невантаженого графа

stack - стек вершин, які обробляються

visited - список відвіданих вершин )

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейкстри

алгоритм Флойда-Уоршалла

Запитання 18

Реалізацію якого алгоритму зображено на малюнку?

(a - матриця суміжності навантаженого графа,

visit - список відвіданих вершин,

dist - список мінімальних відстаней від стартової вершини до всіх решти )

варіанти відповідей

пошук в глибину

алгоритм Дейкстри

пошук в ширину

алгоритм Флойда-Уоршалла

Запитання 19

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ПОШУКУ В ГЛИБИНУ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

пошук мінімального шляху між двома вершинами

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною

пошук шляху мінімальної сумарної ваги (для навантаженого графа)

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінації стартових та кінцевих вершин

Запитання 20

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ДЕЙКСТРИ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною (мінімальні відстані в списку буть менші за "умовну нескінченність")

пошук кількості компонент зв'язності в графі

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінацій стартових та кінцевих вершин

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

Запитання 21

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму ПОШУКУ В ШИРИНУ (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною

пошук шляху (мінімальна кількість пройдених ребер) між двома вершинами

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінації стартових та кінцевих вершин

Запитання 22

Для розв'язку яких із наведених нижче проблем можна використати ОДНЕ використання алгоритму Флойда-Уоршалла (граф заданий матрицею суміжності)?

варіанти відповідей

дослідження, чи є шлях від однієї вершини до іншої (шлях відсутній, якщо a[i,j] = 0)

пошук шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

визначення всіх вершин, що знаходяться в одній компоненті зв'язності графа із поточною (мінімальні відстані в списку відстаней буть менші за "умовну нескінченність")

пошук ВАГИ шляху мінімальної сумарної ваги (для навантаженого графа) для всеможливих комбінацій стартових та кінцевих вершин

пошук ВАГИ шляху мінімальної сумарної ваги (для навантаженого графа) для ОДНІЄЇ пари вершин: стартової та кінцевої

Запитання 23

Які з наведених алгоритмів не змінюють в процесі свого виконання матрицю суміжності графа?

варіанти відповідей

Пошук в ширину

Пошук в глибину

Алгоритм Дейкстри

Алгоритм Флойда-Уоршалла

Запитання 24

Які із наведених алгоритмів недоцільно (чи немає змісту) використовувати для ненавантажених графів?

варіанти відповідей

пошук в ширину

пошук в глибину

алгоритм Дейсктри

алгоритм Флойда-Уоршалла

Запитання 25

Чи можна використовувати алгоритм Дейкстри та Флойда-Уоршалла для графів із від'ємними вагами ребер?

варіанти відповідей

Так, завжди можна

Ні, не можна.