игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Дискретный анализ / Тест 12

Дискретный анализ - тест 12

Упражнение 1:
Номер 1
Появление теории графов как математической дисциплины связывают с датой этого события:

Ответ:

 (1) появление задач о структуре молекул 

 (2) появление статьи Эйлера о Кенигсбергских мостах 

 (3) формулировка задач об электрических сетях 

 (4) постановка проблемы четырех красок 


Номер 2
Укажите название известной головоломки: "Можно ли произвольную географическую карту раскрасить в 4 цвета так, чтобы ни одни 2 государства, граница которых имеется и отлична от точки, не были окрашены в один и тот же цвет".

Ответ:

 (1) выбор цветовой модели 

 (2) задача о карте Европы 

 (3) проблема четырех красок 

 (4) задача коммивояжера 


Номер 3
Укажите приложения теории графов:

Ответ:

 (1) задачи изучения электричеких цепей 

 (2) задача коммивояжера 

 (3) минимизация булевых функций 

 (4) задачи о существовании эфективных алгоритмов 


Упражнение 2:
Номер 1
Что соответствует вершинам и ребрам графа, который описывает "Задачу о четырех красках":

Ответ:

 (1) страны изображаются в виде вершин, ребра соединяют вершины, если между соответствующими им странами имеется граница, отличная от точки  

 (2) страны изображаются в виде вершин, ребра соединяют вершины, если соответствующие им страны окрашены на карте в одинаковый цвет 

 (3) вершины изображают точки, где пересекаются границы трех и более государств, ребра соответствуют линиям границы между государствами 


Номер 2
Для графов с каким количеством вершин удобно их графическое представление в виде точек и соединяющих их линий:

Ответ:

 (1)

 (2) 50 

 (3) 500 


Номер 3
Какая задача в терминах теории графов решалась в связи с проблемой неплатежей после начала перестройки, при наличии списка должников:

Ответ:

 (1) задача поиска простого пути 

 (2) задача поиска циклов с целью устранения их 

 (3) задача о четырех красках 


Упражнение 3:
Номер 1
Как формально определяется граф:

Ответ:

 (1) множество ориентированных и неориентированных отрезков 

 (2) множество точек и соединяющих их отрезков 

 (3) совокупность из двух множеств: множества вершин и множества ребер (дуг) 


Номер 2
Как формально определяется множество ребер неориентированного графа:

Ответ:

 (1) math, где math - упорядоченная пара вершин 

 (2) math, где math - неупорядоченная пара вершин 

 (3) набор ненаправленных отрезков 


Номер 3
Как формально определяется множество ребер ориентированного графа:

Ответ:

 (1) math, где math - упорядоченная пара вершин 

 (2) math, где math - неупорядоченная пара вершин 

 (3) набор отрезков, некоторые из которых являются направленными 


Упражнение 4:
Номер 1
Как называется граф, в котором есть и ориентированные, и неориентированные ребра:

Ответ:

 (1) ориентированный граф 

 (2) неориентированный граф 

 (3) смешанный граф 

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


Номер 2
Укажите, где понятие "инцидентность" использовано верно:

Ответ:

 (1) ребро math инцидентно вершинам math и math 

 (2) два ребра инцидентны 

 (3) две вершины индидентны 


Номер 3
Укажите, где понятие "смежность" использовано верно:

Ответ:

 (1) ребро math смежно с вершинами math и math 

 (2) два ребра смежные 

 (3) две вершины смежные 


Упражнение 5:
Номер 1
Укажите выражения, описывающие количество ребер в полном неориентированном графе с количеством вершин math:

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Номер 2
Укажите выражение, описывающие количество ребер в полном ориентированном графе с количеством вершин math:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Номер 3
Укажите соотношение между количество ребер в полном ориентированном графе и количеством ребер в полном неориентированном графе, оба графа с количеством вершин math:

Ответ:

 (1) количество ребер в этих графах одинаково 

 (2) количество ребер полного ориентированного графа в два раза больше, чем количество ребер полного неориентированного графа 

 (3) количество ребер полного ориентированного графа в два раза меньше, чем количество ребер полного неориентированного графа 

 (4) в силу разнообразия полных графов невозможно вывести точное соотношение 


Упражнение 6:
Номер 1
Неориентированный граф называют простым графом, если этот граф:

Ответ:

 (1) не имеет петель и кратных ребер 

 (2) не является полным 

 (3) не имеет кратных ребер, но может иметь петли 

 (4) не имеет петель и кратных ребер, степень каждой вершины графа равна единице 


Номер 2
Вершине неориентированного графа инцидентны три ребра, петель и кратных ребер в графе нет. Определите степень вершины:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Укажите вершины графа, степень которых равна нулю:

Ответ:

 (1) изолированная вершина 

 (2) вершина, которой инцидентно два ребра и не имеющая петель 

 (3) любая вершина полного графа 

 (4) любая вершина простого графа 


Упражнение 7:
Номер 1
В неориентированном графе количество вершин нечетной степени:

Ответ:

 (1) нечетно 

 (2) четно 

 (3) может быть как четным, так и нечетным 


