Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Графы и деревья


Нелинейные структуры данных

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

Граф – нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладающая следующими свойствами:

– на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

– каждый элемент может иметь связь с любым количеством других элементов;

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

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

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

Граф, все связи которого ориентированные, называется ориентированным или орграфом. Граф со всеми неориентированными связями называется неориентированным, а граф со связями обоих типов – смешанным графом. Обозначение связей: неориентированных – (A,B), ориентированных – <A,B>. Примеры изображений графов приведены на рис. 7.1. Скобочное представление имеет вид: а). ((A,B),(B,A)) и б). (< A,B >,< B,A >).

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



 

       
 
   

 


а). б).

 

Рис. 7.1. Граф неориентированный (а) и ориентированный (б).

 

 

Путь в графе – последовательность узлов, связанных ребрами. Элементарным называется путь, в котором все ребра различны, простым называется путь, в котором все вершины различны. Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом, а граф, содержащий такие пути – циклическим. Граф, в котором отсутствуют циклы, называется ациклическим. Два узла графа являются смежными, если существует путь от одного из них до другого. Узел называется инцидентным к ребру, если он является его вершиной, т.е. ребро направлено к узлу.

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

Существует несколько способов графического изображения деревьев (рис. 7.1).

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

 

 

       
   
 
 

 


а). б).

 

       
   
 
 

 

 


в). г).

 

Рис. 7.2. Представление дерева: а) исходное дерево,

б) оглавление книг, в) граф, г) диаграмма Венна.

<== предыдущая лекция | следующая лекция ==>
Управление динамически выделяемой памятью. Язык программирования LISP | Машинное представление графов

Дата добавления: 2014-01-07; Просмотров: 533; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.