Задача 11. Представить в виде ориентированного графа отношение r =<X, R>

Представить в виде ориентированного графа отношение r =<X, R>

Вариант 1. X= {2, 4, 6, 8}, R = {<x, y>: x < y}

Вариант 2. X= {1, 3, 5}, R = {<x, y>: x £ y}

Вариант 3. X = P ({a, b, c}), R = {<A, B>: A Ì B}

Вариант 4. X = P ({a, b}), R = {<A, B>: A Í B}

Вариант 5. X = {2, 4, 8, 10}, R = {<x, y>: x ³ y}

Вариант 6. X={2, 4, 16, 22}, R ={<x, y>: x являетсяделителем y}

Вариант 7. X = {2, 4, 16, 22}, R ={<x, y>: { x+y делится на 6 }

Вариант 8. X = {2, 4, 16, 22}, R = {<x, y>: x / y четно }

Вариант 9. X = {2, 4, 8, 10}, R = {<x, y>: x - y делится на 3 }

Вариант 10. X = P ({a, b, c}), R = {<A, B>: A Ç B ¹ Æ}

Примечание. Выше P (A) обозначает множество всех подмножеств множества A.

Задача 12.

Варианты 1-4. Нарисовать диаграмму орграфа G=<V, X> и определить, будет ли он связным, сильно связным или несвязным.

Вариант 1. V={v₁, v₂, v_3,, v₄, v₅},

X={<v₁, v₂>, <v₂, v₁>, <v₂, v₂>, <v₂, v₃>, <v₂, v₄>, <v₄, v₃>, <v₄, v₂>, <v₄, v₁>}

Вариант 2. V={v₁, v₂, v_3,, v₄, v₅},

X={<v₁, v₂>, <v₁, v₃>, <v₁, v₅>, <v₂, v₃>, <v₂, v₄>, <v₃, v₃>, <v₃, v₄>, <v₃, v₁>,
<v₄, v₅>, <v₅, v₁>}

Вариант 3. V={v₁, v₂, v_3,, v₄, v₅},

X= {<v₁, v₂>, <v₂, v₁>, <v₂, v₃>, <v₃, v₁>, <v₃, v₃>, <v₄, v₁>, <v₅, v₅>}

Вариант 4. V={v₁, v₂, v_3,, v₄, v₅ , v₆},

X={<v₁, v₂>, <v₁, v₅>, <v₂, v₄>, <v₄, v₃>, <v₃, v₆>, <v₄, v₅>, <v₅, v₁>, <v₆, v₁>, <v₆, v₆>}

Варианты 5-8. Пусть Т =<V, X> ‑ ориентированное дерево. Разрезом С дерева Т называется подмножество вершин Т таких, что

а) не существует двух вершин С на маршруте в Т;

б) ни одна вершина не может быть добавлена к С без нарушения пункта а).

Определить все разрезы следующего ориентированного дерева:

Вариант 5. V={v₁, v₂, v_3,, v₄, v₅ , v₆},

X={<v₁, v₂>, <v₁, v₃>, <v₁, v₄>, <v₃, v₅>, <v₃, v₆>}

Вариант 6. V={v₁, v₂, v_3,, v₄, v₅ , v₆},

X={<v₁, v₂>, <v₁, v₅>, <v₂, v₃>, <v₂, v₄>, <v₅, v₆>}

Вариант 7. V={v₁, v₂, v_3,, v₄, v₅ , v₆},

X={<v₁, v₂>, <v₁, v₆>, <v₂, v₃>, <v₂, v₄>, <v₂, v₅>}

Вариант 8. V={v₁, v₂, v_3,, v₄, v₅ , v₆},

X={<v₁, v₂>, <v₁, v₃>, <v₁, v₄>, <v₂, v₆>, <v₃, v₇>, <v₃, v₈>, <v₄, v₅>}

Варианты 9-10. Если T ‑ ориентированное дерево, то уровень вершины определяют как максимальную длину маршрута от этой вершины до листа. Глубина вершины ‑ это длина пути от корня до этой вершины. Глубиной дерева T называют длину самого длинного маршрута в T. Высотой вершины называют глубину дерева T за вычетом глубины вершины. Высотой дерева T является высота корня.

Пусть T =<V, X>, V={v₁, v₂,..., v₉},

X={<v₁, v₂>, <v₁, v₃>, <v₁, v₄>, <v₃, v₅>, <v₃, v₆>, <v₃, v₇>, <v₅, v₈>, <v₅, v₉>}

Вариант 9. Нарисовать Т со значениями уровней и со значениями глубин в качестве меток вершин.Определить глубину дерева Т.

Вариант 10. Нарисовать Т со значениями уровней и со значениями высот в качестве меток вершин. Определить высоту дерева Т.