База ответов ИНТУИТ

Графы и алгоритмы - ответы

Количество вопросов - 122

В графе с весовой функцией w строится каркас с помощью алгоритма Крускала. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?

В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее

В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?

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

Какие из следующих утверждений верны?

Пусть каждая из функций f_1 и f_2 является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?

Сколько имеется связных абстрактных графов с 4 вершинами?

В дереве имеется ровно три листа a,b,c, причем d(a,b) = 8, d(a,c) = 9, d(b,c) = 5. Сколько всего вершин в этом дереве?

В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?

В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?

Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?

Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?

Какие из следующих равенств выполняются для любых графов G1 и G2?

Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?

Какие из следующих графов являются двудольными?

Какие из следующих утверждений верны?

Сколько ребер нужно добавить к наибольшему паросочетанию графа K_{2,5} + C_9, чтобы получить наименьшее реберное покрытие этого графа?

Какое из следующих утверждений верно?

BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?

Дан граф G с множеством вершин V, \Phi - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара (V,\Phi ) является матроидом,?

Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).

Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?

Чему равно число вершинного покрытия графа P_3 \times P_4 ?

Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?

Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Какие из следующих утверждений верны для любого взвешенного графа?

Какие из следующих графов изоморфны графу\overline {C_5 }?

Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?

Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?

Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?

Граф G имеет 4 вершины, а в его матрице смежности 8 единиц. Граф H имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа G \circ H ?

Сколько имеется абстрактных графов с 4 вершинами радиуса 1?

Что происходит с радиусом графа при добавлении нового ребра?

Какие из следующих утверждений верны?

Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

Сколько имеется абстрактных двудольных графов с 4 вершинами?

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

В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

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

Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе G \cup H 12 ребер. Сколько ребер в графе G \oplus H ?

Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?

Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?

Какие из следующих утверждений справедливы для любого двусвязного графа?

Какие из следующих утверждений верны?

Чему равно кликовое число графа C9?

Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?

Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?

Сколько листьев будет в дереве путей, построенном для графа K4,4?

К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

Какое наименьшее число ребер нужно удалить из графа P_3 \times P_3 , чтобы превратить его в хордальный?

Чему равно хроматическое число графа C_3 \circ C_4 ?

Чему равны хроматические индексы графов K3,3 и C7 ?

В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?

В графе с весовой функцией w строится каркас с помощью алгоритма Прима. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?

Сколько различных наибольших паросочетаний имеется в графе K_5?

Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?

Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?

Пусть (E,\Phi ) - матроид и на множестве E задана весовая функция w с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества E упорядочиваются не по убыванию, а по возрастанию весов?

В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?

В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

Какие из следующих утверждений верны?

Что происходит с хроматическим числом графа при удалении ребра?

Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?

Чему равно число независимости графа Q3?

Сколько ребер имеет граф пересечений граней трехмерного куба?

В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?

Какие из следующих утверждений верны?

Сколько имеется абстрактных деревьев с 6 вершинами?

Как может измениться цикломатическое число при добавлении к графу нового ребра?

Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?

Сколько ребер нужно удалить из наименьшего реберного покрытия графа K_{4,6} + K_7 , чтобы получить наибольшее паросочетание этого графа?

Что происходит с диаметром графа при удалении ребра?

Сколько имеется абстрактных двусвязных графов с 4 вершинами?

Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?

В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?

Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?

В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?

Сколько имеется абстрактных графов с 4 вершинами диаметра 2?

Какие из следующих утверждений верны для любого графаG и любого его подграфаH?

Какие из следующих графов планарны?

Поиск в ширину применяется к графу P_3 \times P_3 . Какой будет высота BFS-дерева?

Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин

Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?

Какие из следующих утверждений верны?

Какие из следующих равенств выполняются для любых графов G1 и G2?

Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?

Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?

Пусть e_1 ,e_2 , \ldots ,e_m - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?

Для некоторого графа построено BFS-дерево с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?

Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?

Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?

В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?

Какие из следующих равенств выполняются для любых графов G1 и G2?

Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу C_{12}?

Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?

Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?

Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Сколько максимальных независимых множеств имеется у графа P5?

Какие из следующих равенств выполняются для любых графов G1 и G2?

Дано непустое конечное множество E и семейство его подмножеств \Phi . В каких из перечисленных ниже случаев пара (E,\Phi ) является матроидом?

В каких из следующих графов имеется гамильтонов цикл?

Сколько различных каркасов имеется у графа K_4 ?

Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?

Поиск в глубину применяется к графу K_2 \times O_4 . Какова будет высота DFS-дерева?

В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?

Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?

Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?

Какие из следующих утверждений верны?

Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?

Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?

Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

Что происходит с диаметром графа при удалении вершины?