bigpo.ru
добавить свой файл
1
n=Это конечный связный граф с выделенной вершиной~sz=111986;pg=1;te=Дерево и названо дерево, поскольку, будучи нарисованным, выглядит как дерево, только перевёрнутое «вверх ногами». Граф, изображённый на рисунке 1 является примером дерева">ерево и названо дерево, поскольку, будучи нарисованным, выглядит как дерево, только перевёрнутое «вверх ногами». Граф, изображённый на рисунке 1 является примером дерева.





Рис. 1

Граф на рисунке 2 не является деревом, поскольку содержит цикл.


Рис. 2

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

^ Для каждой пары вершин дерева узлов – существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины. Расстояние до корневой вершины называется ярусом s вершины,

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

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

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

граф связан и не содержит циклов;

граф не содержит циклов и имеет ребро;

граф связен и имеет ребро;

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

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

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

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


Лес – это граф, компоненты которого являются деревьями.

Граф на рисунке 3 – это лес.


Рис. 3

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

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

Каждая вершина дерева называется узлом, причём каждый узел является корнем дерева, имеющего n поддеревьев (). Тогда узел без поддеревьев называется листом и является висячей вершиной. ^ Рис. 4


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

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

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

^ Бинарное дерево уровня n называется полным, если каждый его узел уровня n является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья. Примером полного бинарного дерева служит таблица розыгрыша соревнования по олимпийской системе («плей-офф»). На рисунке 6 приведена таблица розыгрыша Кубка мира по футболу (корень Бразилия).




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


Цикломатическое число графа.

Пусть задан неориентированный граф G.

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

^ Например, для полного графа К5 (имеющего пять вершин и 10 рёбер) цикломатическое число равно


Сети. Сетевые модели представления информации


Граф называется взвешенным или сетью, если каждому его ребру поставлено в соответствие некоторое число (вес). Взвешенными графами могут быть схемы в электронике, электрические схемы, карты автомобильных и железных дорог и др. Например, на картах автодорог вершины являются населенными пунктами, ребра — дорогами, а весом — числа, равные расстоянию между населенными пунктами.

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

^ Например, последовательность работ для монтажа каркаса здания изображена в виде графа (рис. 1).

Числами обозначены технологические операции:

1 — рытье котлована;

2 — монтаж фундамента;

3 — завоз металлоконструкций;

4 — монтаж подъемного крана;

5 — монтаж каркаса здания.




Рис. 1


^ На рис. 2. изображен сетевой граф некоторого комплекса работ в виде взвешенного графа с указанием времени, затраченного на выполнение этой работы (в минутах).





Рис. 2

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

Сети широко используются в качестве моделей для представления знаний в интеллектуальных системах. Сетевая модель представления информации основана на том, что любые знания можно рассматривать как множества объектов (понятий) и связи между ними (отношения).

Понятия-объекты и другие элементы предметной области могут быть графически изображены в виде вершин, а отношения между ними — в виде дуг, связывающих эти вершины. Такое графическое представление информации (знаний) в интеллектуальных системах носит название семантических сетей. Они являются универсальным средством для представления знаний в интеллектуальных системах. Понятия, входящие в сети, можно описать с помощью фрейма. Фреймом называется минимально возможное описание сущности некоторого явления, объекта, события или процесса. Состоит фрейм из набора стандартных единиц — слотов, содержащих определенный минимум информации о его содержании и назначении. Семантическая сеть в виде некоторой совокупности фреймов нуждается в указании отношения между ее вершинами, что тоже возможно осуществить в виде слота. Семантические сети широко применяются в информатике, например, для операций поиска по образцу, где в виде сетей представляется база данных. Результат такого поиска можно изобразить графом. Используются сети и для графической иллюстрации системы отношений базы данных.

^ Широко применяются сети для графического изображения различных логических схем в теории автоматов, например схемы с памятью, у которых каждый узел F(i) — функция алгебры логики.


Применение графов и сетей

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

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

Рассмотрим пример. Для классификации некоторого объекта . предприятие. (варианты его названия — ) выберем в качестве корня дерева сам объект (рис. 3). Компоненты, составляющие этот объект, разместим на первом уровне (ярусе) графа: это будут Второй уровень (ярус) графа содержит компоненты первого уровня (его подмножества: ). Аналогично на третьем уровне разместим подмножества компонентов второго уровня - От нижнего уровня к высшему ведёт лишь одна дуга, поэтому граф является деревом.




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

Структуру такого типа имеют, например, предприятия (его составные части: цехи, бригады, участки и т.д.), учебные заведения (колледж состоит из факультетов, которые, в свою очередь, состоят из курсов, курсы — из групп). Такой же зависимости подчинены армейские соединения (дивизия, полк, батальон, рота, взвод, отделение, отдельные солдаты). Аналогично устроена любая административно-территориальная структура: республика, области, районы, населенные пункты. По путям этих деревьев движутся информационные потоки: сверху вниз — распоряжения, руководящие указания, снизу вверх — отчеты о работе, оперативная информация. Так как путь от листа к корню единственный, то его можно использовать для опознания компонентов системы. Например, почтовый адрес представляет собой «путь в дереве», аналогичный административно-территориальному. В разделе «Кому» указывается страна, республика, область, район, населенный пункт, улица, дом, квартира. Аналогично классифицируют объекты в любой науке. Получаемая классификация служит примером иерархической структуры. Например, в биологии: класс, отряд, семейство, род, вид. Соответствующий граф содержит элементы разных уровней, корень — класс, а листья — отдельные виды животных.

Иногда связи между объектами образуют не дерево, но все же их можно представить в виде графа. Это бывает в тех случаях, когда, например, происходит подчинение не одному, а нескольким независимым службам (соподчинение между собой).

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

Бинарный поиск. Бинарные деревья применяются в информатике для одной из самых распространенных в прикладных науках операций — поиску. К нему прибегают, когда необходимо найти в некотором упорядоченном массиве (множестве) определенную информацию. Например, в телефонном справочнике — номер какого-нибудь абонента, в словаре — определенное слово, в файле — сведения о зарплате сотрудников некоторого предприятия, сведения о зарплате отдельного работника и т.д.

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

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

Пусть надо найти дубликаты всех чисел в некотором списке. Можно применить сравнение каждого числа с предшествующим на предмет «был — не был». Но тогда необходимо большое число сравнений. Использование бинарных деревьев (БД) укорачивает процедуру сравнения. Считывается новое число и помещается в узел — будущий корень нового БД. Каждое последующее число из списка сравнивается с числом в корне БД. Если эти значения совпадают, то дубликат найден, если число меньше корня, то процесс продолжается в правом поддереве, если больше — в левом поддереве.

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

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