Графы и алгоритмы
700,00 руб.
В течение часа!
Экзамен "Графы и алгоритмы" для пользователей и системных администраторов.
Форма сдачи теста: Экстерн
Количество вопросов: 30
Проходной балл: 90% и выше
Срок действия сертификата: неограничен
Сертификат появляется в профиле ресурса INTUIT, и Вы можете заказать его бумажную версию на сайте INTUIT.
Количество вопросов: 30
Проходной балл: 90% и выше
Срок действия сертификата: неограничен
Сертификат появляется в профиле ресурса INTUIT, и Вы можете заказать его бумажную версию на сайте INTUIT.
10564 шт.
Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?
Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
Какие из следующих графов изоморфны графу ?
Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
Граф имеет 4 вершины, а в его матрице смежности 8 единиц. Граф имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа ?
Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?
Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
Сколько ребер имеет граф пересечений граней трехмерного куба?
Что происходит с диаметром графа при удалении вершины?
Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
Сколько имеется связных абстрактных графов с 4 вершинами?
Какие из следующих утверждений верны?
Какие из следующих утверждений верны?
Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?
Какие из следующих утверждений верны?
Что происходит с радиусом графа при добавлении нового ребра?
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу ?
Сколько различных каркасов имеется у графа ?
Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?
Какие из следующих графов планарны?
Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?
Что происходит с диаметром графа при удалении ребра?
увеличивается или остается прежним.
Сколько имеется абстрактных графов с 4 вершинами радиуса 1?
Какие из следующих утверждений верны для любого графа и любого его подграфа ?
Если - остовный подграф, то
Сколько имеется абстрактных деревьев с 6 вершинами?
Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого
В дереве имеется ровно три листа , причем . Сколько всего вершин в этом дереве?
В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?
Какие из следующих графов являются двудольными?
В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
Для некоторого графа построено BFS-дерево с корнем a. Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?
Сколько имеется абстрактных двудольных графов с 4 вершинами?
Поиск в ширину применяется к графу . Какой будет высота BFS-дерева?
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
Какие из следующих утверждений верны?
Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее
новую вершину с открытой?
Для двудольного графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?
Какие из следующих утверждений справедливы для любого двусвязного графа?
Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?
Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
Поиск в глубину применяется к графу . Какова будет высота DFS-дерева?
Какие из следующих утверждений верны?
Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?
Какие из следующих утверждений верны?
Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?
Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин
Какие из следующих утверждений верны?
Сколько имеется абстрактных двусвязных графов с 4 вершинами?
Как может изм&#x#x435;ниться цикломатическое число при добавлении к графу нового ребра?
G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе 12 ребер. Сколько ребер в графе ?
Какие из следующих утверждений верны?
объединение двух квазициклов, не имеющих общих ребер - всегда квазицикл
если пересечение двух квазициклов - квазицикл, то их объединение - тоже квазицикл
Сколько максимальных независимых множеств имеется у графа P5?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Что получится, если к графу применить каждый из двух описанных в лекции 9 эвристических алгоритмов для задачи о независимом множестве: 1) удаление вершины наибольшей степени на каждом шаге; 2) удаление окрестности вершины наименьшей степени на каждом шаге?
Чему равно кликовое число графа C9?
Чему равно число независимости графа Q3?
Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?
Сколько листьев будет в дереве путей, построенном для графа K4,4?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?
граф K3,5 невозможно добавлением ребер превратить в граф, имеющий эйлеров цикл.
В каких из следующих графов имеется гамильтонов цикл?
K3,3
Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
каждая компонента связности - цикл четной длины или цепь.
Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Какое наименьшее число ребер нужно удалить из графа , чтобы превратить его в хордальный?
Чему равно хроматическое число графа C_3 \circ C_4 ?
Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Чему равно число вершинного покрытия графа ?
Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?
Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?
Что происходит с хроматическим числом графа при удалении ребра?
Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
Сколько ребер нужно добавить к наибольшему паросочетанию графа , чтобы получить наименьшее реберное покрытие этого графа?
Какие из следующих утверждений верны?
К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
Чему равны хроматические индексы графов K3,3 и C7 ?
Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?
В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?
В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?
Сколько ребер нужно удалить из наименьшего реберного покрытия графа , чтобы получить наибольшее паросочетание этого графа?
В графе с весовой функцией строится каркас с помощью алгоритма Прима. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
Пусть - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
Какие из следующих утверждений верны для любого взвешенного графа?
В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Сколько различны&##x445; наибольших паросочетаний имеется в графе ?
В графе с весовой функцией строится каркас с помощью алгоритма Краскала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Дано непустое конечное множество и семейство его подмножеств . В каких из перечисленных ниже случаев пара является матроидом?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова на #x438;большая величина потока от вершины 1 к вершине 6?
Дан граф с множеством ребер E. Для каких из перечисленных ниже семейств подмножеств множества пара является матроидом для любого графа ?
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
Дан граф с множеством вершин , - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара является матроидом,?
Пусть и - ребра с наименьшими весами в некотором взвешенном графе, причем . Какие из следующих утверждений верны для любого графа и любой весовой функции?
В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Пусть - матроид и на множестве задана весовая функция с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества упорядочиваются не по убыванию, а по возрастанию весов?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
Пусть каждая из функций и является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?
Как может измениться цикломатическое число при добавлении к графу нового ребра?
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?
Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
Какие из следующих графов изоморфны графу ?
Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
Граф имеет 4 вершины, а в его матрице смежности 8 единиц. Граф имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа ?
Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?
Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
Сколько ребер имеет граф пересечений граней трехмерного куба?
Что происходит с диаметром графа при удалении вершины?
Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
Сколько имеется связных абстрактных графов с 4 вершинами?
Какие из следующих утверждений верны?
Какие из следующих утверждений верны?
Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?
Какие из следующих утверждений верны?
Что происходит с радиусом графа при добавлении нового ребра?
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу ?
Сколько различных каркасов имеется у графа ?
Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?
Какие из следующих графов планарны?
Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?
Что происходит с диаметром графа при удалении ребра?
увеличивается или остается прежним.
Сколько имеется абстрактных графов с 4 вершинами радиуса 1?
Какие из следующих утверждений верны для любого графа и любого его подграфа ?
Если - остовный подграф, то
Сколько имеется абстрактных деревьев с 6 вершинами?
Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого
В дереве имеется ровно три листа , причем . Сколько всего вершин в этом дереве?
В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?
Какие из следующих графов являются двудольными?
В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
Для некоторого графа построено BFS-дерево с корнем a. Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?
Сколько имеется абстрактных двудольных графов с 4 вершинами?
Поиск в ширину применяется к графу . Какой будет высота BFS-дерева?
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
Какие из следующих утверждений верны?
Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее
новую вершину с открытой?
Для двудольного графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?
Какие из следующих утверждений справедливы для любого двусвязного графа?
Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?
Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
Поиск в глубину применяется к графу . Какова будет высота DFS-дерева?
Какие из следующих утверждений верны?
Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?
Какие из следующих утверждений верны?
Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?
Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин
Какие из следующих утверждений верны?
Сколько имеется абстрактных двусвязных графов с 4 вершинами?
Как может изм&#x#x435;ниться цикломатическое число при добавлении к графу нового ребра?
G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе 12 ребер. Сколько ребер в графе ?
Какие из следующих утверждений верны?
объединение двух квазициклов, не имеющих общих ребер - всегда квазицикл
если пересечение двух квазициклов - квазицикл, то их объединение - тоже квазицикл
Сколько максимальных независимых множеств имеется у графа P5?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Что получится, если к графу применить каждый из двух описанных в лекции 9 эвристических алгоритмов для задачи о независимом множестве: 1) удаление вершины наибольшей степени на каждом шаге; 2) удаление окрестности вершины наименьшей степени на каждом шаге?
Чему равно кликовое число графа C9?
Чему равно число независимости графа Q3?
Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?
Сколько листьев будет в дереве путей, построенном для графа K4,4?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?
граф K3,5 невозможно добавлением ребер превратить в граф, имеющий эйлеров цикл.
В каких из следующих графов имеется гамильтонов цикл?
K3,3
Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
каждая компонента связности - цикл четной длины или цепь.
Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Какое наименьшее число ребер нужно удалить из графа , чтобы превратить его в хордальный?
Чему равно хроматическое число графа C_3 \circ C_4 ?
Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?
Какие из следующих равенств выполняются для любых графов G1 и G2?
Чему равно число вершинного покрытия графа ?
Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?
Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?
Что происходит с хроматическим числом графа при удалении ребра?
Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
Сколько ребер нужно добавить к наибольшему паросочетанию графа , чтобы получить наименьшее реберное покрытие этого графа?
Какие из следующих утверждений верны?
К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
Чему равны хроматические индексы графов K3,3 и C7 ?
Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?
В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?
В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?
Сколько ребер нужно удалить из наименьшего реберного покрытия графа , чтобы получить наибольшее паросочетание этого графа?
В графе с весовой функцией строится каркас с помощью алгоритма Прима. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
Пусть - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
Какие из следующих утверждений верны для любого взвешенного графа?
В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Сколько различны&##x445; наибольших паросочетаний имеется в графе ?
В графе с весовой функцией строится каркас с помощью алгоритма Краскала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Дано непустое конечное множество и семейство его подмножеств . В каких из перечисленных ниже случаев пара является матроидом?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова на #x438;большая величина потока от вершины 1 к вершине 6?
Дан граф с множеством ребер E. Для каких из перечисленных ниже семейств подмножеств множества пара является матроидом для любого графа ?
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
Дан граф с множеством вершин , - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара является матроидом,?
Пусть и - ребра с наименьшими весами в некотором взвешенном графе, причем . Какие из следующих утверждений верны для любого графа и любой весовой функции?
В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
Пусть - матроид и на множестве задана весовая функция с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества упорядочиваются не по убыванию, а по возрастанию весов?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
Пусть каждая из функций и является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?
Как может измениться цикломатическое число при добавлении к графу нового ребра?
Вы можете обратится к нам напрямую, через:
По Skype: molodoyberkut
По Telegram: @MolodoyBerkut
По ICQ: 657089516
Или через форму обратной связи на нашем сайте
По Skype: molodoyberkut По Telegram: @MolodoyBerkut По ICQ: 657089516Или через форму обратной связи на нашем сайте
Пока сочиняется...
Экзамен "Графы и алгоритмы" для пользователей и системных администраторов.
