Презентация на тему "Списки, графы, деревья и таблицы"

Структуры данных

Линейные

Односвязный список

Стек

Очередь

Нелинейные

Дерево

Граф

Односвязный список

Стек

Очередь

Дерево

Граф

Таблица

Таблица

От англ. Last In, First Out – последним пришёл, первым ушёл.

От англ. First In, First Out – первым пришёл, первым ушёл.

Для каждого элемента, кроме крайних, есть предыдущий и следующий элементы.

Элементы иерархической структуры связаны отно-шением «предок - потомок».

Множество элементов вместе с набором отношений между ними.

В ячейках содержится информация о свойстве пар объектов.

Невзвешенный

Взвешенный

Ориентированный

Неориентированный

Ребро

Дуга

Вес ребра

Вес вершины

Вершина

Таблица

Корень

Дерево – совокупность элементов (вершин), в которой выделен один элемент, а остальные элементы разбиты на непересекающиеся множества (поддеревья). Каждое поддерево является деревом, а его корень является потомком корня дерева. Все элементы связаны между собой отношением «предок — потомок». В результате образуется иерархическая структура вершин.

Частным случаем дерева является бинарное дерево, в котором каждая вершина может иметь не более двух потомков.

Такую таблицу называют матрицей смежности. Матрица смежности не-ориентированного графа симметрична относительно главной диагонали. У ориентированного графа такая симметрия отсутствует.

Решение
K(X) – количествомаршрутов от начала до X.
K(A)=1
K(B)=K(A)=1
K(C)=K(B)=1
K(D)=K(B)=1
K(E)=K(C)+K(D)=1+1=2
K(G)=K(D)+K(E)=1+2=3
K(F)=K(C)+K(E)+K(G)=1+2+3=6
K(H)=K(G)+K(F)=3+6=9
Ответ: 9

Задание 1. Сколько существует различных маршрутов от A до H?

Задание 2. На рисунке представлена схема дорог, связывающих населённые пункты A, B, C, D, E, F. В таблице содержатся сведения о стоимости проезда. На схеме информация об этих же дорогах. Отсутствие значения означает, что прямого рейса нет. Определить минимальную стоимость проезда из пункта E в пункт C.

Выясним степень каждой вершины – число ребер, соединяющих некоторую вершину с другими вершинами.

Степени вершин отметим на графе и в таблице.

Каждая из вершин со степенями 1, 3, 4 встречается один раз. Значит, можно установить взаимно-однозначное соответствие между ними.

По данным в таблице подпишем вес определенных ребер.

Найдем вершину A, ее от всех остальных отличает то, что вершина A является смежной вершиной для двух уже определенных вершин – D и C.

По таблице видно, что вершина C является смежной вершиной четырем вершинам – D, A, F и B1. Вес ребра CB – 6.

Осталась единственная неустановленная вершина – E. Вес ребра BE-10, а ребра DE-5.

Все способы передвижения от пункта E до пункта C можно рассмотреть на дереве решений. Минимальная стоимость при перемещении E-D-A-C.

4

1

3

2

2

2

4

2

3

1

2

2

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Геральт спешит выручить Цири из плена Кагыра. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Геральта до Цири (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.