Теория графов - ответы на вопросы на СтудИзбе

Какие из утверждений ниже являются предикатами?

• 8=2^4
• X решает задачи быстрее, чем Y
• Василий решает задачи быстрее, чем Борис
• 2 - четное число
• c = 2^d

В группе из 25 студентов лингвистов 12 изучают греческий, 10 - латынь и 9 - санскрит. Каждые два языка изучает ровно три студента. Сколько студентов изучают все три языка?

В начале некоторой игры вы выбрали три одинаковые фигуры, теперь вы можете расставить их на поле 4x4. Сколько способов это сделать?

Пусть R={(1, r)}, Запишите обратное отношение. Ответ необходимо записать в виде множества пар, например, {(а,b)} или {(а,b),(а,b)} и т.п.

Найдите количество шестизначных чисел, в которых цифры невозрастают.

• Размещения
• Размещения с повторениями
• Сочетания
• Сочетания с повторениями

Какова арность соответствующего предложению предиката: "Эта погода совсем не нравится Алексею"

Согласно биному Ньютону чему будет равен коэффициент при x6 после раскрытия скобок в выражении (1+x)9?

• 80
• 84
• 65
• 12
• 49

Пусть А = { -1}, a B = {1}.
Записать отношение АхB.
Ответ необходимо записать в виде списка пар, например, {(1,2), (2,1)}.

