Сделай Сам Свою Работу на 5

Деревья. Лес. Бинарные деревья





Деревом называют конечный связный граф с выделенной вер­шиной (корнем), не имеющий циклов Вершины графа – дерева, называются узлами.

Для каждой пары вершин дерева – узлов- существует един­ственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины. Расстояние до кор­невой вершины К0 называется ярусомs вершины, s= d(V0 V).

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

Каждая висячая вершина дерева называется его листом.

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

Теорема 7. Граф является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

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



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

граф G(V, X) связен и имеет п-1 ребро;

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

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

в графе G(V, X) всякая пара вершин соединена цепью, и только одной.

Дерево с п вершинами имеет п-1 ребро, поэтому оно будет минимальным связным графом.

Висячие вершины, за исключением корневой, называются листьями.

Лесом называется граф, полученный в результате упорядоченного объединения не пересекающихся деревьев. Так, если графы A,S.D.F – деревья, то граф G= A∪S∪D∪F есть лес

Компонентами связности леса являются деревья. Остовомсвязно­го графа G называется любой его подграф F, содержащий все вер­шины графа G и являющийся деревом (говорят: покрывающим его деревом»).

Если граф F есть остов леса G, то дополнения F’ до G является кодеревом.

Дерево может быть представлено расслоенным на ярусы (уров­ни), при этом ветвям, попавшим в один ярус, соответствует оди­наковая длина пути исходного графа. Число путей в каждом дере­ве соответствует числу висячих вершин (листьев).



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

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

Очевидно, что узел без поддеревьев называется листом и является висячей вер­шиной.

Узел k-го яруса называется отцомузла (k+ 1)-го яруса, если они смежные.

Узел (k+ 1)-го яруса называется сыномузла k-ro яруса.

Два узла, имеющие одного отца, называются братьями.

Вполне очевидно, что отца можно назвать предком, а сыновей – потомками.

Упорядоченным деревомназывается дерево, в котором поддере­вья каждого узла образуют упоря­доченное подмножество.

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

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

