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