Графы: деревья - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Графы: деревья. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ПРОГРАММИРОВАНИЕ Семинар 11. Графы: деревья

Слайд 2

Описание слайда:

Определения (a, b) = {a, {a, b}} — упорядоченная пара. (a, b) = (c, d)⇔ a = c & b = d {a, b} = {b, a} A× B = {(a, b) | a ∈ A & b ∈ B} — декартово произведение.

Слайд 3

Описание слайда:

Пример A = {1, 2} B = {2, 3, 4} A× B = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}

Слайд 4

Описание слайда:

Отношения Произвольное подмножество A× B называется отношением из A в B. A — область определения. B — область значений. Если A = B, то отношение задано на A. (a, b)∈ R ⇔ aRb

Слайд 5

Описание слайда:

Свойства отношений Пусть на множестве A задано отношение R: рефлексивное, если aRa∀a∈ A; симметричное, если aRb⇒ bRa∀a, b∈ A; транзитивное, если aRb & bRc⇒ aRc∀a, b, c∈ A. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. A = ⋃a∈ A Aa — разбиение: Aa = {b | aRb} — класс эквивалентности; Aa⋂ Ab =∅, a ≠ b.

Слайд 6

Описание слайда:

Графы Неупорядоченный граф G = (V, E), где: V — множество вершин; E — отношение на V. Граф G ориентированный (орграф), если E — асимметричное, иначе — неориентированный.

Слайд 7

Описание слайда:

Пример V = {1, 2, 3, 4} E = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}

Слайд 8

Описание слайда:

Графы (a, b)∈ R — дуга (ребро): дуга выходит из a и входит в b; a предшествует b; b следует за a; b смежна с a.

Слайд 9

Описание слайда:

Пути в графах Последовательность вершин (a0, a1, a2, …, an), n ≥ 1 называется путём (маршрутом) длины n из a0 в an, если (ai - 1, ai)∈ E∀i∈ {1, 2, …, n}, при этом, говорят, что an достижима из a0. Путь, в котором a0 = an, называется циклом. Орграф называется сильно связным, если для любых его двух вершин существует путь из одной в другую.

Слайд 10

Описание слайда:

Степень вершины Степень по входу (полустепень входа) вершины — число входящих в неё дуг. Степень по выходу (полустепень выхода) вершины — число исходящих из неё дуг. Если граф неориентированный, то степень вершины — количество связанных с ней рёбер.

Слайд 11

Описание слайда:

Ациклические графы Ациклический граф — орграф без циклов. Вершина с полустепенью входа 0 — базовая. Вершина с полустепенью выхода 0 — лист (концевая).

Слайд 12

Описание слайда:

Пример Базовая

Слайд 13

Описание слайда:

Ациклические графы (a, b)∈ R — дуга: a — прямой предок b; b — прямой потомок a. Если существует путь из a в b, то: a — предок b; b — потомок a.

Слайд 14

Описание слайда:

Деревья (Ориентированное) дерево — (ориентированный) граф со специальной вершиной r (корнем): полустепень по входу равна 0; полустепень по входу всех остальных равна 1; каждая вершина достижима из корня. Свойства: 1. Дерево — ациклический граф. 2. Для каждой вершины дерева существует единственный путь в неё из корня.

Слайд 15

$Поддерево Поддерево дерева T = (V, E) — любое дерево T' = (V', E'): 1. V' ≠ ∅ & V'⊆ V. 2. E' = (V'× V')⋂ E. 3. Ни одна вершина из V \ V' не является потомком вершины из V'. Орграф из нескольких деревьев — лес.$

Описание слайда:

Поддерево Поддерево дерева T = (V, E) — любое дерево T' = (V', E'): 1. V' ≠ ∅ & V'⊆ V. 2. E' = (V'× V')⋂ E. 3. Ни одна вершина из V \ V' не является потомком вершины из V'. Орграф из нескольких деревьев — лес.

Слайд 16

Описание слайда:

Пример

Слайд 17

Описание слайда:

Деревья (a, b)∈ R — дуга: a — отец b; b — сын a. Глубина (уровень) вершины — длина пути до неё из корня. Высота вершины — длина максимального пути от неё до листа. Высота дерева — длина максимального пути от корня до листа.

Слайд 18

Описание слайда:

Бинарные деревья Упорядоченное дерево — дерево, в котором множество сыновей каждой вершины упорядочено слева направо. Бинарное дерево — это упорядоченное дерево: 1. Любой сын либо левый, либо правый. 2. Любая вершина имеет не более одного левого и не более одного правого сына.

Слайд 19

Описание слайда:

Пример

Слайд 20

Описание слайда:

Бинарные деревья Бинарное дерево полное, если существует целое k, такое что любая вершина глубины меньше k имеет и левого, и правого сыновей, а любая вершина глубины k — лист.