Например для бинарного дерева можно указать, что отец A, сыновья В и С, при­чем В – левый, а С – правый потомки ( по алфавиту и запись слева направо по строчке (ярусу дерева)

Строго бинарным деревом называется такой граф, у которого каждый узел, не являющийся листом, содержит два и только два поддерева – ле­вое и правое.



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

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

Примером бинарных деревьев может служить турнирная таблица спортивных игр, например волейбол, шахматы и др.Что бы быть победителем, надо выиграть в финале, где встречаются две команды, которые победили в полуфинале, а перед этим победили в четверть финале и т.д. К таким относится также олимпийская система соревнований

Цикломатическим числомграфа называется число v = m + c – n, где:

m – количество ребер;

c - количество связных компонент графа;

п – количество вершин.

Цикломатическое число дерева равно нулю. Цикломатическое число леса равно сумме цикломатических чисел составных связных компонент – деревьев и, следовательно, тоже равно нулю. Для остальных гра­фов цикломатические числа – положительные.

Например, для полного графа, имеющего пять вершин и 10 ребер цикломатическое число равно v = 10 + 1 – 5 = 6.

4. Способы задания графа. Изоморфные графы

Графы могут задаваться следующими способами:

1. Геометрическим способом – рисунки, схемы, диаграммы,

2. Алгебраическим способом – перечислением вершин и ребер,

3. Табличным способом.

4. Матричным способом.

Человеку удобно работать с графом-рисунком, так как он может легко установить связь между вершинами в на­глядном виде с помощью ребер, изображаемых непрерывными линиями. Такое геометрическое представление плоского графа на­зывается его реализацией.

Для машинной обработки удобнее за­дать граф в алгебраической форме – перечислением (списком) вершин или ребер.

При переходе от алгебраического способа к геометриче­скому одному и тому же графу могут соответствовать различные изображения – изоморфные графы,при этом от правильного изоб­ражения зависит, например, свойство плоской реализуемости. Для этого нужно правильно задать сам граф.

Основным способом задания графа является перечисление всех его вершин и ребер. Но такое представление, во-первых, несим­метрично (с ним трудно работать, особенно ЭВМ), во-вторых, для указания каждого ребра нужно еще раз выписывать соответ­ствующие вершины, что плохо с точки зрения сжатия и хранения информации.

При задании графа таблицейсоставляется таблица,состоящей из п строк (вершины) и т столбцов (ребра). На пересечении строк и столбцов пишутся соответствующие знаки, которые показывают отношение (инцидентность) вершины и ребра. Это может быть знаки “+” и “-”, числа 0,1,-1 и др.

Главным во всех способах задания графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами п вершин Vt к т ребер X-t.

Пусть дан граф G(V, X),где V= {V1, V2 …Vn}вершины, а Х= {Х1, Х2 .,., Хm}ребра, среди которых могут и кратные ребра (есть вершины, которые соединяет несколько ребер).

Матрицей инцидентностиданного графа будет таблица, состоящая из n строк (вершины) и т столбцов (ребра).

При рассмотрении неориентированного графа на пересечении строк и столбцов ставится число 1, если соответствующие вершина и ребро инцидентны и ставится число 0, они не инцидентны.

При рассмотрении ориентированного графа на пересечении строк и столбцов ставится число 1, если из вершины выходит соответствующее ее ребро. Если в вершину входит ребро, то ставят число -1. Если вершина не инцидентна ребру и, то ставится число 0

Очевидно, что в каждом столбце матрицы инцидентности долж­но быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки – сте­пень соответствующей вершины.

Матрицы инцидентности прямоугольные, если число строк и столбцов различно. Если число вершин и ребер в графе одинаковое, то получается квадратная матрица.

Матрицу можно сделать квадратной для любого графа без кратных ребер. В таких случаях строки и столбцы изображают вершины. На пересечении строк и столбцов ставится число 1, если соответствующие вершины соединены ребром и ставится число 0, если вершины не соединены.

Для неориентированного графа ребраодновременно принадлежат или не принадлежат графу, так как символизируют одно и то же ребро. Матрица смеж­ности неориентированного графа является симметрической и не меняется при транспонировании.

Хотя формально каждая вершина всегда смежная сама с собой, в матрице смежности мы будем ставить 0, если у нее нет петли, и 1, если есть одна петля.

Если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули.

ЗаданиеСоставить таблицу и матрицу инцидентности для орграфа, изображенного на рисунке, который имеет 3вершины и 4 ребра.

Ответ.

Практические задания

1. Решите задачи «о переправах», изобразите решение гра­фом.

1. Три генерала – Строгий, Лихой и Грозный – со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо пе­реправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку?

2. Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух чело­век. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали, чтобы ни на одном берегу не остава­лось больше женщин, чем мужчин. Как им переправиться через реку?

3. Муж, жена и двое детей должны переправиться на противо­положный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети – по 50. Как им быть, если лодка вмещает до 100 кг и каждый из них умеет грести?

4. Человеку необходимо было переправить через реку с помо­щью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оста­вить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то она съест капусту, а в присутствии человека никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал?

2. Задачи на поиск «фальшивой монеты» решите с помощью графов.

1. Из 9 монет одна фальшивая (более легкая). Как двумя взве­шиваниями на чашечных весах определить фальшивую монету?

2. Из 80 одинаковых по виду монет одна более легкая (фальши­вая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую?

3. Из 28 монет одна более легкая. Как при помощи 4 взвешива­ний определить ее?

4. Из 27 монет одна более легкая. Как при помощи 3 взвешива­ний определить ее?

5. Из 81 монеты одна более легкая. Показать, что 4 взвешива­ний достаточно, чтобы ее определить.

6. Из 82 монет одна более легкая. Какое наименьшее число взве­шиваний необходимо для определения этой монеты?

7. Из т одинаковых по виду монет одна фальшивая (более лег­кая). Указать наименьшее число взвешиваний, необходимых для определения фальшивой монеты.

Требования к знаниям умениям и навыкам.

Студенты должны знать определение графа. Уметь строить графы отношений. Понимать применимость графов для решения определенных задач.

 

© GOU SPO.

 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.