🗊Презентация Отношения, графы, деревья

Категория: Математика
Нажмите для полного просмотра!
Отношения, графы, деревья, слайд №1Отношения, графы, деревья, слайд №2Отношения, графы, деревья, слайд №3Отношения, графы, деревья, слайд №4Отношения, графы, деревья, слайд №5Отношения, графы, деревья, слайд №6Отношения, графы, деревья, слайд №7Отношения, графы, деревья, слайд №8Отношения, графы, деревья, слайд №9Отношения, графы, деревья, слайд №10Отношения, графы, деревья, слайд №11Отношения, графы, деревья, слайд №12Отношения, графы, деревья, слайд №13Отношения, графы, деревья, слайд №14Отношения, графы, деревья, слайд №15Отношения, графы, деревья, слайд №16
Скачать
Вы можете ознакомиться и скачать презентацию на тему Отношения, графы, деревья. Доклад-сообщение содержит 16 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Отношения, графы, деревья Определения
Описание слайда:
Отношения, графы, деревья Определения

Слайд 2


Определение. Пусть а и b — объекты. Определение. Пусть а и b — объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых в этом порядке. Упорядоченные пары (а, b) и (с, d) называются равными, если а = с и b = d. В противоположность этому {а, b}= {b, а}. Определение. Декартовым произведением множеств A и B, обозначаемым через АхВ, называют множество {(а, b) | аА и bB}. Пример. Пусть A = {1, 2} и В = {2, 3, 4}. Тогда AхB = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}
Описание слайда:
Определение. Пусть а и b — объекты. Определение. Пусть а и b — объекты. Через (а, b) обозначим упорядоченную пару, состоящую из объектов а и b, взятых в этом порядке. Упорядоченные пары (а, b) и (с, d) называются равными, если а = с и b = d. В противоположность этому {а, b}= {b, а}. Определение. Декартовым произведением множеств A и B, обозначаемым через АхВ, называют множество {(а, b) | аА и bB}. Пример. Пусть A = {1, 2} и В = {2, 3, 4}. Тогда AхB = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}

Слайд 3


Отношения Определение. Пусть А и В —множества. Отношением из А в В называется любое подмножество множества АхВ. Если А = B, то говорят, что отношение задано, или определено, на А (или просто, что это — отношение на множестве A). Если R — отношение из A в B и (а, b)R, то пишут аRb. A — область определения отношения R, В —множество его значений. Определение. Отношение {(b, а) | (а, b)  R} называется обратным к отношению R и часто обозначается через R-1.
Описание слайда:
Отношения Определение. Пусть А и В —множества. Отношением из А в В называется любое подмножество множества АхВ. Если А = B, то говорят, что отношение задано, или определено, на А (или просто, что это — отношение на множестве A). Если R — отношение из A в B и (а, b)R, то пишут аRb. A — область определения отношения R, В —множество его значений. Определение. Отношение {(b, а) | (а, b)  R} называется обратным к отношению R и часто обозначается через R-1.

Слайд 4


Свойства отношений Определение. Пусть A—множество и R — отношение на A. Отношение R называется рефлексивным, если аRа для всех a из А, симметричным, если аRb влечет bRa для a и b из A, транзитивным, если аRb и bRс влекут аRс для а, b и с из A. Элементы а, b и с не обязаны быть различными. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Важное свойство любого отношения эквивалентности R, определенного на множестве A, заключается в том, что оно разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности.
Описание слайда:
Свойства отношений Определение. Пусть A—множество и R — отношение на A. Отношение R называется рефлексивным, если аRа для всех a из А, симметричным, если аRb влечет bRa для a и b из A, транзитивным, если аRb и bRс влекут аRс для а, b и с из A. Элементы а, b и с не обязаны быть различными. Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности. Важное свойство любого отношения эквивалентности R, определенного на множестве A, заключается в том, что оно разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности.

Слайд 5


Графы Определение. Неупорядоченный граф G — это пара (А, R), где А — множество элементов, называемых вершинами (или узлами), а R — отношение на множестве А. Если R — несимметричное отношение, то G — ориентированный граф; R — симметричное, то G —неориентированный граф. Пример. A={1, 2, 3, 4} , R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}.
Описание слайда:
Графы Определение. Неупорядоченный граф G — это пара (А, R), где А — множество элементов, называемых вершинами (или узлами), а R — отношение на множестве А. Если R — несимметричное отношение, то G — ориентированный граф; R — симметричное, то G —неориентированный граф. Пример. A={1, 2, 3, 4} , R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}.

Слайд 6


Пара (а, b)R называется дугой (или ребром) графа G. Пара (а, b)R называется дугой (или ребром) графа G. Говорят, что дуга выходит из вершины а и входит в вершину b. Если (а, b) — дуга, то говорят, что вершина а предшествует вершине b, а вершина b следует за вершиной a. Вершина b смежна с вершиной a.
Описание слайда:
Пара (а, b)R называется дугой (или ребром) графа G. Пара (а, b)R называется дугой (или ребром) графа G. Говорят, что дуга выходит из вершины а и входит в вершину b. Если (а, b) — дуга, то говорят, что вершина а предшествует вершине b, а вершина b следует за вершиной a. Вершина b смежна с вершиной a.

