Какие из следующих утверждений о работе алгоритма Дейкстры на графе с n вершинами верны?А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не возрастают.Б) Число этапов (итераций основного цикла) не превосходит (n - 1).В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не длиннее кратчайшего пути из исходной вершины в любую вершину множества (V \ S).
Какие из следующих утверждений о работе алгоритма Дейкстры верны?А) Если в графе нет циклов отрицательной длины, то алгоритм Дейкстры работает верно.Б) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S не короче кратчайшего пути из исходной вершины в любую вершину множества (V \ S).В) Если длины всех ребер в графе попарно различны, то дерево кратчайших путей из заданной вершины единственно.
Пусть задан ориентированный нагруженный граф G:V= {a, b, c, d, e, f, g, h }, E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
Пусть задан ориентированный нагруженный граф G:V= {a, b, c, d, e, f, g, h }, E= { (a, b; 5), (a, c; 32), (a, d; 2), (a, e; 32), (a, f; 12), (a, g; 15), (b, f; 6), (b, e; 20), ( b, h; 4), (c, h; 5), (d, g; 8), (d, h; 21), (g, c; 10), (g; e; 12), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
Пусть задан ориентированный нагруженный граф G:V= {a, b, c, d, e, f, g, h }, E= { (a, c; 24), (a, d; 8), (a, e; 12), (a, f; 2), (a, g; 15), (b, c; 5), ( b,g; 15), (c, h; 5), (d, b; 10), (d, e; 3), (d, g; 10), (d, h; 21), (e, g; 2), (f, d; 5), (f, b; 17) }
(здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны?Сумма степеней всех вершин G четна.Если в G имеется ровно две вершины четной степени, то они связаны путем Если в G имеется ровно две вершины нечетной степени, то они связаны путем
Пусть задан неориентированный нагруженный граф
G:
V= {a, b, c, d, e, f, g, h, k }, E= {(a, b; 9), (a, c; 6), (b, c; 10), (b, d; 5), (b, e; 4), (d, e; 6), (d, f; 4), (e, f; 25),(f, g; 20), (g, h; 8), (g, k; 10), (h, k; 7) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, c) II) (f, g) III) (g, k)
Пусть задан неориентированный нагруженный граф
G:
V= {a, b, c, d, e, f, g, h }, E= {(a,b; 5), (a, h; 7), (b, c; 4), (b, f; 3), (c, d; 6), (c,f; 7), (d, e; 10), (e, f; 9), ( b,g; 15), (g, h; 10) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (b, g) II) (c, f) III) (d, l)
Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)?По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).В точности две переменных из p1, p2, p3, p4истинны (равны 1).Хотя бы одна переменная из p1, p2, p3, p4истинна (равна 1).
Пусть задан неориентированный нагруженный граф G:
V= {a, b, c, d, e, f, g, h, k }, E= {(a, b; 10), (a, c; 7), (b, f; 21), (b, d; 9), (c, d; 8), (f, e; 7), (f, g; 8), (e, k; 12), (e, h; 10), (g, h; 8) }
(здесь каждая скобка
(u,v; D) задает ребро
(u,v) из
E и его "вес"
c(u,v)=D ).Какие из следующих трех ребер не могут попасть ни в какой минимальный остов?
I) (a, b) II) (e, h) III) (b, f)
