Font size
WorksheetsГрафи (Python)
Total questions: 17
Worksheet time: 9mins
Графом називають:
схему з’єднання об’єктів
множину вершин і множину ліній, що з’єднують дві будь-які вершини
множину об’єктів із зв’язками
множину вершин із зв’язками
Лінії, що з’єднують вершини у графі, називають:
дугами
з’єднувачами
вказівниками
ребрами
Дві вершини у графі називають суміжними, якщо вони:
з’єднані петлею
з’єднані дугою
не мають з’єднань
з’єднані ребром
Граф називають повним, якщо:
всі вершини суміжні
всі вершини мають дуги
дві будь-які вершини з’єднані ребрами
всі вершини з’єднані
Граф називають зв’язаним, якщо:
будь-яка його пара вершин зв’язана
будь-яка вершина не має петлі
будь-яка його пара має дугу
будь-яка пара вершин має тільки одне ребро
Довжиною шляху називають:
кількість ребр у графі
кількість ребр, що виходять з вершини графа
кількість вершин і ребр у графі
кількість ребр, що входять у цей шлях
Циклом у графі називають:
шлях з одної вершини в суміжну вершину
шлях з одної вершини в висячу вершину
шлях з одної вершини в будь-яку вершину
шлях з одної вершини в ту саму вершину
Граф називають орієнтовним, якщо:
хоча б одне з ребр має напрям
більше половини ребр мають напрям
всі ребра мають напрям
у графі є ребра і дуги
Граф називають зваженим, якщо:
всі ребра мають вагу
у графі є ребра і дуги
хоча б одне ребро має вагу
у графі є ребра і дуги
Графи у комп’ютері подаються:
масивами
списками суміжних вершин
матрицями суміжності
кортежами суміжних вершин
Елементи матриці суміжності незваженого графа набувають значень:
номерів вершин
чисел 0 і 1
чисел від 1 до 9
чисел від 0 до 9
В алгоритмі пошуку у глибину на кожному кроці із поточної вершини:
вибирається одна суміжна вершина
вибираються усі суміжні вершини
вибираються усі суміжні вершини
вибирається найближня до неї вершина
В алгоритмах пошуку в ширину на кожному кроці із поточної вершини:
вибирається одна суміжна вершина
вибираються всі суміжні з нею вершини
вибирається найближня до неї вершина
вибирається випадкова вершина
В алгоритмах визначення найкоротшого шляху в графі між двома вершинами може відшукуватися:
шлях з мінімальною кількістю вершин
шлях із мінімальною сумою ваг ребр
шлях з мінімальною кількістю ребр
шлях з мінімальною кількістю вершин і ребр
Пошук найкоротшого шляху може виконуватися в таких графах:
змішаному
будь-якому
неорієнтованому
В алгоритмі Дейкстри відшукується найкоротший шлях:
від одної вершини до заданої
від одної вершини до всіх інших
від кожної вершини до всіх інших
від першої вершини до останньої
В алгоритмі Флойда — Уоршелла відшукується найкоротший шлях:
від одної вершини до всіх інших
від одної вершини до заданої
від кожної вершини до всіх інших
від першої вершини до останньої
