Тест по теме "Графы"

Тест: Основы теории графов Задание №1 Графом называется… 1) + пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; 2) 3) 4) ­ ­ ­ пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек; множество линий, соединяющих некоторые пары точек; пара двух конечных множеств: множество точек и множество линий. Задание №2 Точки графа называются… 1) Ответ: узлами Задание №3 Линии графа называются…  1) Ответ: ребрами Задание №4 Если ребро графа   соединяет две его вершины, то говорят, что это ребро им…  1) Ответ: инцидентно Задание №5 Если существует ребро, инцидентное двум вершинам графа, то эти вершины являются…  1) Ответ: смежными Задание №6 Ребро, имеющее совпадающие начало и конец, называется…  1) Ответ: петлей Задание №7 Ребра называются смежными, если они... инцидентны одной и той же вершине; параллельны; являются кратными. 1) + 2) 3) ­ ­ Задание №8 Какие из графов являются подграфами данного графа G: 1) + 2) + 3) + 4) ­ Задание №9 Эйлеров цикл… 1) 2) 3) + ­ ­ содержит каждое ребро только один раз; содержит каждую вершину только один раз; проходит через все вершины и ребра графа только один раз. Задание №10 Гамильтонов цикл… 1) ­ содержит каждое ребро только один раз; 2) 3) + ­ содержит каждую вершину только один раз; проходит через все вершины и ребра графа только один раз. Задание №11 В эйлеровом графе все вершины  1) 2) + ­ четной степени; нечетной степени. Задание №12 В полуэйлеровом графе допускаются 1) 2) 3) ­ + ­ 3 вершины нечетной степени; 2 вершины нечетной степени; 1 вершина нечетной степени. Задание №13 Какой   из   циклов   графа   с   множеством   вершин   {a,b,c,d,e,f}   является гамильтоновым? 1) 2) 3) 4) ­ ­ + ­  abeca fbecdf abecdfa abcdfca Задание №14 Какой граф является гамильтоновым: 1) ­ 2) + 3) + Задание №15 Граф содержит 7 дуг. Его эйлеров цикл будет состоять из: 1) 2) 3) 4) ­ + ­ ­ 6 дуг; 7 дуг; 8 дуг; 5 дуг. Задание №16 Простая цепь это: 1) 2) 3) 4) ­ ­ ­ + маршрут минимальной стоимости; маршрут, где нет повторяющихся вершин; маршрут, где нет повторяющихся ребер; маршрут, где нет повторяющихся вершин и ребер. Задание №17 Расстояние между вершинами есть... 1) 2) ­ + сумма длин ребер, входящих в путь; длина кратчайшего пути. Задание №18 Дерево есть... 1) 2) 3) 4) ­ ­ ­ + связный граф; граф без циклов; остовный подграф графа; связный граф без циклов. Задание №19 Если любые две вершины графа можно соединить простой цепью, то граф называется: 1) 2) 3) 4) + ­ ­ ­ связным; несвязным; деревом; остовом. Задание №20 Сколько вершин содержит гамильтонов цикл графа с 5 вершинами? 1) 2) 3) 4) + ­ ­ ­ 5; 4; 6; 7. Задание №21 Ребра называются кратными, если они... 1) 2) 3) 4) ­ ­ ­ + инцидентны одной и той же вершине; параллельны; являются смежными; имеют одинаковые направления. Задание №22 Расстояние до вершины дерева называют: 1) 2) 3) 4) + ­ ­ ­ ярусом вершины; высотой вершины; удаленностью вершины; этажом. Задание №23 Конечный   связный   граф   с   выделенной   вершиной   (корнем),   не   имеющий циклов, называют…  1) Ответ: деревом Задание №24 . Глубина элемента а2 в дереве    равна: а2 1) 2) 3) 4) ­ ­ + ­ 0; 1; 2; 3. Задание №25 а2 Степень вершины а2 в графе    равна: 1) 2) 3) 4) ­ ­ ­ + 0; 1; 2; 3. Задание №26 В графе из n вершин остов содержит: 1) 2) 3) ­ + ­  n+1 ребро; n­1 ребро; n ребер; 4) ­ 2n ребер. Задание №27 Упорядоченное   объединение   деревьев,   представляющее   собой   несвязный граф, называется…  1) Ответ: лесом Задание №28 Дерево,   в   котором   поддеревья   каждого   узла   образуют   упорядоченное подмножество называется..  1) Ответ: упорядоченным Задание №29 Если   каждая   из   вершин   неориентированного   графа   соединена   рёбрами   с остальными, то такой граф называется: 1) 2) 3) 4) ­ ­ ­ + гиперграфом; мультиграфом; цепью; полным графом. Задание №30 Последовательность   ребер,  в   которой   каждые   два   соседних   ребра  имеют общую вершину, и никакое ребро не встречается более одного раза – это… 1) 2) 3) 4) ­ + ­ ­ цикл; путь; дорога; прекция. Задание №31 После удаления из дерева одной из концевых вершин вместе с инцидентным ей ребром  получается: 1) 2) 3) 4) ­ + ­ ­ орграф; дерево; цепь; связь. Задание №32 Ребро   графа   является   |____|   тогда   и   только   тогда,   когда   в   графе   нет циклов,содержащих это ребро. 1) 2) 3) 4) ­ ­ + ­ связным мостом; связным графом; мостом; орграфом; Задание №33 Ребро связного графа G называется _____, если после его удаления G станет несвязным и распадется на два связных графа G’ и G".  1) Ответ: мост Задание №34 Бинарное дерево уровня n называется ____, если каждый его узел уровня n является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья.  1) Ответ: полным Задание №35 Висячие вершины дерева, за исключением корневой, называются... 1) Ответ: листьями Задание №36 Любой граф, изоморфный плоскому называется: 1) 2) 3) 4) ­ ­ ­ + Кратный Симметрический Хроматический Планарный Задание №37 Граф   называется   |____|,   если   существует   такое   разбиение   множества   его вершин на две части, что концы каждого ребра принадлежат разным частям. 1) 2) 3) 4) ­ + ­ ­ 2­хроматичным Двудольным Двойным Симметричным Задание №38 Для того, чтобы конечный связный граф был деревом, необходимо и достаточно, чтобы число его ребер было: 1) 2) 3) 4) ­ ­ ­ + Больше или равно числу его вершин Равно числу его вершин На единицу больше числа его вершин На единицу меньше числа его вершин Задание №39 Выберите верные утверждения: 1) 2) 3) 4) + + ­ ­ Цикломатическое число дерева равно нулю. Цикломатическое число леса равно нулю. Цикломатическое число леса равно всегда положительно Для   остальных   графов   цикломатические   числа   — отрицательные. Задание №40 Некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества, называется… 1) 2) 3) 4) ­ ­ + ­ Цикломатическим числом Кольцевой суммой Компонентой связности Степенью  Задание №41 Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную: 1) 2) 3) 4) ­ ­ ­ + 2; 1; 3; 0. Задание №42 Способы задания графа: 1) 2) 3) 4) + ­ ­ + Геометрический Указание вершин Перечисление ребер Матричный Задание №43 Геометрическое представление плоского графа называется его…  1) Ответ: реализацией Задание №44 Если   граф   имеет   матрицу   смежности   и   не   имеет   петель,   на   главной диагонали у него всегда стоят: 1) 2) + ­ нули; единицы. Задание №45 Выберите верные утверждения. В матрице инцидентности для неориентированного графа: 1) 2) 3) 4) + ­ ­ + bij = 1, если вершина Vi инцидентна ребру Xj; bij = 0, если вершина Vi  инцидентна ребру Xj; bij = ­1, если вершина Vi не инцидентна ребру Xj; bij = 0, если вершина Vi не инцидентна ребру Xj. Задание №46 Выберите верные утверждения. В матрице инцидентности для ориентированного графа: 1) 2) 3) 4) + + ­ + bij = 1, если вершина Vi является началом дуги Xj; bij = ­1, если вершина Vi является концом дуги Хj; bij = 0, если вершина Vi является концом дуги Хj; bij = 0, если вершина Vi не инцидентна дуге Xj. Задание №47 Выберите верные утверждения. 1) + 2) ­ 3) + 4) ­ Матрица   смежности   неориентированного   графа   является симметрической. Матрица   смежности   неориентированного   графа   меняется   при транспонировании Матрица смежности неориентированного графа не меняется при транспонировании. Матрица   смежности   неориентированного   графа     не   является симметрической. Задание №48 Граф называется ______, если каждому его ребру поставлено в соответствие некоторое число.  1) Ответ: сеть Задание №49 Минимально возможное описание сущности некоторого явления, объекта, события или процесса называется… 1) 2) 3) 4) ­ + ­ ­ Слот; Фрейм; Сеть; Вес. Задание №50 Набор   стандартных   единиц, информации о содержании и назначении фрейма  ­ это...   содержащих   определенный   минимум 1) Ответ: слот Задание №51 Любой   подграф   связного графа G, содержащий все вершины графа G и являющийся деревом, называется…  1) Ответ: остов Задание №52 Если вершине инцидентна петля, то степень этой вершины равна (запишите число):  1) Ответ: 2 Задание №53 Вершина графа, имеющая степень, равную нулю, называется: 1) 2) ­ ­ нулевой; отдельной; 3) 4) + ­ изолированной; висячей. Задание №54 Граф, состоящий из изолированных вершин, называется... 1) Ответ: нуль­граф Задание №55 Вершина графа, имеющая степень, равную 1, называется: 1) 2) 3) 4) ­ + ­ ­ изолированной; висячей; свободной; связной. Задание №56 Число нечетных вершин любого графа — … 1) Ответ: четно Задание №57 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж? 1) Ответ: 33 Задание №58 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л.   По   каждой   дороге   можно   двигаться   только   в   одном   направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? 1) Ответ: 36 Задание №59 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге  можно  двигаться  только в одном направлении,  указанном стрелкой. Сколько существует различных путей из города А в город З? 1) Ответ: 14 Задание №60 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К? 1) Ответ: 12 Задание №61 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ? 1) Ответ: 12 Задание №62 На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге  можно  двигаться  только в одном направлении,  указанном стрелкой. Сколько существует различных путей из города А в город К?  1) Ответ: 13 Задание №63 Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте К, через 14   часов   может   грозить   опасность.   Взяв   с   собой   карту,   он   немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Успеет ли рыцарь спасти Прекрасную Даму?  (Ответ запишите в форме: Нет АБЕК 17 или Да АБЕК 17) 1) Ответ: Да АБВЖГИЗК 14 Задание №64 Винни­Пух   вышел   на   прогулку,   взяв   с   собой   карту.   Числа   на   рисунке обозначают   время  движения  (в минутах)  от  пункта  до  пункта. Помогите Винни­Пуху найти кратчайший путь от своего дома в пункте А до дома Пятачка в пункте К. Перечислите пункты, через которые должен пройти Винни­Пух, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме: АВЖЗДК 80) 1) Ответ: АБЕДЗК 60 Задание №65 Атос поскакал в гости к Портосу, взяв с собой карту. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. Перечислите пункты, через которые должен проехать Атос, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме:  ЕКЗИГД 20)  1) Ответ: ЕЖВБАД 12 Задание №66 Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте О, ровно через сутки может грозить опасность. Взяв с собой карту,  он немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от   пункта   до   пункта.   Успеет   ли   рыцарь   спасти   Прекрасную   Даму? Обоснуйте ответ, указав кратчайший маршрут и время, затраченное на весь путь. (Ответ запишите в форме: Нет АБВГО 38 или Да АБВГО 38) 1) Ответ: Нет АКЛДО 25 Задание №67 Во дворе живут 4 пёсика: Бобик, Робик, Тобик и Толстолобик. Каждому из них случалось драться с кем­нибудь из остальных, причём у Бобика, Робика и Тобика число тех, с кем они дрались – разное. Со сколькими собаками двора дрался Толстолобик?  1) Ответ: 2 Задание №68 Лес состоит из 10 деревьев. Всего в лесу 200 вершин. В нём ___ребер.  1) Ответ: 190 Задание №69 Каждое ребро графа покрасили в синий или зелёный цвет так, что ни из одной вершины не выходит двух одноцветных рёбер. Синих рёбер оказалось на 5 больше, чем зелёных. Какое наименьшее число компонент связности может иметь этот граф? 1) Ответ: 5 Задание №70 Сколько всего рёбер в графе, степени вершин которого равны 3, 4, 5, 3, 4, 5, 3, 4, 5? 1) 2) 3) ­ ­ + 10; 20; 18. Задание №71 В деревне Вишкиль  9 домов. Из каждого дома тянется четыре шланга к четырём другим домам. Сколько шлангов в деревне? 1) 2) 3) ­ + ­ 16; 18; 36. Задание №72 Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным? 1) 2) 3) ­ + ­ 18; 14; 15. Задание №73 Сколько рёбер в полном графе с 20 вершинами? 1) 2) 3) ­ ­ + 180 200 190 Задание №74 Цикломатическое число графа рассчитывается по формуле: v(G) = m(G) + c(G) – n(G), где: 1) 2) 3) 3 1 2 m(G) c(G) n(G) число   связных   компонент графа число вершин число его ребер 1) 2) 3) Задание №75 Соотнесите понятия  и определения: Цепь 1) 2 Цикл 2) 4 Последовательность   ребер неориентированного графа, в 1) которой   вторая   вершина ребра предыдущего   совпадает с первой вершиной следующего 2) Маршрут , в котором ребро встречается только один раз Маршрут 3) 1 Путь 4) 3 Задание №76 Соотнесите понятия  и определения: Связные графы 1) 2 2) 3) 3 1 Упорядоченная последовательность ребер   ориентированного 3) графа,   в   которой   конец предыдущего ребра     совпадает   началом следующего   и   все   ребра с единственны Путь, у которого совпадают начало и конец Любые   подграфы   связного   содержащие   все графа, вершины   графа   G   и являющиеся деревом   между   любыми Графы, двумя   вершинами   которых есть маршрут 4) 1) 2) Планарные(плоские) графы Остовы 3) Графы,   которые   имеют изоморфные   им   графы,   в изображении   которых   на ребра плоскости пересекаются   только   в вершинах Графы,   имеющие   взаимно­ однозначное   соответствие между   их   ребрами   и вершинами,   причем   со­ 4) ответствующие ребра соединяют   соответствующие   вершины Изоморфные графы 4) 4 Задание №77 Установите соответствие: Объединение графов 1) 3 1) Пересечение графов 2) 2 2) Подграф  3) 3 3) Кольцевая сумма 4) 4 4) Задание №78 Установите соответствие: Граф   со   смежными вершинами Полный граф Граф   со   смежными ребрами Граф с петлей 1) 2) 3) 4) 1) 4 2) 3 3) 1 4) 2 Задание №79 Соотнесите понятия и определения: 1) 4 Строго бинарное дерево 1) Бинарное   дерево,   каждый узел   уровня   n   которого является   листом,   а   каждый узел   уровня   меньше,   чем   n, имеет   непустое   левое   и Полное бинарное дерево правое поддеревья. подмножество   множества деревьев, когда каждый узел 2) либо  является  листом,  либо образует   два   поддерева: левое и правое. Бинарное дерево дерево,   в   котором 3) поддеревья   каждого   узла образуют   упорядоченное подмножество. Упорядоченное дерево такой   граф,   у   которого каждый узел, не являющийся листом,   содержит   два   и 4) только   два   поддерева   — левое и правое. 2) 1 3) 2 4) 3 Задание №80 Укажите степени вершин графа  1) V1 2) V2 2 5 3) V3 4) V4 5) V5 6) V6 7) V7 3 3 3 4 4 Задание №81 Укажите степени вершин графа  1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 5 4 5 6 4 5 Задание №82 Укажите степени вершин графа 1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 7) V7 4 4 4 4 5 5 6 Задание №83 Укажите степени вершин графа  1) V1 2) V2 3) V3 4) V4 5) V5 6) V6 4 3 5 2 3 4 7) V7 5 Задание №84 Найдите цикломатическое число графа G  1) Ответ: 6 Задание №85 Найдите цикломатическое число графа G  1) Ответ: 9 Задание №86 Найдите цикломатическое число графа G  1) Ответ: 10 Задание №87 Найдите цикломатическое число графа G  1) Ответ: 7 Задание №88 Найдите цикломатическое число графа G 1) Ответ: 0