ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

а) 2 мл раствора хромата или бихромата калия подкислите разбавленной серной кислотой, добавьте 2 мл диэтилового эфира, и такой же объём 10% раствора пероксида водорода. Перемешайте смесь и дождитесь расслоения системы. Что находится в эфирном слое? в водном слое? Напишите уравнения реакций.

б) К подкисленным растворам молибдата и вольфрамата в отдельных пробирках прилейте по несколько капель 3%-ного раствора пероксида водорода. Как изменяется цвет растворов? Напишите уравнения реакций.

Построение генеалогического древа семьи

ЦЕЛЬ РАБОТЫ

13.1.1 Ознакомиться с теоретическими сведениями по бинарным деревьям.

13.1.2 Получить практические навыки по построению генеалогического древа семьи.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

13.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

13.3.1 Изучить методические указания к практической работе.

13.3.2 Постройте древо своей семьи.

СОДЕРЖАНИЕ ОТЧЕТА

13.4.1 Цель работы

13.4.2 Методические рекомендации

13.4.3 Порядок выполнения работы

13.4.4 Ответы на контрольные вопросы

13.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

13.5.1 Что такое дерево?

13.5.2 Дайте определение бинарному дереву?

13.5.3 Что такое дерево?

13.5.4 Дайте определение цикломатическому числу?

13.5.5 Что такое лист?

13.5.6 Что такое высота дерева?

13.5.7 Что такое ярус?

13.5.8 Что такое лес?

13.5.9 Что такое корень дерева?

13.5.10 Наиболее характерные свойства деревьев?

13.5.11 Что называется ветвью?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

 

Ориентированным деревом (ордеревом, или корневым деревом) называется орграф со следующими свойствами:

1. существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева;

2. полустепень захода всех остальных узлов равна 1;

3. каждый узел достижим из корня.

(ориентированные деревья)

Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла.

Поскольку маршрут между двумя вершинами единственный. То, применяя это свойство к смежным вершинам, можно заключить, что любая ветвь является мостом.

Действительно, при удалении ребра этот единственный маршрут прерывается. Тогда граф распадется на два подграфа. В одном из них остается корневая вершина, и этот граф тоже будет являться деревом. В другом графе выделим вершину, инцидентную удаленному мосту. Тогда второй подграф также будет являться деревом.

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

Граф G(v,x) (v=n>1) является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

v граф G(v,x) связен и не содержит циклов;

v граф G(v,x) не содержит циклов и имеет n-1 ребро;

v граф G(v,x) связен и имеет n-1 ребро;

v граф G(v,x) не содержит циклов, но добавление ребра между несмежными вершинами приводит к появлению одного и только одного простого цикла;

v граф G(v,x) связный, но утрачивает это свойство после удаления любого ребра;

v в графе G(v,x) всякая пара вершин соединена цепью и причем только одной

Итак, дерево с n вершинами имеет n-1 ребро, поэтому оно будет минимальным связным графом. Висячие вершины, за исключением корневой, называются листьями.

Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой.

При описании деревьев принято использовать термины: отец, сын, предок, потомок.

Каждая вершина дерева называется узлом, причем каждый узел является корнем дерева, имеющего n поддеревьев. Тогда узел без поддеревьев называется листом и является висячей вершиной. Узел к-го яруса называется отцом узла (к+1)-го яруса, если они смежны. Узел (к+1) ярус называется сыном узла к-го яруса. Два узла, имеющие одного отца, называются братьями.

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

В информатике принято использовать подмножество множества деревьев, когда каждый узел либо является листом, либо образует два поддерева: левое и правое. Такой вид деревьев называется бинарными деревьями и используется при делении множества на два взаимоисключающих подмножества по какому-то признаку. Для отца А – сыновья В и С, причем В – левый, а С – правый потомки. Строго бинарным деревом называется такой граф, у которого каждый узел, не являющийся листом, содержит два и только два поддерева – левое и правое.

Бинарное дерево уровня n называется полным, если каждый его узел уровня n является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья. Примером полного бинарного дерева служит таблица розыгрыша соревнования по олимпийской системе.

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