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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для наглядного представления графа используются схемы (см. рис. 1.58), а для математических расчетов удобнее использовать представление графа в форме матрицы смежности (рис. 1.59, а). Матрицу смежности можно представить в виде таблицы, строки и столбцы которой соответствуют номерам вершин графа. Если вершины смежные, то элемент матрицы смежности равен 1, если вершины не смежные, то элемент матрицы равен 0. Диагональные элементы матрицы равны 0, так как вершины сами с собой не смежные (их не соединяет ребро).

Пусть в матрице смежности графа G строки нумеруются индексом n, а столбцы — индексом k, тогда элементы матрицы смежности обозначаются R_nk. Для смежных вершин элементы матрицы смежности (R₁₂, R₁₄, R₁₅, R₂₁, R₂₃, R₂₅, R₃₂, R₃₄, R₃₅, R₄₁, R₄₃, R₄₅, R₅₁, R₅₂, R₅₃, R₅₄) равны 1, а для не смежных вершин элементы матрицы (R₁₃, R₂₄, R₃₁, R₄₂) равны 0. Диагональные элементы матрицы (R₁₁, R₂₂, R₃₃, R₄₄, R₅₅) равны 0.

Преобразуем граф G в сеть, т. е. присвоим ребрам, соединяющим смежные вершины, числовые значения (R₁₂ = 50, R₁₄ = 25, R₁₅ = 10, R₂₁ = 50, R₂₃ = 25, R₂₅ = 30, R₃₂ = 25, R₃₄ = 50, R₃₅ = 35, R₄₁ = 25, R₄₃ = 50, R₄₅ = 15, R₅₁ = 10, R₅₂ = 30, R₅₃ = 35, R₅₄ = 15). Отобразим сеть G в форме матрицы смежности (рис. 1.59, б).

Рис. 1.59. Граф и сеть G в форме матрицы смежности

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

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