Информатика -продвинутый курс


   Гостиница Волхов 2        

ОСНОВНЫЕ ПОНЯТИЯ - часть 2


Если в ориентированном графе существует путь из vi в vj,

то говорят, что вершина vj достижима из вершины vi.

Две вершины vi

и vj называют связанными в графе G, если в нем существует путь, для которого эти вершины являются концевыми. Граф G

называется связным, если каждые две вершины в нем являются связанными. На рис. 1.7 изображен простой неориентированный связный граф.

Последовательность вершин v1, v5, i4, v3 , например, определяет путь, а последовательность вершин v1, v5,

i4, v3, vl, v1 - цикл. Деревом будем называть неориентированный связный граф без циклов. Лес - это любой граф без циклов. На рис. 1.8 показаны возможные деревья с пятью вершинами.

Рис. 1.7. Пример неориентированного связного графа

Рис. 1.8. Примеры деревьев

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




Содержание  Назад  Вперед