Деревья. Лес. Бинарные деревья
Деревом называют конечный связный граф с выделенной вершиной (корнем), не имеющий циклов Вершины графа – дерева, называются узлами.
Для каждой пары вершин дерева – узлов- существует единственный маршрут, поэтому вершины удобно классифицировать по степени удаленности от корневой вершины. Расстояние до корневой вершины К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 - 2025 stydopedia.ru Все материалы защищены законодательством РФ.
|