Сколько различных наибольших паросочетаний имеется в графе ?
(Отметьте один правильный вариант ответа.)
Варианты ответа
5
20
15(Верный ответ)
10
Похожие вопросы
G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе 12 ребер. Сколько ребер в графе ?
Сколько различных каркасов имеется у графа ?
В дереве имеется ровно три листа , причем , , . Сколько всего вершин в этом дереве?
Пусть и - ребра с наименьшими весами в некотором взвешенном графе, причем . Какие из следующих утверждений верны для любого графа и любой весовой функции?
Для некоторого графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
Для двудольного графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?
В графе с весовой функцией строится каркас с помощью алгоритма Прима. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
В графе с весовой функцией строится каркас с помощью алгоритма Крускала. Пусть - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого ?
Дан граф с множеством ребер . Для каких из перечисленных ниже семейств подмножеств множества пара является матроидом для любого графа ?
Дан граф с множеством вершин , - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара является матроидом,?