Номер 2
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Ответ:

 (1) (4,3,3,3) 

 (2) (4,4,3,3) 

 (3) (4,3,3,3,3) 

 (4) (1,2,3,4,5) 


Номер 3
Для доказательства изоморфности двух графов:

Ответ:

 (1) достаточно определить взаимнооднозначное соответствие между вершинами этих графов 

 (2) необходимо установить взаимноознозначное соответствие между вершинами этих графов 

 (3) достаточно установить взаимноознозначное соответствие между вершинами этих графов, сохраняющее свойство "быть связанным ребром" 


Упражнение 8:
Номер 1
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Ответ:

 (1) (1,1,1,1,1) 

 (2) (10,10,3,2) 

 (3) (4,5,4,5,4) 

 (4) (11,1,2,2,3) 


Номер 2
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Ответ:

 (1) (1,2,3,4,5,6) 

 (2) (4,4,3,2) 

 (3) (4,3,4,3,4) 

 (4) (1,1,2,2,3) 


Номер 3
Отметьте среди последовательностей степеней вершин такие, которым соответствует реально существующий граф:

Ответ:

 (1) (1,3,3,3) 

 (2) (2,3,3,3) 

 (3) (2,3,2,3,2) 

 (4) (1,2,3,4) 


Упражнение 9:
Номер 1
Способ представления графа в виде матрицы, в которой строки соответствуют вершинам графа, а столбцы - ребрам, называется:

Ответ:

 (1) список смежности 

 (2) список инцидентности 

 (3) матрица смежности 

 (4) матрица инциденций 


Номер 2
Укажите способы машинного представления графа:

Ответ:

 (1) графический способ 

 (2) матрица смежности 

 (3) матрица инциденций 

 (4) списки инциденций 

 (5) списки смежности 


Номер 3
При котором из способов представления графа матрица для его представления всегда квадратная:

Ответ:

 (1) матрица смежности 

 (2) матрица инциденций 

 (3) списки инциденций 


Упражнение 10:
Номер 1
Укажите самый неудобный способ машинного представления графа:

Ответ:

 (1) матрица смежности 

 (2) списки инциденций 

 (3) матрица инциденций 


Номер 2
Способ представления графа в виде матрицы, в которой столбцы и строки соответствуют вершинам графа, называется:

Ответ:

 (1) матрица смежности 

 (2) списки инциденций 

 (3) матрица инциденций 


Номер 3
Укажите достоинства списков инциденций как способа машинного представления графа:

Ответ:

 (1) свобода модификации этого списка 

 (2) абсолютная экономия места 

 (3) список используется в программном смысле этого слова 

 (4) необходимость регулярно чистить память машины 


Упражнение 11:
Номер 1
Длина пути в графе - это:

Ответ:

 (1) количество ребер, входящих в путь 

 (2) количество вершин, входящих в путь 

 (3) сумма количества ребер и количества вершин, входящих в путь 


Номер 2
Путь в графе - это:

Ответ:

 (1) любая последовательность вершин графа 

 (2) такая последовательность вершин графа, в которой любые две последовательно перечисленные вершины соединены ребром 

 (3) последовательность всех вершин графа 


Номер 3
Путь назвается простым, если:

Ответ:

 (1) начальная и конечная вершины пути различны 

 (2) путь проходит через все вершины пути 

 (3) все вершины пути, кроме, быть может, первой и последней, различны 


Упражнение 12:
Номер 1
Цикл, по определению, - это:

Ответ:

 (1) любой путь, у которого начальная и конечная вершины совпадают 

 (2) простой путь, у которого начальная и конечная вершины совпадают 

 (3) проходящий через все вершины графа простой путь, у которого начальная и конечная вершины совпадают 


Номер 2
Какова минимальная длина цикла в простом графе:

Ответ:

 (1)

 (2)

 (3)


Номер 3
Укажите верные утверждения:

Ответ:

 (1) некоторые пути являются циклами 

 (2) все циклы являются путями 

 (3) все простые пути являются циклами 

 (4) все циклы являются простыми путями 


Упражнение 13:
Номер 1
Как соотносятся между собой графы math и math, если множество вершин графа math является подмножеством вершин графа math и все ребра графа math яаляются ребрами графа math:

Ответ:

 (1) граф math является изоморфным графу math 

 (2) граф math является циклом в графе math 

 (3) граф math является подграфом графа math 

 (4) граф math является частью графа math 


Номер 2
Как соотносятся между собой графы math и math, если множество вершин графа math является подмножеством вершин графа math и множество ребер графа math состоит из всех ребер графа math, соединяющих вершины графа math:

Ответ:

 (1) граф math является циклом в графе math 

 (2) граф math является изоморфным графу math 

 (3) граф math является подграфом графа math 

 (4) граф math является частью графа math 


Номер 3
Укажите верные утверждения:

Ответ:

 (1) любая часть графа является подграфом исходного графа 

 (2) любой подграф является частью исходного графа 

 (3) некоторые части графа являются его подграфами 

 (4) подграф некоторого графа может содержать вершины, которые не содержатся в исходном графе 


