Практика · Математика

Пройти тест онлайн «Дискретная матиматика. Графы»

Проверьте, насколько уверенно вы разбираетесь в теме «Дискретная матиматика. Графы». Выберите ответы и посмотрите результат после завершения теста.

11 класс 36 вопросов

Перед началом

Как проходить тест

Все вопросы находятся на этой странице. Отвечайте в удобном темпе и проверьте выбор перед отправкой.

01
Прочитайте вопрос и выберите один вариант ответа.
02
Пройдите остальные вопросы. Ответ можно изменить до отправки.
03
Нажмите «Завершить тест», чтобы увидеть результат.

Задания

Вопросы теста

Вопрос 1 из 36

Эйлеровым циклом называется

цикл, проходящий по всем вершинам графа ровно по одному разу
цикл, проходящий по всем ребрам графа ровно по одному разу

Вопрос 2 из 36

Точки графа называются...

ребрами графа
пунктами графа
вершинами графа
узлами графа

Вопрос 3 из 36

Степенью вершины называется...

Число ребер, одним из концов которых она является
Число соединенных с ней вершин
Число исходящих из нее дуг
Число входящих в нее дуг
Нет правильного ответа
Все ответы верны

Вопрос 4 из 36

Связность графа не меняется при удалении

циклового ребра
перешейка(дуги)

Вопрос 5 из 36

Отношение взаимодостижимости на графе есть

отношение эквивалентности
отношение эквивалентности
отношение строгого порядка

Вопрос 6 из 36

Множество – это …

набор каких-либо элементов;
перечень одинаковых элементов;
совокупность элементов, обладающих некоторым признаком, свойством;
совокупность чисел.

Вопрос 7 из 36

Между выбранными двумя вершинами x и у произвольного дерева можно построить

единственную простую цепь
ровно две простые цепи
в зависимости от вида дерева различное количество простых цепей

Вопрос 8 из 36

Матрица смежности произвольного неорграфа есть

квадратная несимметричная матрица, элементами главной диагонали которой являются нулевые элементы
квадратная симметричная матрица, элементами главной диагонали которой могут быть и нули и единицы
квадратная симметричная матрица, элементы главной диагонали которой равны нулю
Нет правильного ответа

Вопрос 9 из 36

Матрица инцидентности неорграфа G(X,V), |X|= 7, |V|= 4 есть

квадратная матрица В(4х4)
матрица В(4х7)
квадратная матрица В(7х7)
матрица В(7х4)

Вопрос 10 из 36

Матрица достижимости связного неорграфа есть

матрица, все элементы которой — единичные
матрица, элементы главной диагонали которой равны нулю, остальные элементы — единичные
матрица, равная матрице смежности данного неорграфа

Вопрос 11 из 36

Маршрут в неорграфе, конечная и начальная вершина которого не совпадают, называется

цепью
контуром
циклом

Вопрос 12 из 36

Каким образом можно задать множество?

перечислить все его элементы
перечислить некоторые элементы;
указать свойство, которым обладают только элементы, принадлежащие данному множеству

Вопрос 13 из 36

Если каждая из вершин неориентированного графа соединена рёбрами с остальными, то такой граф называется

гиперграфом
мультиграфом
цепью
полным графом

Вопрос 14 из 36

Если две различные вершины графа соединены более чем одним ребром, то такие ребра называются

Параллельными
Смежными
Кратными

Вопрос 15 из 36

Если две вершины соединены ребром, то они называются...

Смежные
Изоморфные
Изолированные
Висячие
Четные
Инцидентные

Вопрос 16 из 36

Если два ребра соединены общей вершиной, то они называются...

Ссмежными
Изоморфными
Изолированными
Висячими
Четными
Инцидентными

Вопрос 17 из 36

Дуги в графе - это

неорентированные ребра
ориентированные ребра
кратные ребра
смежные ребра

Вопрос 18 из 36

Для того, чтобы в графе существовала эйлерова цепь необходимо и достаточно, чтобы

все вершины графа имели четные степени
ровно две вершины имели четные степени
ровно две вершины имели нечетные степени

Вопрос 19 из 36

Для любого орграфа всегда истинно выражение «Любая вершина графа смежна сама себе»

да
нет

Вопрос 20 из 36

Для любого неорграфа истинно выражение "Если вершина x смежна вершине y, то и вершина y смежна вершине x"

Да
Нет
Не знаю

Вопрос 21 из 36

Для выделения компонент связности можно использовать

алгоритм Флойда
алгоритм обхода графа «в глубину»
алгоритм Дейкстры

Вопрос 22 из 36

Граф с петлями и кратными ребрами называется

мультиграфом
псевдографом
графом

Вопрос 23 из 36

Граф называется связным, если...

Все его вершины соединены между собой
Все его ребра кратны
Все его вершины соединены друг с другом
Все его ребра ориентированы

Вопрос 24 из 36

Граф называется планарным, если...

Все его вершины соединены друг с другом
Все его ребра ориентированы
Все его вершины соединены между собой
Все его ребра кратны

Вопрос 25 из 36

Граф называется орграфом, если...

Все его ребра кратны
Все его вершины соединены между собой
Все его ребра ориентированы
Все его вершины соединены друг с другом

Вопрос 26 из 36

Граф без петель называется

мультиграфом
псевдографом
графом

Вопрос 27 из 36

Граф - это...

множество точек, две из которых обязательно соединяются линиями
множество точек, которые никогда не соединяются линиями
только две точки, которые соединяются линиями
множество точек, которые могут соединяться линиями

Вопрос 28 из 36

Выберите истинные высказывания

у полного неориентированного графа р(xi) = m-1, где m - число рёбер
число вершин полного неориентированного графа n = m(m+1)/2
у полного неориентированного графа р(xi) = n-1, где n - число вершин
число рёбер полного неориентированного графа m = n(n-1)/2, где n - число вершин

Вопрос 29 из 36

Вершину, не принадлежащую ни одному ребру называют ...

Изолированной
Висячей
Отдельной

Вопрос 30 из 36

Вершина графа первой степени называется ...

Висячей
Доминирующей
Изолированной

Вопрос 31 из 36

В произвольном дереве можно выделить

как простую цепь, так и цепь, не являющуюся простой
только простую цепь
только простой цикл
как простой цикл, так и цикл, не являющийся простым

Вопрос 32 из 36

В орграфе G вершина x смежна вершине y если

вершины x и y инцидентны дуге v
в графе G есть дуга (x,y)
в графе G есть дуга (y,x)

Вопрос 33 из 36

В орграфе G вершина x инцидентна дуге v если

вершина x — начало дуги v
вершина x либо начало дуги v, либо конец дуги v
вершина x конец дуги v

Вопрос 34 из 36

В любом произвольном неорграфе число вершин нечетной степени

произвольно
всегда четно
всегда нечетно
всегда есть

Вопрос 35 из 36

В любом дереве

хотя бы одна висячая вершина
хотя бы две висячие вершины
ровно n-1 висячая вершина
нет висячих вершин

Вопрос 36 из 36

Алгоритм Дейкстры ищет минимальный путь между заданными вершинами x и y

в нагруженном орграфе
в нагруженном неорграфе
и в нагруженном орграфе и в нагруженном неорграфе
в произвольном графе (как нагруженном, так и не нагруженном)
нет правильного ответа

Готовы проверить свои ответы?