Слайд 21

Описание слайда:

Пример

Слайд 22

Описание слайда:

Представление полных бинарных деревьев Массив T[2k - 2]: T[0] — корень; левый сын вершины i — T[2 * i - 1]; правый сын вершины i — T[2 * i]. Отец вершины в позиции i > 0 расположен в позиции ⌊i / 2⌋ - 1.

Слайд 23

Описание слайда:

Пример T == {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Слайд 24

Описание слайда:

Обходы деревьев Обход дерева — способ исследования вершин дерева, при котором каждая вершина проходится только один раз. Виды: 1. В глубину. 2. В ширину.

Слайд 25

Описание слайда:

Обходы деревьев в глубину Пусть T — дерево c корнем r, а v1, v2, …, vn — сыновья r. Прямой (префиксный) обход: 1. Посетить корень r. 2. Посетить в прямом порядке поддеревья с корнями v1, v2, …, vn. Обратный (постфиксный) обход: 1. Посетить в обратном порядке поддеревья с корнями v1, v2, …, vn. 2. Посетить корень r. Внутренний (инфиксный) обход: 1. Посетить в0 внутреннем порядке левое поддерево корня r. 2. Посетить корень r. 3. Посетить в0 внутреннем порядке правое поддерево корня r.

Слайд 26

Описание слайда:

Пример: прямой обход

Слайд 27

Описание слайда:

Пример: обратный обход

Слайд 28

Описание слайда:

Пример: внутренний обход

Слайд 29

Описание слайда:

Пример

Слайд 30

Описание слайда:

Пример Префиксный: + * a - d e / + f g c Постфиксный: a d e - * f g + c / + Инфиксный: a * (d - e) + (f + g) / c

Слайд 31

Описание слайда:

Обход в ширину Это обход по уровням, начиная от корня, слева направо (или справа налево). Алгоритм: 0. Поместить в очередь корень. 1. Взять из очереди очередную вершину. Поместить в очередь всех её сыновей слева направо (справа налево). 2. Если очередь пуста — конец. Иначе на шаг 1.

Слайд 32

Описание слайда:

Пример b h i i a j a j k l j k l k l d e l d e f g d e f g e f g f g g

Слайд 33

Описание слайда:

Представления деревьев Левое скобочное представление Lrep(T): 1. Если a — корень T с поддеревьями T1, T2, …, Tn, корни которых — сыновья a, то Lrep(T) = a(Lrep(T1), Lrep(T2), …, Lrep(Tn)). 2. Если у a сыновей нет, то Lrep(T) = a. Правое скобочное представление Rrep(T): 1. Если a — корень T с поддеревьями T1, T2, …, Tn, корни которых — сыновья a, то Rrep(T) = (Rrep(T1), Rrep(T2), …, Rrep(Tn))a. 2. Если у a сыновей нет, то Rrep(T) = a.

Слайд 34

Описание слайда:

Пример Lrep(T) = b(h(a, j(d)), i(k(e, f, g), l)) Rrep(T) = ((a, (d)j)h, ((e, f, g)k, l)i)b

Слайд 35

Описание слайда:

Представления деревьев Список прямых предков: Составляется список прямых предков для вершин дерева с номерами 1, 2, …, n. Для корня полагаем, что предок имеет номер 0.

Слайд 36

Описание слайда:

Пример 0 1 2 2 4 1 6 6 7 7 7

Слайд 37

Описание слайда:

Дерево двоичного поиска Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждая вершина v которого помечена элементом l(v)∈ S: 1. l(u) < l(v) для всех вершин u из левого поддерева вершины v. 2. l(u) > l(v) для всех вершин u из правого поддерева вершины v. 3. ∀a∈ S ∃!v: l(v) = a.

Слайд 38

Описание слайда:

Пример

Слайд 39

Описание слайда:

Просмотр дерева двоичного поиска Вход: дерево T двоичного поиска для множества S, элемент a. Выход: истина, если a∈ S, ложь — иначе. Метод: Если T = ∅, то выдать ложь, иначе выдать ПОИСК(a, r), где r — корень дерева T. функция ПОИСК(a, v) { если a = l(v) то выдать истина иначе если a < l(v) то если v имеет левого сына w то выдать ПОИСК(a, w) иначе выдать ложь иначе если v имеет правого сына w то выдать ПОИСК(a, w) иначе выдать ложь }

Слайд 40

Описание слайда:

Построение дерева двоичного поиска Вход: последовательность слов произвольной длины. Выход: введённые слова в лексикографическом порядке. Метод: каждое слово при вводе помещается в вершину дерева двоичного поиска. По окончании ввода дерево обходится в инфиксном порядке и слова выводятся.