Какие из следующих утверждений о работе алгоритма Дейкстры верны?

А) Значения D[w] текущего расстояния от исходной вершины до вершины w, добавляемой на каждом этапе к множеству отмеченных вершин S, не убывают.

Б) В дереве кратчайших путей, построенном алгоритмом Дейкстры, длины ребер на каждой ветви не убывают.

В) На каждом этапе алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества S.

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

• # Пусть задан неориентированный нагруженный граф 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)
• # Построить таблицу для функции, заданной формулой и определить число наборов аргументов, на которых она равна 1.
• # Какие из следующих условий можно выразить булевскими формулами от переменных p1, p2, p3, p4, использующими лишь логические связки ∧и ∨(без отрицания ¬)? По крайней мере две переменные из p1, p2, p3, p4истинны (равны 1).Не все из переменных из p1, p2, p3, p4ложны (равны 0).Нечетное число переменных из p1, p2, p3, p4истинны (равны 1).
• # Какие из следующих формул задают нелинейные функции: A= (Y →​¬X) →​ Z, B = (X∧ Y∧ Z) ∨ (¬ X∧ ¬Y ) ∨ (X∧ Y∧ ¬ Z), C= ( Z→​ X) ∨Y
• # Какие из следующих формул логики предикатов являются тождественно истинными? ( ∀x P(x) ∨ ∀x Q(x) ) →​ ∀x ( P(x) ∨ Q(x) )∀x ( P(x) ∨ Q(x) ) →​ ( ∀x P(x) ∨ ∀x Q(x) )(∃x P(x) ∨ ∃x Q(x) ) →​ ∃x ( P(x) ∨ Q(x) )