Пусть А={2}, B={x}, C={*}
Пусть отношения R на A´B и S на B´C заданы в виде: R={(2, x}, S={(x, *)}
Запишите композицию S ° R .

Пусть А={1}, B={x}, C={*}
Пусть отношения R на A´B и S на B´C заданы в виде: R={(1, x}, S={(x, *)}
Запишите композицию S°R .
Ответ необходимо записать в виде множества пар, например, {(а,b)} или {(а,b),(а,b)} и т.п.

Пусть А = {2}, а B = {5}. Записать отношение А х B.

Неверно, что А и не-А.
Так представлен закон...
отделения
исключенного третьего
противоречия
поглощения.

Гамильтонов цикл проходит …

• вершины один раз
• ребра один раз

Гамильтонов цикл проходит …

• вершины один раз
• ребра один раз

Пусть R={(1, s), (3, s)},
Запишите обратное отношение.
Ответ необходимо записать в виде множества пар, например, {(а,b)} или {(а,b),(а,b)} и т.п.

Листьями дерева называются …

• вершины степени 1
• вершины степени 2
• точки на ветвях

Пусть А = {1}, a B = {4}.
Записать отношение А хB. Ответ в виде ( , )

Полное бинарное ориентированное дерево высоты h имеет …

• 2^h листьев
• 2^(h+1) - 1 вершин

Если графы G и G' гомеоморфны, то граф G имеет эйлеров цикл (собственный путь) тогда и только тогда, когда граф G' имеет …

• эйлеров цикл (собственный путь)
• гамильтонов путь
• эйлеров путь
• гамильтонов цикл.

Если графы G и G' – гомеоморфны, то у них …

• одинаковое количество вершин четной степени
• разное количество вершин нечетной степени
• разное количество вершин четной степени
• одинаковое количество вершин нечетной степени

В начале некоторой игры вы выбираете какими фигурами будете играть. Всего есть 5 видов фигур, вам нужно выбрать 3 фигуры (необязательно разных видов). Сколько различных стартовых наборов существует в этой игре?

Двудо́льный граф, или бигра́ф, — это граф, в котором:

• не существует ребра, соединяющего две вершины из одной и той же части;
• множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части.

Сколько существует четырехзначных чисел, у которых есть как четные, так и нечетные цифры?

Фрагмент кода:
Цикл по i от 1 до m:
Цикл по j от 1 до n:
Cij=Aij+Bij;
Конец цикла;
Конец цикла;
В фрагменте выше приведен алгоритм вычисления какой процедуры?

• нахождение топологической сортировки
• сумма элементов ряда
• сложение матриц
• вычисление полинома

Диаметром графа называется …

• наименьшее расстояние между двумя любыми его вершинами.
• наибольшее расстояние между двумя любыми его вершинами.

Функция f: A®B называется инъективной, или инъекцией, …

• если из f(a) = f(a' ) следует а=а' .
• если для каждого b из B существует некоторое а из А такое, что f(a) = b.
• если A = B и f : A -> B

Доказательство можно определить как последовательность утверждений, каждое из которых истинно в силу одной из следующих причин...(выберете нужные)

• по предположению
• по правилу выделения
• по аксиоме
• по ранее доказанной теореме
• по допущению

Корень дерева – это …

• вершина в самой нижней части каждого изображения
• точка внизу графа
• вершина в самой верхней части каждого изображения
• точка в верхней части графа

Под операцией удаления вершин из графа будем понимать операцию, заключающуюся …

• в удалении некоторой вершины вместе с инцидентными ей ребрами.
• в удалении некоторой вершины без инцидентных с ней ребер.

Число способов, которыми можно расставить n пар скобок в выражении a1, a2, a3, …, an, an+1, соответствует...

• числам Каталана
• числам Фибоначчи
• ничего из указанного
• функции Аккермана

Наличие петель допускается …

• для любых графов.
• в случае ориентированного графа.

Простой цикл, который проходит через каждую вершину графа G – это …

• Гамильтонов цикл
• Эйлеров цикл

Верно ли, что для сочетаний не важен порядок в выборке?

• Верно
• Неверно

Граф для кенигсбергских мостов имеет …

• четыре вершины с нечетными степенями
• четыре вершины с четными степенями
• три вершины с четными степенями
• три вершины с нечетными степенями

Сколько существует целых чисел от 1 до 33000, которые не делятся ни на 3, ни на 5, но делятся на 11

В начале некоторой игры вы выбираете три фигуры из пяти (необязательно различные) и назначаете им цену (1, 2 и 3, все разные ). Сколько различных назначений цен может получиться в этой игре?

Функция f называется перестановкой множества А, …

• если из f(a) = f(a' ) следует а=а'
• если для каждого b из B существует некоторое а из А такое, что f(a) = b.
• если A = B и f : A -> B

Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда …

• каждая вершина имеет нечетную степень.
• он связный.
• каждая вершина имеет четную степень

Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая вершина имеет …

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

Если эйлеров путь не является эйлеровым циклом, такой путь называют …

• собственным гамильтоновым путем
• собственным путем
• собственным эйлеровым путем

Сохранение потока сети – это означает, что …

• Поток, входящий в вершину, был равен потоку, выходящему из вершины, за исключением вершин a и z
• Входящий поток в источнике равен выходящему потоку в стоке

Верно ли, что для вычисления можно использовать использовать рекурсивный алгоритм?

• Верно
• Неверно

Если два связных графа гомеоморфны, то они …

• оба непланарны
• оба планарны

Эйлеров цикл - это ...

• цикл, который включает все ребра и вершины графа G
• цикл, который включает все вершины графа G
• цикл, который включает все вершины графа G

Высотой дерева – это …

• самая длинная часть дерева
• длина самого длинного пути от корня дерева до листа
• длина от корня дерева до листа

Высотой дерева – это …

• самая длинная часть дерева
• длина самого длинного пути от корня дерева до листа
• длина от корня дерева до листа

В группе из 50 ребят некоторые знают все буквы, кроме "р", которую просто пропускают при письме, а остальные знают все буквы, кроме "к", которую тоже пропускают. Однажды учитель попросил 10 учеников написать слово "кот", 18 других учеников – слово "рот", а остальных – слово "крот". При этом слова "кот" и "рот" оказались написанными по 15 раз. Сколько ребят написали своё слово верно?

Правильное умозаключение истинно всякий раз, когда...

• истинны его гипотезы и заключение
• истинно его заключение
• истинны его гипотезы

Графы G и G' называются …, если существует граф G'' такой, что оба графа, G и G' , являются производными от графа G'' .

• гомоморфными
• гомеоморфными
• изоморфными

Найти обратную функцию для y = 6x + 3

Пусть G=(V, E) - граф. Эйлеров цикл включает :

• все ребра графа G
• все вершины графа G

В начале некоторой игры вы выбрали три разные фигуры, теперь вы можете расставить их на поле 4x4. Сколько способов это сделать?

Пусть G – граф (ориентированный граф).
Пусть В – матрица, строки которой обозначены вершинами графа и столбцы обозначены теми же вершинами в том же самом порядке. Элемент i-ой строки и j-го столбца матрицы В, обозначаемый Вij , равен 1, если имеется ребро (ориентированное ребро) из i-ой вершины в j-ю вершину, и равен 0 в противоположном случае.

• Матрица В называется матрицей смежности графа G.
• Матрица В называется матрицей инцидентности графа G.

Ребро e графа G является разрезающим ребром графа G тогда и только тогда, когда

• оно не входит в цикл графа G
• оно входит в цикл графа G

Свойство деревьев: (отметить все, если свойств несколько)

• Для любых двух вершин a и b дерева Т существует два пути из a и b
• Для любых двух вершин a и b дерева Т существует единственный путь из a и b
• Если для любых двух вершин графа G существует единственный путь из вершины a в вершину b, тогда G – дерево
• Если для любых двух вершин графа G существует два пути из вершины a в вершину b, тогда G – дерево

Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда …

• он связный и степень входа каждой вершины равна ее степени выхода
• он несвязный и степень входа каждой вершины больше ее степени выхода
• он связный и степень входа каждой вершины меньше ее степени выхода
• он несвязный и степень входа каждой вершины равна ее степени выхода

Бинарным дерево – это …

• дерево, если наибольшая из степеней выхода для вершин дерева равна m = 3
• дерево, если наибольшая из степеней выхода для вершин дерева равна m = 1
• дерево, если наибольшая из степеней выхода для вершин дерева равна m = 2
• дерево, если наибольшая из степеней выхода для вершин дерева равна m

Отношение R на А есть отношение частичного порядка, если …

• оно антирефлексивно, симметрично и транзитивно.
• оно рефлексивно, симметрично и антитранзитивно.
• оно рефлексивно, симметрично и транзитивно.
• оно рефлексивно, антисимметрично и транзитивно.

Если полное m-арное ориентированное дерево имеет n вершин, i внутренних вершин и l листьев, то…

• l = (m + 1) i -1
• l = m i +1
• l = (m – 1) i +1

^​Граф для кенигсбергских мостов в задаче Л. Эйлера …
не является эйлеровым.
является эйлеровым.

Число неизоморфных корневых бинарных деревьев с n вершинами равно …

• числу Каталана Cn
• числу экспоненте
• числу Фибоначчи

Пусть G=(V, E) – ориентированный граф. Ориентированный цикл, который включает все ребра и вершины графа G, называется …

• эйлеровым циклом
• гамильтоновым циклом
• циклом

Какова арность соответствующего предложению предиката: "Светлана Ивановна и Алексей Петрович – родители Андрея"

Если первое влечет второе, то отрицание второго влечет отрицание первого. Этот закон называется законом....

Какова мощность множества точек отрезка [0,1]?

• Бесконечность
• 1
• 0

Область определения R есть …

• множество всех первых координат упорядоченных пар из R.
• множество всех вторых координат упорядоченных пар из R.

Сколько существует целых чисел от 1 до 1000000, которые не являются ни полным квадратом, ни полным кубом, ни четвёртой степенью?

Множество значений R есть …

• множество всех первых координат упорядоченных пар из множество всех первых координат упорядоченных пар из R.
• множество всех вторых координат упорядоченных пар из R.

Функция f называется сюръективной функцией, или сюръекцией, …

• если A = B и f : A -> B
• если для каждого b из B существует некоторое а из А такое, что f(a) = b.
• если из f(a) = f(a' ) следует а=а' .

Сопоставьте название закона и его суть

1. Если А. то В; неверно В Неверно А
2. Если А, то В; А В
3. если А, то А
4. Если А, то В. Если А, то С. Неверно В или неверно С. Неверно А.
5. Если А, то С. Если В, то С. А или В. С

1. Модус поненс
2. Простая деструктивная дилемма
3. Закон тождества
4. Простая конструктивная дилемма
5. Модус толленс

Найдите число двоичных векторов длины семь и веса 3.

• Размещения
• Размещения с повторениями
• Сочетания
• Сочетания с повторениями

Какова арность соответствующего предложению предиката: "Эта прямая пересекает окружность"

Граф имеет эйлеров цикл, поскольку степень каждой его вершины ...

• четная
• нечетная

Сколько существует трехзначных чисел, у которых цифры ненулевые и различные?

Расстояние между двумя вершинами графа называется …

• длина самого короткого пути между этими двумя вершинами.
• длина самого длинного пути между этими двумя вершинами.

Наличие петель у сети …

• обязательно
• недопустимо
• возможно

Если у дерева Т имеется е ребер и v вершин, тогда v - e = …

• 1
• 2
• 3
• 0

Орграф G состоит …

• из множества V вершин и отношения E на V, называемого множеством ребер, если понятно, что граф ориентирован.
• из множества V вершин и ребер