Слайд 7


Определения. Определения. Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (или маршрутом) длины n из вершины а0 в вершину аn, если для каждого 1≤i≤n существует дуга, выходящая из вершины аi-1 и входящая в вершину аi. Если существует путь из вершины а0 в вершину аn, то говорят, что аn достижима из а0. Циклом называется путь (а0, а1, ...,аn), в котором а0 = аn. Граф называется сильно связным, если для любых двух разных вершин а и b существует путь из a в b.
Описание слайда:
Определения. Определения. Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (или маршрутом) длины n из вершины а0 в вершину аn, если для каждого 1≤i≤n существует дуга, выходящая из вершины аi-1 и входящая в вершину аi. Если существует путь из вершины а0 в вершину аn, то говорят, что аn достижима из а0. Циклом называется путь (а0, а1, ...,аn), в котором а0 = аn. Граф называется сильно связным, если для любых двух разных вершин а и b существует путь из a в b.

Слайд 8


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

Слайд 9


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

Слайд 10


Дуга и путь в ациклическом графе Если (a, b) – дуга в ациклическом графе, то a – прямой предок b, b – прямой потомок a. Если в ациклическом графе существует путь из a в b, то a – предок b, b – потомок a.
Описание слайда:
Дуга и путь в ациклическом графе Если (a, b) – дуга в ациклическом графе, то a – прямой предок b, b – прямой потомок a. Если в ациклическом графе существует путь из a в b, то a – предок b, b – потомок a.

Слайд 11


Дерево (частный вид ациклического графа) Определение. (Ориентированным) деревом Т называется (ориентированный) граф G = (А,R) со специальной вершиной r А, называемый корнем, у которого степень по входу вершины r равна 0, степень по входу всех остальных вершин дерева Т равна 1, каждая вершина аА достижима из r. Дерево Т обладает следующими свойствами: Т—ациклический граф, для каждой вершины дерева Т существует единственный путь, ведущий из корня в эту вершину.
Описание слайда:
Дерево (частный вид ациклического графа) Определение. (Ориентированным) деревом Т называется (ориентированный) граф G = (А,R) со специальной вершиной r А, называемый корнем, у которого степень по входу вершины r равна 0, степень по входу всех остальных вершин дерева Т равна 1, каждая вершина аА достижима из r. Дерево Т обладает следующими свойствами: Т—ациклический граф, для каждой вершины дерева Т существует единственный путь, ведущий из корня в эту вершину.

Слайд 12


Поддеревом дерева Т = (А, R) называется любое дерево Поддеревом дерева Т = (А, R) называется любое дерево T' =(А', R'), у которого А' непусто и содержится в A, R' = (A'хA')R, ни одна вершина из множества А \ А' не является потомком вершины из множества А‘. Ориентированный граф, состоящий из нескольких деревьев, называется лесом.
Описание слайда:
Поддеревом дерева Т = (А, R) называется любое дерево Поддеревом дерева Т = (А, R) называется любое дерево T' =(А', R'), у которого А' непусто и содержится в A, R' = (A'хA')R, ни одна вершина из множества А \ А' не является потомком вершины из множества А‘. Ориентированный граф, состоящий из нескольких деревьев, называется лесом.

Слайд 13


Пусть Т=(A, R) – дерево, (a, b) R, тогда Пусть Т=(A, R) – дерево, (a, b) R, тогда a – отец b, а b – сын a. Глубина или уровень вершины – длина пути от корня до этой вершины. Высота вершины – длина максимального пути от этой вершины до листа. Высота дерева – длина максимального пути от корня до листа. Глубина корня = 0.
Описание слайда:
Пусть Т=(A, R) – дерево, (a, b) R, тогда Пусть Т=(A, R) – дерево, (a, b) R, тогда a – отец b, а b – сын a. Глубина или уровень вершины – длина пути от корня до этой вершины. Высота вершины – длина максимального пути от этой вершины до листа. Высота дерева – длина максимального пути от корня до листа. Глубина корня = 0.

Слайд 14


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

Слайд 15


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

Слайд 16


Представление полных бинарных деревьев с помощью массива Пусть T[2k-1] – массив для хранения вершин дерева, k- высота дерева. В T[1] хранится корень дерева. Левый сын узла i расположен в позиции 2*i, правый сын – в позиции 2*i+1. Отец узла, находящегося в позиции i>1, расположен в позиции i/2.
Описание слайда:
Представление полных бинарных деревьев с помощью массива Пусть T[2k-1] – массив для хранения вершин дерева, k- высота дерева. В T[1] хранится корень дерева. Левый сын узла i расположен в позиции 2*i, правый сын – в позиции 2*i+1. Отец узла, находящегося в позиции i>1, расположен в позиции i/2.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию