Дискретная математика тест-драйв по дискретной математике и математи
..pdf1.3. Эйлеровы графы, цикломатическое ихроматическое числа
Уровень – легкий
t1. Эйлерова цепь в неориентированном графе – это цепь, включающая все
(1): ребра, и притом по одному разу (2): вершины, и притом по одному разу (3): ребра (4): вершины
t2. Эйлеров цикл – это
(1): эйлерова цепь, не являющаяся циклом (2): цепь, включающая все вершины, и притом по одному разу
(3): цепь, включающая всевершины, ипритом непо одному разу (4): эйлерова цепь, являющаяся циклом
t3. Эйлеров граф содержит (1): эйлеров цикл (2): гамильтонов цикл
(3): незамкнутую эйлерову цепь (4): незамкнутый эйлеров маршрут
t4. Эйлеров цикл существует (1): только в несвязных графах (2): в деревьях (3): только в связных графах (4): в лесах
t5. Эйлеров цикл в неориентированном графе существует тогда и только тогда, когда он
(1): связен и степени всех вершин нечетны (2): несвязен и степени всех вершин нечетны (3): связен и степени всех вершин четны (4): несвязен и степени всех вершин четны
51
t6. Эйлерова цепь существует тогда и только тогда, когда число вершин нечетной степени не превосходит
(1): 1 (2): 2 (3): 3 (4): 4
t7. Граф, который может быть изображен на плоскости так, что все пересечения ребер являются вершинами, называется
(1): двудольным (2): хроматическим (3): циклическим (4): планарным
t8. Граф, вкоторомвсевершинысвязаныдругсдругом, называется (1): идеальным (2): полным (3): универсальным (4): нормальным
Уровень – средний
t9. Эйлеров цикл в ориентированном графе существует тогда и только тогда, когда для каждой вершины ее полустепень захода … полустепени исхода
(1): равна (2): больше (3): меньше (4): не равна
t10. Граф называется р-хроматическим, если его вершины можно раскрасить р цветами так, что никакие … вершины не будут раскрашены одинаково
(1): несмежные
(2): две
(3): две смежные
(4): три
52
t11. Граф называется бихроматическим, если его вершины можно раскрасить двумя цветами так, что никакие … вершины не будут раскрашены одинаково
(1): несмежные
(2): две (3): три
(4): две смежные
t12. Граф, который может быть представлен двумя непересекающимися подмножествами вершин, называется
(1): тривиальным (2): нормальным (3): бинормальным (4): двудольным
Уровень – сложный
t13. Цикломатическое число графа с n вершинами и m ребрами вычисляется как
(1): m – n + 1 (2): m + n + 1 (3): m – n – 1 (4): m + n – 1
t14. Цикломатическое число графа «квадрат» с 4 вершинами и 4 ребрами равно
(1): 0 (2): 2 (3): 3 (4): 1
t15. Цикломатическое число графа «треугольник» с 3 вершинами и 3 ребрами равно
(1): 3 (2): 1 (3): 2 (4): 0
53
t16. Цикломатическое число |
графа «четырехконечный |
крест» |
||
с 5 вершинами и 4 ребрами равно |
|
|
|
|
(1): 1 |
|
|
|
|
(2): 2 |
|
|
|
|
(3): 0 |
|
|
|
|
(4): 4 |
|
|
|
|
t17. Хроматическое |
число графа |
«квадрат» с 4 вершинами |
||
и 4 ребрами равно |
|
|
|
|
(1): 1 |
|
|
|
|
(2): 4 |
|
|
|
|
(3): 2 |
|
|
|
|
(4): 3 |
|
|
|
|
t18. Хроматическое число графа «треугольник» с 3 вершинами |
||||
и 3 ребрами равно |
|
|
|
|
(1): 3 |
|
|
|
|
(2): 1 |
|
|
|
|
(3): 2 |
|
|
|
|
(4): 0 |
|
|
|
|
t19. Хроматическое |
число |
графа |
«четырехконечный |
крест» |
с 5 вершинами и 4 ребрами равно
(1): 1 (2): 3 (3): 4 (4): 2
1.4. Покрытия, связность, трансверсали
Уровень – легкий
t1. Вершина графа покрывает (1): инцидентные ей ребра (2): смежные ей вершины (3): инцидентные ей вершины
(4): метки соответствующих ребер
54
t2. Ребро графа покрывает (1): смежные ему ребра (2): инцидентные ему вершины (3): смежные ему вершины (4): метку данного ребра
t3. Вершинное покрытие графа – это множество (1): ребер, покрывающих все вершины (2): названий вершин (3): меток ребер
(4): вершин, покрывающих все ребра
t4. Реберное покрытие – это множество (1): ребер, покрывающих все вершины (2): вершин, покрывающих все ребра (3): меток ребер (4): названий вершин
t5. Наименьшее число вершин во всех вершинных покрытиях называется числом
(1): реберного покрытия (2): Эйлера (3): вершинного покрытия (4): Кенигсберга
t6. Наименьшее число ребер во всех реберных покрытиях называется числом
(1): вершинного покрытия (2): Стирлинга (3): реберного покрытия (4): Паскаля
Уровень – средний
t7. Множество вершин графа независимо, если (1): все они смежны (2): некоторые из них смежны
55
(3): все они инцидентны (4): никакие две из них не смежны
t8. Наибольшее число вершин в независимом множестве вершин называется
(1): реберным числом независимости (2): вершинным числом независимости (3): числом вершинного покрытия (4): числом реберного покрытия
t9. Графы не бывают связаны (1): сильно (2): двухсторонне
(3): односторонне (4): слабо
t10. Если в орграфе существует ориентированная цепь из одной вершины в другую и наоборот, то они
(1): сильно связаны (2): односторонне связаны (3): слабо связаны (4): не связаны
t11. Двудольный граф разбивается на пары тогда, когда любые k элементов одной из долей связаны по крайней мере с … другой доли
(1): k – 1 элементом (2): k – 2 элементами (3): k – 3 элементами (4): k элементами
Уровень – сложный
t12. Для двудольного графа Г (V, E) = {е1, е2, е3, е4}; {{v1, v4, v5}, {v1}, {v2, v3, v4}, {v2, v4}} трансверсалью является
(1): {v1, v1, v3, v4} (2): {v4, v1, v4, v2}
56
(3): {v5, v1, v3, v4} (4): {v4, v1, v2}
t13. Для графа «треугольник» с тремя вершинами и тремя ребрами наименьшее реберное покрытие составляет
(1): два ребра (2): одно ребро (3): три ребра (4): четыре ребра
t14. Для графа «треугольник» с тремя вершинами и тремя ребрами наименьшее вершинное покрытие составляет
(1): одна вершина (2): три вершины (3): две вершины (4): четыре вершины
t15. Для графа «квадрат» с четырьмя вершинами и четырьмя ребрами наименьшее реберное покрытие составляет
(1): одно ребро (2): три ребра (3): два ребра (4): четыре ребра
t16. Для графа «квадрат» с четырьмя вершинами и четырьмя ребрами наименьшее вершинное покрытие составляет
(1): одна вершина (2): две вершины (3): три вершины (4): четыре вершины
57
1.5. Анализ графа цепи Маркова
Уровень – легкий
t1. Цепь Маркова – это
(1): неориентированный граф (2): цепь в орграфе
(3): цепь в неориентированном графе (4): орграф
t2. Граф марковской цепи – это ориентированный граф, нагруженный … перехода из состояния в состояние
(1): вероятностями или интенсивностями (2): стоимостями (3): условиями (4): временами
t3. Если в графе марковской цепи существует предельное распределение вероятностей, не зависящее от начального состояния, то такой процесс называется
(1): динамическим (2): критическим (3): эргодическим (4): статическим
t4. Если в графе марковской цепи существует предельное распределение вероятностей, не зависящее от начального состояния, то это определяет
(1): динамический режим (2): установившийся режим (3): статический режим (4): критический режим
58
t5. В установившемся режиме марковская цепь описывается системой
(1): логических уравнений (2): интегральных уравнений
(3): пропорционально-интегрально-дифференциальныхуравнений (4): алгебраических уравнений
t6. В установившемся режиме система уравнений марковской цепи по каждой вершине графа приравнивается
(1): к 1 (2): 0 (3): –1 (4): 0,5
t7. Количество уравнений для описания марковской цепи равно числу
(1): дуг
(2): вершин + дуг (3): вершин (4): вершин – дуг
t8. Уравнение по каждой вершине марковской цепи составляется путем анализа
(1): только исходящих дуг (2): только входящих дуг (3): исходящих и входящих дуг (4): только петель
t9. Для составления уравнений марковской цепи по данной вершине необходимо вероятность данного состояния
(1): умножать на интенсивность перехода по входящей дуге (2): делить на интенсивность перехода по исходящей дуге (3): делить на интенсивность перехода по входящей дуге (4): умножать на интенсивность перехода по исходящей дуге
59
t10. Для составления уравнений марковской цепи по данной вершине необходимо интенсивность перехода по входящей дуге
(1): умножать на вероятность данного состояния (2): умножать на вероятность состояния, изкоторого онаисходит (3): делить на вероятность данного состояния
(4): делить на интенсивность перехода по исходящей дуге
t11. Произведение вероятности данного состояния на интенсивность перехода по исходящей дуге
(1): берется со знаком «+» (2): приравнивается к 0 (3): берется со знаком «–» (4): приравнивается к 1
t12. Произведение интенсивности перехода по входящей дуге в данноесостояниена вероятность состояния, из которого онаисходит,
(1): берется со знаком «–» (2): берется со знаком «+» (3): приравнивается к 0 (4): приравнивается к 1
Уровень – средний
t13. Для решения системы алгебраических уравнений марковской цепи в нее включают
(1): сумму вероятностей всех состояний (2): сумму вероятностей половины состояний (3): разность вероятностей всех состояний
(4): произведение вероятностей всех состояний
t14. Отображение – это
(1): не полностью определенное соответствие (2): множество всех подмножеств (3): полностью определенное соответствие
(4): множество одноэлементных подмножеств
60