Информатика -продвинутый курс
в ориентированном графе существует путь
Если в ориентированном графе существует путь из 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. Примеры деревьев
Анализ приведенных здесь понятий и определений показывает, что в качестве моделей графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов, между которыми существуют определенные связи, отношения, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в разделах: операционные системы, алгоритмизация, структуры данных, информационное моделирование и др.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий