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

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

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

G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе G \cup H 12 ребер. Сколько ребер в графе G \oplus H ?

(Отметьте один правильный вариант ответа.)
Варианты ответа
12
5
17
7(Верный ответ)
Похожие вопросы
В графе с весовой функцией 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?
Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?
В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?
В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?
Для некоторого графа построено BFS-дерево с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?