С.Ф. Тюрин, Ю.А. Аляев ДИСКРЕТНАЯ МАТЕМАТИКА ТЕСТ-ДРАЙВ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ И МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

1.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

с 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