Чему равно число связных компонент неориентированного графа G=(V,E), где V={1, 2, 3, 4, 5, 6, 7, 8, 9}, E={(1,4), (2,7), (3,9), (5,4), (1,5), (6,7)}?

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

• # Пусть задан неориентированный граф G=(V,E): V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, f), (d, e), (f, e), (a, g), (g, i), (h, g), (i, h) }. Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
• # Для следующей формулы определить, какие из занумерованных вхождений переменных свободны (F), а какие являются связанными (C). \begin{array}{llllllllll} (\forall x(P(x,y) & \rightarrow & \exists y(\forall z(Q(x,y,z) &\rightarrow & P(x,z)) &\rightarrow & P(z,y))) & \rightarrow & Q(x,y,z)) \\ \phantom{ (\forall x(P(}1\phantom{,}2 & & \phantom{\exists y(\forall z(Q(}3\phantom{,y,}4 & & \phantom{P(x,}5 & & \phantom{P(}6\phantom{,} 7& & \phantom{Q(}8\phantom{,}9\end{array}
• # Пусть отношения R и S со схемами R(A,B,C) и S(B,C,D) заданы перечислениями своих кортежей: R ={(a, 5, 8), (a, 6, 8), (a1, 3, 12), (a1, 6, 2)},S = {(6, 8, d), (6, 2, d), (5, 8, d1), (3, 12, d2)}. Какое отношение Qi (i=1, 2, 3) задается выражением реляционной алгебры Q = πAD(σ B >3(R) >< S) и какая из указанных формул Fj (j=1,2) ему эквивалентна? Q1 ={(a,d), (a,d1), (a1,d1) } F1= ∃b ∃c (R(a, b, c) ∧ S(b, c, d) ∧ (b > 3)) Q2 ={(a,d), (a,d1), (a1,d), (a1,d1) } F2= ∃b ∃c ((R(a, b, c) ∧ S(b, c, d) )→​ (b > 3)) Q3 ={(a,d), (a,d1), (a1,d), (a1,d1), (a1,d2) }
• # Пусть база данных включает отношение Книга(Автор, Название, Издательство, ГодИздания). Укажите, какие из приведенных формул логики предикатов выражают следующее ограничение целостности: атрибуты Автор и Название образуют ключ отношения. Ф1 = ∀a∀k∀p∀y∀a1∀k1∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a1,k1,p1,y1) ∧ (p≠p1 ∨ y≠y1)) →​ (a ≠ a1 ∨ k≠k1))Ф2 = ∀a∀k∃p∃y (Книга (a,k,p,y) →​ ∃p1∃y1 (Книга (a,k,p1,y1) →​ (p=p1 ∧ y=y1)))Ф3 = ∀a∀k∀p∀y∀p1∀y1 ((Книга (a,k,p,y) ∧ (Книга (a,k,p1,y1)) →​ (p=p1 ∧ y=y1)))
• # Пусть G=( V, E) - это конечный ориентированный граф без циклов и |E |> 0. Какие из следующих утверждений верны? В G есть вершина, в которую не входят ребра.В G есть вершина, из которой не выходят ребра.В G есть изолированная вершина, т.е. вершина, у которой нет инцидентных ребер.