ВУЗ:
Составители:
62
Рис. 5.8. Разделимые графы:
а – с точкой сочленения; б – с мостом; в – блоки В
1
– В
3
графа с мостом
Модель данных, имеющую вид ориентированного графа, называют се-
тью. Сеть, в которой между любой парой вершин имеется не более одного реб-
ра, называется простой сетью. Сеть, имеющая параллельные ребра, называется
сложной сетью.
Деревья. Нелинейные отношения между объектами типа «один ко мно-
гим» носят иерархический характер и отображаются
древовидными структура-
ми. Древовидные иерархические структуры широко используются в повседнев-
ной человеческой деятельности. Это всевозможные классификаторы, оглавле-
ния, функциональные структуры управления и т.п. Древовидные структуры ис-
пользуются для построения алгоритмов решения алгебраических выражений,
для создания справочников, для сортировки и поиска данных. Деревья играют
важную роль в различных прикладных задачах,
когда, например, речь идет о
связи каких-либо объектов минимальным числом каналов с определенными
свойствами. С помощью деревьев определяются системы координат при моде-
лировании цепей и систем различной физической природы. Деревья использу-
ются в качестве моделей при рассмотрении иерархических систем объектов,
структурных формул органических соединений и т.п.
Дерево представляет собой
частный случай графа с определенными ог-
раничениями, а именно – это связный ациклический граф. На множестве вер-
шин р дерево всегда содержит q = p – 1 ребер, то есть минимальное количество
ребер, необходимое для того, чтобы граф был связным. При добавлении в дере-
во хотя бы одного ребра образуется цикл, а при удалении
хотя бы одного ребра
дерево распадается на компоненты, каждая из которых представляет собой так-
же дерево или изолированную вершину.
Пусть множество V содержит p вершин, которые пронумерованы по-
рядковыми числами от 1 до р, т.е.
V = {1, 2, . . . , p}.
а б в
Страницы
- « первая
- ‹ предыдущая
- …
- 60
- 61
- 62
- 63
- 64
- …
- следующая ›
- последняя »
