Содержание
- 2. Определение. Пусть а и b — объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов
- 3. Отношения Определение. Пусть А и В —множества. Отношением из А в В называется любое подмножество множества
- 4. Свойства отношений Определение. Пусть A—множество и R — отношение на A. Отношение R называется рефлексивным, если
- 5. Графы Определение. Неупорядоченный граф G — это пара (А, R), где А — множество элементов, называемых
- 6. Пара (а, b)∈R называется дугой (или ребром) графа G. Говорят, что дуга выходит из вершины а
- 7. Определения. Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (или маршрутом) длины n из вершины
- 8. Степень вершины Степенью по входу (полустепенью входа) вершины а назовем число входящих в нее дуг, а
- 9. Ациклические графы Ациклическим графом называется (ориентированный) граф, не имеющий циклов. Вершину, степень по входу которой равна
- 10. Дуга и путь в ациклическом графе Если (a, b) – дуга в ациклическом графе, то a
- 11. Дерево (частный вид ациклического графа) Определение. (Ориентированным) деревом Т называется (ориентированный) граф G = (А,R) со
- 12. Поддеревом дерева Т = (А, R) называется любое дерево T' =(А', R'), у которого А' непусто
- 13. Пусть Т=(A, R) – дерево, (a, b) ∈R, тогда a – отец b, а b –
- 14. Бинарные деревья Упорядоченное дерево – это дерево, в котором множество сыновей каждой вершины упорядочено слева направо.
- 15. Бинарное дерево называется полным, если существует некоторое целое k, такое что любой узел глубины меньше k
- 17. Скачать презентацию