Что такое взвешенный граф в информатике

Взвешенный граф в информатике: понятное объяснение и ключевые свойства

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

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

Применяемая в теории информатики терминология:

• Вершина — название узла или объекта, являющегося составным элементом схемы.
• Ребро — линия, концы которой объединяют две вершины между собой. Может задавать направление или быть ненаправленной.
• Ориентированный граф — схема, в которой каждое ребро является направленным.
• Степень или порядок вершины — количество ребер, выходящих из данной точки.
• Путь — последовательный маршрут ребер, объединяющих точки графа.
• Цикл — путь, начало и конец которого приходятся на одну и ту же вершину.
• Дерево — граф, не имеющий ни одного цикла.

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

Вес ребра в графе

Весом ребра принято называть натуральное значение показателя длины линии графа.

Представление взвешенного графа

Визуализация взвешенного графа может быть представлена несколькими методами:

• Матрица смежности. Показатель веса ребра может быть интегрирован в матрицу, а при его отсутствии можно задать специальное значение.
• Списки смежности. Позволяет хранить набор из двух элементов — номера точки и реберной длины, при этом проверить сложно будет проверить наличие ребер между двумя точками.
• Отдельный массив. Объединяет в себе номера двух вершин — начальной и конечной, где результатом является длина ребра между ними.

Представление графов применяется для визуализации взаимосвязей, объединяющих между собой элементы модели объекта.

Матрица смежности и список смежности

Матрица представляет собой наглядную таблицу, где в каждой строке и столбце представлены вершины. Список отличается более сдержанным содержанием. Применяется для графов с небольшим числом ребер.

Список ребер

Перечень всех линий на графе называется списком. У каждого ребра есть начальная и конечная точки. Наглядно список можно представить таблицей с двумя столбцами. Помимо самого перечня необходимо указать все обособленные вершины.

Взвешенные деревья

Дерево называют взвешенным, когда каждое его ребро и каждая вершина имеет вес размером в натуральное число. При этом вес каждой из вершин будет равен совокупному весу выходящих из нее ребер.

Пути и маршруты

Путь — это последовательность точек графа, соединенных ребрами. Маршрутом называется последовательность вершин и ребер. Начало и конец маршрута представлены вершинами.

Что такое алгоритм Крускала

Это определенная методика формирования взвешенного дерева графа. Способ основан на первичной визуализации пустых ребер с последующим добавлением новых без образования цикла. Алгоритм считается оконченным, когда таких ребер не остается.

Примеры применения взвешенных графов

Ситуации, при которых взвешенные графы находят применение:

• построение транспортной сети;
• схематичное изображение времени движения поездов;
• формирование модели инженерной сети.

Наглядное изображение схемы посредством взвешенных графов позволяет эффективно решать задачи экономического и управленческого характера.

Транспортная логистика

Предполагает графическое изображение путей движения транспорта, оптимизации маршрутов перевозки, организации логистических аспектов. При этом вес ребер может определять, как временные значения, так и показатели расстояния между объектами логистики.

Социальные сети

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

• коммуникационные социальные сети для общения в интернете;
• тематическое онлайн-сообщество группы людей.

Анализ схемы позволяет изучать процессы взаимодействия между объектами-участниками социальной сети.

Финансовая аналитика

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