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

Графы и алгоритмы

<<- Назад к вопросам

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

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа
существует оптимальный каркас, содержащий оба ребра e_1 ,e_2(Верный ответ)
существует оптимальный каркас, содержащий все три ребра e_1 ,e_2 ,e_3
существует оптимальный каркас, содержащий ребро e_1(Верный ответ)
если ребра e_1 ,e_2 ,e_3 не образуют цикла, то существует оптимальный каркас, содержащий все эти ребра(Верный ответ)
Похожие вопросы
В графе с весовой функцией w строится каркас с помощью алгоритма Прима. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?
В графе с весовой функцией w строится каркас с помощью алгоритма Крускала. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?
Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?
Какие из следующих утверждений верны для любого графаG и любого его подграфаH?
Для некоторого графа построено BFS-дерево с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?
Какие из следующих утверждений верны для любого взвешенного графа?
Сколько ребер нужно удалить из наименьшего реберного покрытия графа K_{4,6}  + K_7 , чтобы получить наибольшее паросочетание этого графа?
Сколько ребер нужно добавить к наибольшему паросочетанию графа K_{2,5}  + C_9, чтобы получить наименьшее реберное покрытие этого графа?