Главная / Алгоритмы и дискретные структуры / Графы и алгоритмы

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

Правильные ответы выделены зелёным цветом.
Все ответы: Курс посвящен алгоритмам на графах. Приводятся базовые понятия и факты из теории графов и излагаются некоторые алгоритмы для решения задач на графах.
Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?
(1) 8
(2) 16
(3) 27
(4) 64
К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?
(1) 2
(2) 3
(3) 4
(4) 5
В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?
(1) 14
(2) 15
(3) 16
(4) 17
Дано непустое конечное множество math и семейство его подмножеств math . В каких из перечисленных ниже случаев пара math является матроидом?
(1) math состоит из всех непустых подмножеств множества math
(2) math состоит из всех подмножеств множества math
(3) math
(4) math состоит из всех подмножеств мощности не более k(k задано)
Сколько имеется связных абстрактных графов с 4 вершинами?
(1) 5
(2) 6
(3) 7
(4) 8
Сколько имеется абстрактных деревьев с 6 вершинами?
(1) 4
(2) 5
(3) 6
(4) 7
В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее
(1) новую вершину с открытой?
(2) открытую вершину с закрытой?
(3) новую вершину с закрытой?
(4) две открытые вершины?
Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе math 12 ребер. Сколько ребер в графе math ?
(1) 5
(2) 7
(3) 12
(4) 17
Чему равно число независимости графа Q3?
(1) 3
(2) 4
(3) 5
(4) 6
Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?
(1) 3
(2) 4
(3) 5
(4) 6
Какое наименьшее число ребер нужно удалить из графа math, чтобы превратить его в хордальный?
(1) 2
(2) 3
(3) 4
(4) 5
Пусть math - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?
(1) существует оптимальный каркас, содержащий ребро math
(2) существует оптимальный каркас, содержащий оба ребра math
(3) существует оптимальный каркас, содержащий все три ребра math
(4) если ребра math не образуют цикла, то существует оптимальный каркас, содержащий все эти ребра
Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).
(1) при любой весовой функции будет найдено независимое множество матроида, имеющее наибольший вес
(2) может быть найдено независимое множество не наибольшего веса
(3) результатом работы алгоритма может быть множество, не являющееся независимым
(4) при любой весовой функции будет найдена база матроида, имеющая наибольший вес
Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?
(1) 2
(2) 3
(3) 4
(4) 5
Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?
(1) 8
(2) 15
(3) 16
(4) 31
Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
Поиск в глубину применяется к графу math. Какова будет высота DFS-дерева?
(1) 2
(2) 4
(3) 2 или 4
(4) 2, 3 или 4
Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?
(1) каждое ребро каркаса принадлежит точно одному фундаментальному циклу
(2) каждое ребро каркаса принадлежит хотя бы одному фундаментальному циклу
(3) каждое ребро каркаса, не являющееся перешейком, принадлежит хотя бы одному фундаментальному циклу
(4) каждое ребро графа, не принадлежащее каркасу, принадлежит точно одному фундаментальному циклу
Какие из следующих равенств выполняются для любых графов G1 и G2?
(1) math
(2) math
(3) math
(4) math
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?
(1) 0
(2) 1
(3) 2
(4) 3
Чему равно хроматическое число графа math?
(1) 2
(2) 3
(3) 4
(4) 5
В графе с весовой функцией math строится каркас с помощью алгоритма Крускала. Пусть math - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого math?
(1) math
(2) ребро math может не иметь общих вершин ни с одним из ребер math
(3) ребро math может иметь общую вершину с несколькими из ребер math
(4) ребро math имеет общую вершину ровно с одним из ребер math
В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?
(1) 1
(2) 2
(3) 3
(4) 4
Что происходит с диаметром графа при удалении ребра?
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним.
(4) может увеличиться, уменьшиться или остаться прежним
Какие из следующих графов являются двудольными?
(1) math
(2) math
(3) math
(4) math
Для некоторого графа построено BFS-дерево с корнем math. Ребро графа math дереву не принадлежит. Какие из следующих соотношений могут выполняться (math обозначает расстояние между вершинами в графе)?
(1) math
(2) math
(3) math
(4) math
Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
(1) math
(2) math
(3) math
(4) math
Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?
(1) 45
(2) 56
(3) 60
(4) 90
Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?
(1) 6
(2) 9
(3) 18
(4) 27
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
(1) 7
(2) 14
(3) 18
(4) 21
Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?
(1) 3
(2) 4
(3) 5
(4) 6
Сколько ребер нужно добавить к наибольшему паросочетанию графа math, чтобы получить наименьшее реберное покрытие этого графа?
(1) 2
(2) 3
(3) 4
(4) 5
Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?
(1) math
(2) math
(3) math
(4) math
Какие из следующих утверждений верны?
(1) любое ребро, соединяющее два шарнира, является перешейком
(2) если два перешейка имеют общую вершину, то эта вершина - шарнир.
(3) любая вершина, инцидентная перешейку, является шарниром
(4) любая вершина, инцидентная перешейку и имеющая степень больше 1, является шарниром.
В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?
(1) 3
(2) 4
(3) 5
(4) такого графа не существует
Сколько имеется абстрактных двусвязных графов с 4 вершинами?
(1) 2
(2) 3
(3) 4
(4) 5
Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?
(1) 2
(2) 4
(3) 6
(4) 8
Какие из следующих утверждений верны?
(1) два чередующихся пути могут иметь две общих вершины.
(2) два чередующихся пути могут иметь три общих вершины
(3) если в графе относительно некоторого паросочетания имеются два увеличивающих пути, то существует паросочетание, в котором на два ребра больше
(4) если в графе относительно некоторого паросочетания имеются два непересекающихся увеличивающих пути, то существует паросочетание, в котором на два ребра больше
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
(1) 4
(2) 5
(3) 6
(4) 7
Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?
(1) 3
(2) 4
(3) 5
(4) 6
Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?
(1) 2
(2) 3
(3) 4
(4) 5
В каких из следующих графов имеется гамильтонов цикл?
(1) K3,3
(2) K3,4
(3) math
(4) math
Пусть каждая из функций math и math является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?
(1) math
(2) math
(3) math
(4) math для каждого ребра math
Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?
(1) 8
(2) 16
(3) 27
(4) 64
Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?
(1) удаление ребра
(2) добавление нового ребра
(3) удаление вершины
(4) добавление новой вершины и ребер, соединяющих ее со всеми "старыми" вершинами
В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
(1) 10
(2) 11
(3) 12
(4) 13
Дан граф math с множеством ребер math. Для каких из перечисленных ниже семейств math подмножеств множества math пара math является матроидом для любого графа math?
(1) mathсостоит из всех множеств ребер остовных подграфов графа math
(2) mathсостоит из всех множеств ребер остовных лесов графа math
(3) mathсостоит из всех паросочетаний графа math
(4) mathсостоит из всех реберных покрытий графа math
Сколько имеется абстрактных графов с 4 вершинами диаметра 2?
(1) 2
(2) 3
(3) 4
(4) 5
Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?
(1) 10
(2) 11
(3) 12
(4) 13
Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин
(1) math
(2) math
(3) math
(4) math
Чему равно кликовое число графа C9?
(1) 2
(2) 3
(3) 4
(4) 5
Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
(1) 3
(2) 4
(3) 5
(4) 6
Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?
(1) 6
(2) 7
(3) 8
(4) 9
Какие из следующих утверждений верны для любого взвешенного графа?
(1) если в графе имеется единственное ребро наибольшего веса, то оно принадлежит каждому оптимальному каркасу
(2) если в графе имеются точно два ребра наибольшего веса, то они оба принадлежат каждому оптимальному каркасу
(3) если в графе имеются точно три ребра наибольшего веса, то все они принадлежат каждому оптимальному каркасу
(4) если в графе имеются точно три ребра наибольшего веса и они не образуют цикла, то все они принадлежат каждому оптимальному каркасу
Пусть math - матроид и на множестве math задана весовая функция math с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества math упорядочиваются не по убыванию, а по возрастанию весов?
(1) при любой функции math будет найдено независимое множество матроида, имеющее наименьший вес
(2) результатом работы алгоритма может быть множество, не принадлежащее math
(3) если все веса отрицательны, то будет найдено независимое множество наименьшего веса
(4) при любой функции math будет найдена база матроида, имеющая наименьший вес
Какие из следующих утверждений верны?
(1) граф, дополнительный к связному, всегда связен
(2) граф, дополнительный к связному, всегда несвязен
(3) граф, дополнительный к несвязному, всегда связен
(4) граф, дополнительный к несвязному, всегда несвязен
Сколько различных каркасов имеется у графа math?
(1) 4
(2) 8
(3) 12
(4) 16
Поиск в ширину применяется к графу math. Какой будет высота BFS-дерева?
(1) 2
(2) 4
(3) 2 или 4
(4) 2, 3 или 4
Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
(1) всегда math
(2) h может быть меньше, чем радиус графа
(3) h может быть больше, чем диаметр графа.
(4) h не может быть меньше, чем эксцентриситет стартовой вершины.
Как может измениться цикломатическое число при добавлении к графу нового ребра?
(1) обязательно увеличивается
(2) увеличивается или не изменяется
(3) может увеличиться, уменьшиться или остаться прежним
(4) если граф связен, то обязательно увеличивается
Какие из следующих равенств выполняются для любых графов G1 и G2?
(1) math
(2) math
(3) math
(4) math
Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?
(1) 0
(2) 1
(3) 2
(4) 3
Что происходит с хроматическим числом графа при удалении ребра?
(1) увеличивается
(2) уменьшается
(3) уменьшается или не изменяется
(4) может увеличиться, уменьшиться или остаться прежним
В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?
(1) 10
(2) 13
(3) 16
(4) 19
Что происходит с диаметром графа при удалении вершины?
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним
(4) может увеличиться, уменьшиться или остаться прежним.
Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу math?
(1) 1
(2) 2
(3) 3
(4) 4
Для двудольного графа построено BFS-дерево с корнем math . Ребро графа math дереву не принадлежит. Какие из следующих соотношений могут выполняться (math обозначает расстояние между вершинами в графе)?
(1) math
(2) math
(3) math
(4) math
Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?
(1) если вершина x не является листом DFS-дерева, то у нее имеется такой сын y, что math
(2) если math то вершина x - предок вершины y в DFS-дереве
(3) если вершина x - предок вершины в DFS-дереве, то math
(4) если math и вершины x,y смежны в графе, то вершина x - предок вершины y в DFS-дереве
Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?
(1) 4
(2) 5
(3) 6
(4) 8
Граф math имеет 4 вершины, а в его матрице смежности 8 единиц. Граф math имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа math ?
(1) 20
(2) 40
(3) 60
(4) 80
Чему равны хроматические индексы графов K3,3 и C7 ?
(1) 3 и 2
(2) 3 и 3
(3) 4 и 2
(4) 4 и 3
Сколько ребер нужно удалить из наименьшего реберного покрытия графа math , чтобы получить наибольшее паросочетание этого графа?
(1) 2
(2) 3
(3) 4
(4) 5
Пусть math и math - ребра с наименьшими весами в некотором взвешенном графе, причем math. Какие из следующих утверждений верны для любого графа и любой весовой функции?
(1) существует геодезическое дерево, содержащее ребро math
(2) каждое геодезическое дерево содержит ребро math
(3) существует геодезическое дерево, содержащее оба ребра math
(4) если ребра math и math не имеют общей вершины, то существует геодезическое дерево, содержащее оба ребра math
Какое из следующих утверждений верно?
(1) простой цикл не может проходить через перешеек.
(2) замкнутый маршрут не может проходить через перешеек
(3) замкнутый маршрут не может проходить через шарнир
Какие из следующих графов планарны?
(1) math
(2) math
(3) math
(4) math
Какие из следующих утверждений справедливы для любого двусвязного графа?
(1) через любые две вершины проходит простой цикл
(2) через любые два ребра проходит простой цикл
(3) через любые три вершины проходит простой цикл
(4) через любые три вершины, среди которых имеется хотя бы одна пара смежных, проходит простой цикл
Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?
(1) 4
(2) 6
(3) 8
(4) граф K3,5 невозможно добавлением ребер превратить в граф, имеющий эйлеров цикл.
Для двудольного графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны?
(1) если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания
(2) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания
(3) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a
(4) любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро math, math, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
(1) 5
(2) 6
(3) 7
(4) 8
В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?
(1) 10
(2) 11
(3) 12
(4) такого графа не существует
BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?
(1) 2
(2) 3
(3) 4
(4) 5
Сколько листьев будет в дереве путей, построенном для графа K4,4?
(1) 16
(2) 24
(3) 48
(4) 144
Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?
(1) 2
(2) 3
(3) 4
(4) 5
Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?
(1) 2
(2) 3
(3) 4
(4) 5
В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?
(1) выбранные ребра образуют дерево
(2) выбранные ребра образуют лес
(3) некоторые из выбранных ребер могут образовать цикл
(4) если веса всех ребер графа различны, то выбранные ребра образуют лес
Дан граф math с множеством вершин math, math - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара math является матроидом,?
(1) для любого графа math
(2) для любого двудольного графа math
(3) для полного графа math
(4) для любого графа math, в котором каждая компонента компонента связности является полным графом
Сколько имеется абстрактных графов с 4 вершинами радиуса 1?
(1) 3
(2) 4
(3) 5
(4) 6
В дереве имеется ровно три листа math, причем math, math, math. Сколько всего вершин в этом дереве?
(1) 10
(2) 11
(3) 12
(4) такого дерева не существует
Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?
(1) math
(2) math
(3) math
(4) math
Какие из следующих утверждений верны?
(1) пересечение двух квазициклов - всегда квазицикл
(2) граф, дополнительный к квазициклу - всегда квазицикл
(3) объединение двух квазициклов, не имеющих общих ребер - всегда квазицикл
(4) если пересечение двух квазициклов - квазицикл, то их объединение - тоже квазицикл
Чему равно число вершинного покрытия графа math?
(1) 3
(2) 4
(3) 5
(4) 6
Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
(1) 0
(2) 1
(3) 2
(4) 3
Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?
(1) math
(2) math
(3) math
(4) math
В графе с весовой функцией math строится каркас с помощью алгоритма Прима. Пусть math - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого math?
(1) math
(2) ребро math может не иметь общих вершин ни с одним из ребер math
(3) ребро math может иметь общую вершину с несколькими из ребер math
(4) ребро math имеет общую вершину ровно с одним из ребер math
Какие из следующих утверждений верны для любого графаmath и любого его подграфаmath?
(1) math
(2) math
(3) еслиmath - порожденный подграф, то math
(4) еслиmath - остовный подграф, то math
Сколько имеется абстрактных двудольных графов с 4 вершинами?
(1) 6
(2) 7
(3) 8
(4) 9
Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?
(1) можно выбрать стартовую вершину так, что будет math
(2) h может быть больше, чем диаметр графа.
(3) можно выбрать стартовую вершину так, что будет math
(4) всегда math
Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?
(1) math
(2) math
(3) math
(4) math
Какие из следующих равенств выполняются для любых графов G1 и G2?
(1) math
(2) math
(3) math
(4) math
Сколько ребер имеет граф пересечений граней трехмерного куба?
(1) 6
(2) 8
(3) 12
(4) 24
Какие из следующих равенств выполняются для любых графов G1 и G2?
(1) math
(2) math
(3) math
(4) math
В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?
(1) 1
(2) 2
(3) 3
(4) 4
Что происходит с радиусом графа при добавлении нового ребра?
(1) увеличивается
(2) уменьшается или остается прежним
(3) увеличивается или остается прежним
(4) может увеличиться, уменьшиться или остаться прежним
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился двудольный граф?
(1) 4
(2) 5
(3) 6
(4) 7
В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?
(1) x - корень дерева
(2) x и y находятся в дереве на одинаковом расстоянии от корня.
(3) x и y - любые вершины.
(4) вершина x является предком вершины y в BFS-дереве.
Какие из следующих утверждений верны?
(1) лист DFS-дерева не может быть шарниром графа.
(2) если (x,y)- обратное ребро, то ни одна отличная от x и y вершина пути, соединяющего x и y в DFS-дереве, не является шарниром
(3) если вершина x является сыном вершины y в DFS-дереве и обе эти вершины - шарниры графа, то ребро (x,y) - перешеек
(4) если (x,y) - обратное ребро, то ни одно ребро пути, соединяющего x и y в DFS-дереве, не является перешейком
Сколько максимальных независимых множеств имеется у графа P5?
(1) 1
(2) 2
(3) 3
(4) 4
Какие из следующих графов изоморфны графуmath?
(1) math
(2) math
(3) math
(4) math
Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?
(1) степени вершин не превосходят 2
(2) нет циклов нечетной длины
(3) каждая компонента связности - цепь
(4) каждая компонента связности - цикл четной длины или цепь.
Сколько различных наибольших паросочетаний имеется в графе math?
(1) 5
(2) 10
(3) 15
(4) 20
Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?
(1) 1
(2) 2
(3) 3
(4) 4
Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?
(1) 2
(2) 3
(3) 4
(4) 5
Какие из следующих утверждений верны?
(1) если ребро math циклически связано с ребром math, а ребро math циклически связано с ребром math, то ребра math и math циклически связаны
(2) если вершина math циклически связана с вершиной math, а вершина math циклически связана с вершиной math, то вершины math и math циклически связаны
(3) если вершина math циклически связана с ребром math, а ребро mathциклически связано с вершиной math, то вершины math и math циклически связаны
(4) если ребро math циклически связано с вершиной math, а вершина math циклически связана с ребром math, то ребра mathи mathциклически связаны
Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?
(1) будет построен маршрут, проходящий через некоторые ребра дважды
(2) будет построен маршрут, не проходящий через некоторые ребра
(3) если в качестве стартовой выбрана концевая вершина, то будет построен эйлеров путь.
(4) если в качестве стартовой выбрана не концевая вершина, то будет построена последовательность вершин, не являющаяся маршрутом
Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?
(1) если дерево T содержит свободную вершину, отличную от a, то в графе имеется увеличивающий путь относительно данного паросочетания
(2) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания
(3) если в дереве T нет свободных вершин, отличных от a, то в графе нет увеличивающих путей относительно данного паросочетания, начинающихся в вершине a
(4) любое дерево достижимости с корнем a, построенное для данного паросочетания, имеет то же множество вершин, что и дерево T
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро math, math, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
(1) 5
(2) 10
(3) 15
(4) 20
Какие из следующих утверждений верны?
(1) если в графе каждый блок содержит ровно две вершины, то этот граф - дерево
(2) если каждый блок некоторого графа является двудольным графом, то и весь граф двудольный
(3) если каждый блок некоторого графа является планарным графом, то и весь граф планарный
(4) Если в каждом блоке связного графа имеется эйлеров цикл, то и во всем графе есть эйлеров цикл
Какие из следующих утверждений верны?
(1) если вершина x - предок вершины y в DFS-дереве, то math
(2) если вершина x - предок вершины y в DFS-дереве, то math
(3) если в графе имеется ребро (x,y), то math
(4) если вершина x - предок вершины y в DFS-дереве и в графе имеется ребро (x,y),то math