Упражнение 14:
Номер 1
По определению, две вершины называются связанными, если:

Ответ:

 (1) эти вершины смежные 

 (2) существует путь, для которого одна из двух рассматриваемых вершин является начальной вершиной, а вторая - конечной вершиной 

 (3) существуют кратные ребра, соединяющие эти вершины 

 (4) степени этих двух вершин численно равны друг другу 


Номер 2
По определению, граф называется связным, если:

Ответ:

 (1) все вершины графа попарно связаны 

 (2) некоторые вершины графа попарно связаны 

 (3) все вершины графа связаны только простыми путями 

 (4) через каждую вершину графа проходит более двух простоых путей 


Номер 3
Представление графа в виде объединения связанных компонент - это:

Ответ:

 (1) графическое представление графа в виде точек, связанных дугами 

 (2) представление графа в виде объединения связных непересекающихся подграфов 

 (3) построение взаимнооднозначного соответствия между вершинами изоморфных графов 

 (4) представление графа в виде объединения полных графов 


Упражнение 15:
Номер 1
Единственные вершины нечетной степени в простом графе:

Ответ:

 (1) всегда связанные 

 (2) всегда не связанные 

 (3) могут быть как связанными, так и не связанными 


Номер 2
Укажите последовательность степеней вершин существующего графа, которая требует связности первой и второй вершины:

Ответ:

 (1) (1,1,1,1) 

 (2) (1,1,2,2) 

 (3) (1,2,3,4,5) 

 (4) (4,4,4,4) 


Номер 3
Максимальное количество ребер в простом графе с math вершинами и math компонентами связности равно:

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Упражнение 16:
Номер 1
Максимальное количество ребер в простом графе с 3 вершинами и 2 компонентами связности равно:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
Максимальное количество ребер в простом графе с 4 вершинами и 2 компонентами связности равно:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Максимальное количество ребер в простом графе с 5 вершинами и 2 компонентами связности равно:

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 17:
Номер 1
Укажите свойство простого графа с количеством вершин math и количеством ребер большим math:

Ответ:

 (1) полный 

 (2) связный 

 (3) имеющий петли или кратные ребра 

 (4) содержащий math компонент связности 


Номер 2
Укажите нижнюю границу количества ребер простого графа с math вершинами, превышение которой означает связность графа:

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Номер 3
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 4 вершинами:

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 18:
Номер 1
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 5 вершинами:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 2
Укажите максимальное количество ребер, которое может содержаться в простом несвязном графе с 3 вершинами:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Для простого графа с math вершинами укажите количества ребер, обеспечивающие связность графа:

Ответ:

 (1) math 

 (2) math 

 (3) math 


Упражнение 19:
Номер 1
Какой неориентированный граф по определению называется деревом:

Ответ:

 (1) связный граф, имеющий циклы 

 (2) связный граф, не имеющий циклов 

 (3) граф, все имеющиеся пути в котором простые 


Номер 2
Укажите верные утверждения:

Ответ:

 (1) в дереве любые две вершины связаны простым путем 

 (2) дерево не имеет петель и кратных ребер 

 (3) дерево не имеет кратных ребер, но может иметь петли 


Номер 3
Что из перечисленного есть термины теории графов:

Ответ:

 (1) корень дерева 

 (2) листья 

 (3) лес 


Упражнение 20:
Номер 1
Вершина дерева называется концевой вершиной, если:

Ответ:

 (1) степень данной вершины равна 0 

 (2) степень данной вершины равна 1 

 (3) данной вершине инцидентно концевое ребро 


Номер 2
Сколько ребер содержит дерево с math вершинами?

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Номер 3
Сколько ребер содержит дерево со 100 вершинами?

Ответ:

 (1) 100 

 (2) 10000 

 (3) 10 

 (4) 99 


Упражнение 21:
Номер 1
Количество деревьев, которое можно построить на math заданный вершинах, равно:

Ответ:

 (1) math 

 (2) math 

 (3) math 

 (4) math 


Номер 2
Количество деревьев, которое можно построить на 2 заданный вершинах, равно:

Ответ:

 (1)

 (2)

 (3)

 (4)


Номер 3
Количество деревьев, которое можно построить на 3 заданный вершинах, равно:

Ответ:

 (1)

 (2)

 (3)

 (4)


Упражнение 22:
Номер 1
Количество деревьев, которое можно построить на 4 заданных вершинах, равно:

Ответ:

 (1)

 (2)

 (3)

 (4) 16 


Номер 2
Количество деревьев, которое можно построить на 10 заданный вершинах, равно:

Ответ:

 (1) 100 

 (2) 10000 

 (3) 1000000 

 (4) 100000000 


Номер 3
Любое нетривиальное дерево содержит::

Ответ:

 (1) хотя бы одно концевую вершину 

 (2) хотя бы две концевых вершины и одно концевое ребро 

 (3) хотя бы три концевых вершины и два концевых ребра 




Главная / Алгоритмы и дискретные структуры / Дискретный анализ / Тест 12