Используя алгоритм БыстроеЗамыкание, вычислить замыкание для набора исходных продуктов X = {c, d} и следующей системы технологических процессов F:

a, b →​ h;

a, b, c, g →​ f;

d, g →​ a; .

d, f →​ k;

b, k →​ d;

c, f, k →​ h;

h, d, c →​ e;

c, d →​ g;

c, d →​ f

Определите длину кратчайшей цепочки технологических процессов, приводящей к получению e.

Правильный ответ:

• # Пусть задан ориентированный нагруженный граф 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 в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
• # Пусть X ={a, b, c} – множество из трех элементов. Число трехместных отношений, которые можно определить на X равно:
• # Булева функция f(X0, X1, X2)равна 1, если число, двоичная запись которого имеет вид X2X1X0, равно 3, 4, 5или 7. Какая из следующих формул задает эту функцию?
• # Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны? Сумма степеней всех вершин G четна.Если в G имеется ровно две вершины четной степени, то они связаны путем Если в G имеется ровно две вершины нечетной степени, то они связаны путем
• # Пусть граф G=(V,E) задан своей матрицей смежности A_G=\begin{array}{ccccc} 0& 1 &0 &0 &0\\ 0 &1& 0& 0& 0\\ 0 &0 &0 &1 &0\\ 0 &1 &0 &0 &1\\ 1 &0 &0 &0 &1 \end{array} Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.