Главная / Графы и алгоритмы

Графы и алгоритмы - ответы на тесты Интуит

Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.

Список вопросов:

# Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?
# Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
# Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
# Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
# Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
# Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
# Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?
# Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
# Сколько ребер имеет граф пересечений граней трехмерного куба?
# В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
# Граф имеет 4 вершины, а в его матрице смежности 8 единиц. Граф имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа ?
# Какие из следующих графов изоморфны графу?
# К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
# Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?
# Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?
# Какое наименьшее число ребер нужно удалить из графа , чтобы превратить его в хордальный?
# Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?
# Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
# Чему равно хроматическое число графа ?
# Что происходит с хроматическим числом графа при удалении ребра?
# Какие из следующих равенств выполняются для любых графов G1 и G2?
# Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
# Чему равны хроматические индексы графов K3,3 и C7 ?
# Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
# В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?
# В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
# В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?
# Пусть - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
# Какие из следующих утверждений верны для любого взвешенного графа?
# В графе с весовой функцией строится каркас с помощью алгоритма Прима. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
# В графе с весовой функцией строится каркас с помощью алгоритма Крускала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
# Сколько ребер нужно добавить к наибольшему паросочетанию графа , чтобы получить наименьшее реберное покрытие этого графа?
# Сколько ребер нужно удалить из наименьшего реберного покрытия графа , чтобы получить наибольшее паросочетание этого графа?
# Сколько различных наибольших паросочетаний имеется в графе ?
# Какие из следующих утверждений верны?
# Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
# Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
# Дано непустое конечное множество и семейство его подмножеств . В каких из перечисленных ниже случаев пара является матроидом?
# Дан граф с множеством ребер . Для каких из перечисленных ниже семейств подмножеств множества пара является матроидом для любого графа ?
# Дан граф с множеством вершин , - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара является матроидом,?
# Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
# Пусть - матроид и на множестве задана весовая функция с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества упорядочиваются не по убыванию, а по возрастанию весов?
# В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?
# В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
# В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
# Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
# Пусть и - ребра с наименьшими весами в некотором взвешенном графе, причем . Какие из следующих утверждений верны для любого графа и любой весовой функции?
# В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
# В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
# В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
# Пусть каждая из функций и является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?
# Сколько имеется связных абстрактных графов с 4 вершинами?
# Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
# Сколько имеется абстрактных графов с 4 вершинами радиуса 1?
# Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?
# Какие из следующих утверждений верны?
# Какие из следующих утверждений верны для любого графа и любого его подграфа?
# Что происходит с диаметром графа при удалении ребра?
# Что происходит с диаметром графа при удалении вершины?
# Что происходит с радиусом графа при добавлении нового ребра?
# Какие из следующих утверждений верны?
# Какое из следующих утверждений верно?
# Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?
# Сколько имеется абстрактных деревьев с 6 вершинами?
# Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?
# В дереве имеется ровно три листа , причем , , . Сколько всего вершин в этом дереве?
# Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?
# Сколько различных каркасов имеется у графа ?
# Сколько имеется абстрактных двудольных графов с 4 вершинами?
# Какие из следующих графов являются двудольными?
# Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу ?
# Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
# В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
# Какие из следующих графов планарны?
# Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
# Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?
# В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?
# В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее
# Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
# Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
# Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
# Поиск в ширину применяется к графу . Какой будет высота BFS-дерева?
# Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
# Для некоторого графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
# Для двудольного графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
# В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
# Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
# Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
# Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
# Поиск в глубину применяется к графу . Какова будет высота DFS-дерева?
# Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
# Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
# Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
# Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
# Какие из следующих утверждений верны?
# Какие из следующих утверждений верны?
# G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе 12 ребер. Сколько ребер в графе ?
# Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин
# Какие из следующих утверждений верны?
# Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?
# Как может измениться цикломатическое число при добавлении к графу нового ребра?
# Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?
# Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?
# Сколько имеется абстрактных двусвязных графов с 4 вершинами?
# Какие из следующих утверждений справедливы для любого двусвязного графа?
# Какие из следующих утверждений верны?
# Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?
# BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?
# Какие из следующих утверждений верны?
# Чему равно число независимости графа Q3?
# Чему равно кликовое число графа C9?
# Чему равно число вершинного покрытия графа ?
# Какие из следующих равенств выполняются для любых графов G1 и G2?
# Какие из следующих равенств выполняются для любых графов G1 и G2?
# Какие из следующих равенств выполняются для любых графов G1 и G2?
# Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?
# Сколько максимальных независимых множеств имеется у графа P5?
# Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?
# Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?
# Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?
# В каких из следующих графов имеется гамильтонов цикл?
# Сколько листьев будет в дереве путей, построенном для графа K4,4?