Уроки 31 - 34
§1.10. Графы и их исследование с использованием языков объектно-ориентированного программирования Visual Basic и Turbo Delphi

Содержание урока

1.10.1. Введение в теорию графов

Основные понятия теории графов

Маршрут графа

Ориентированные графы

Взвешенные графы

Описание графа с помощью матрицы смежности

Подграфы и деревья

Преобразование графа в основное связное дерево минимального веса

Контрольные вопросы

1.10.2. Изучение графов на языке Visual Basic

1.10.3. Изучение графов на языке Turbo Delphi

1.10.1. Введение в теорию графов

Маршрут графа

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

Маршрут является замкнутым (циклом), если его начальная и конечная вершины совпадают. Например, в графе G можно выделить несколько циклических маршрутов, например V₄R₁₂V₂R₂₃V₃R₃₄V₄R₁₄V₁ и V₂R₂₃V₃R₃₅V₅R₂₅V₂.

Маршрут называется простой цепью, если все его вершины и ребра различны.

Длина маршрута равна количеству ребер, входящих в него.

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

Например, маршрут между вершинами V₁ и V₄ может быть следующим: V₁R₁₂V₂R₂₃V₃R₃₄V₄.

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

Следующая страница Ориентированные графы

Cкачать материалы урока