Тест: Дискретная матиматика. Графы

Целью данного онлайн-теста для 11 класса является проверка знаний и понимания базовых понятий, связанных с темой «Дискретная матиматика. Графы». Тест поможет оценить уровень владения темой, а также способность применять полученные знания в понимании материала и ответе на вопросы.

После ответа на все вопросы ученик получит результат теста с оценкой. Этот онлайн-тест поможет укрепить свои навыки и углубить понимание в предмете Математика.

---

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

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

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

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

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

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

перечислить некоторые элементы;

перечислить все его элементы

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

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

отношение эквивалентности

отношение эквивалентности

4 Граф - это...

только две точки, которые соединяются линиями

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

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

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

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

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

совокупность чисел.

перечень одинаковых элементов;

набор каких-либо элементов;

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

в графе G есть дуга (y,x)

в графе G есть дуга (x,y)

вершины x и y инцидентны дуге v

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

Кратными

Смежными

Параллельными

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

Все его ребра ориентированы

Все его вершины соединены друг с другом

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

Все его ребра кратны

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

Инцидентными

Четными

Висячими

Изоморфными

Изолированными

Ссмежными

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

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

нет правильного ответа

в нагруженном неорграфе

и в нагруженном орграфе и в нагруженном неорграфе

в нагруженном орграфе

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

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

Все его ребра кратны

Все его ребра ориентированы

Все его вершины соединены друг с другом

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

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

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

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

кратные ребра

смежные ребра

ориентированные ребра

неорентированные ребра

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

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

ровно две простые цепи

единственную простую цепь

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

цепью

полным графом

мультиграфом

гиперграфом

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

вершинами графа

узлами графа

пунктами графа

ребрами графа

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

Инцидентные

Четные

Висячие

Изоморфные

Изолированные

Смежные

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

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

Нет правильного ответа

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

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

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

ровно n-1 висячая вершина

нет висячих вершин

хотя бы две висячие вершины

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

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

Все его вершины соединены друг с другом

Все его ребра ориентированы

Все его ребра кратны

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

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

только простой цикл

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

только простую цепь

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

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

циклом

контуром

цепью

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

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

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

матрица, все элементы которой — единичные

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

графом

псевдографом

мультиграфом

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

вершина x конец дуги v

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

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

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

Не знаю

Нет

Да

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

нет

да

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

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

матрица В(7х4)

матрица В(4х7)

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

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

Все ответы верны

Нет правильного ответа

Число входящих в нее дуг

Число соединенных с ней вершин

Число исходящих из нее дуг

Число ребер, одним из концов которых она является

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

перешейка(дуги)

циклового ребра

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

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

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

число вершин полного неориентированного графа n = m(m+1)/2

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

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

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

алгоритм обхода графа «в глубину»

алгоритм Флойда

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

Изолированной

Доминирующей

Висячей

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

графом

псевдографом

мультиграфом

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

всегда нечетно

всегда есть

всегда четно

произвольно

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

Отдельной

Висячей

Изолированной

Показать результат

---