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

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

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

В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

(Отметьте один правильный вариант ответа.)
Варианты ответа
8
7
6
5(Верный ответ)
Похожие вопросы
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i < j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?
Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
Для некоторого графа построено BFS-дерево с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?
Дан граф G с множеством вершин V, \Phi - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара (V,\Phi ) является матроидом,?
Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?
G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе G \cup H 12 ребер. Сколько ребер в графе G \oplus H ?
Граф G имеет 4 вершины, а в его матрице смежности 8 единиц. Граф H имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа G \circ H ?
В дереве имеется ровно три листа a,b,c, причем d(a,b) = 8, d(a,c) = 9, d(b,c) = 5. Сколько всего вершин в этом дереве?
Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?