Представить в виде ориентированного графа отношение 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={v1, v2, v3,, v4, v5},
X={<v1, v2>, <v2, v1>, <v2, v2>, <v2, v3>, <v2, v4>, <v4, v3>, <v4, v2>, <v4, v1>}
Вариант 2. V={v1, v2, v3,, v4, v5},
X={<v1, v2>, <v1, v3>, <v1, v5>, <v2, v3>, <v2, v4>, <v3, v3>, <v3, v4>, <v3, v1>,
<v4, v5>, <v5, v1>}
Вариант 3. V={v1, v2, v3,, v4, v5},
X= {<v1, v2>, <v2, v1>, <v2, v3>, <v3, v1>, <v3, v3>, <v4, v1>, <v5, v5>}
|
|
Вариант 4. V={v1, v2, v3,, v4, v5 , v6},
X={<v1, v2>, <v1, v5>, <v2, v4>, <v4, v3>, <v3, v6>, <v4, v5>, <v5, v1>, <v6, v1>, <v6, v6>}
Варианты 5-8. Пусть Т =<V, X> ‑ ориентированное дерево. Разрезом С дерева Т называется подмножество вершин Т таких, что
а) не существует двух вершин С на маршруте в Т;
б) ни одна вершина не может быть добавлена к С без нарушения пункта а).
Определить все разрезы следующего ориентированного дерева:
Вариант 5. V={v1, v2, v3,, v4, v5 , v6},
X={<v1, v2>, <v1, v3>, <v1, v4>, <v3, v5>, <v3, v6>}
Вариант 6. V={v1, v2, v3,, v4, v5 , v6},
X={<v1, v2>, <v1, v5>, <v2, v3>, <v2, v4>, <v5, v6>}
Вариант 7. V={v1, v2, v3,, v4, v5 , v6},
X={<v1, v2>, <v1, v6>, <v2, v3>, <v2, v4>, <v2, v5>}
Вариант 8. V={v1, v2, v3,, v4, v5 , v6},
X={<v1, v2>, <v1, v3>, <v1, v4>, <v2, v6>, <v3, v7>, <v3, v8>, <v4, v5>}
Варианты 9-10. Если T ‑ ориентированное дерево, то уровень вершины определяют как максимальную длину маршрута от этой вершины до листа. Глубина вершины ‑ это длина пути от корня до этой вершины. Глубиной дерева T называют длину самого длинного маршрута в T. Высотой вершины называют глубину дерева T за вычетом глубины вершины. Высотой дерева T является высота корня.
Пусть T =<V, X>, V={v1, v2,..., v9},
X={<v1, v2>, <v1, v3>, <v1, v4>, <v3, v5>, <v3, v6>, <v3, v7>, <v5, v8>, <v5, v9>}
Вариант 9. Нарисовать Т со значениями уровней и со значениями глубин в качестве меток вершин.Определить глубину дерева Т.
Вариант 10. Нарисовать Т со значениями уровней и со значениями высот в качестве меток вершин. Определить высоту дерева Т.