Граф — это математическая структура, которая состоит из вершин (или узлов) и рёбер (или соединений) между ними. Графы являются важным инструментом в различных областях — от информатики и физики до социальных наук.
Матрица смежности
Один из способов представления графов —
матрица смежности. Это таблица, в которой строки и столбцы соответствуют вершинам графа. Если между двумя вершинами существует ребро, в соответствующей ячейке матрицы указывается
1 (или
да), если ребра нет —
0 (или
нет). Например, для графа с вершинами A, B и C, если между A и B есть ребро, а между A и C — нет, то матрица смежности будет выглядеть так:
| |
A |
B |
C |
| A |
0 |
1 |
0 |
| B |
1 |
0 |
1 |
| C |
0 |
1 |
0 |
Весовая матрица
В
весовой матрице к каждому ребру приписан вес — числовое значение, которое может означать, например, расстояние между городами или стоимость перевозки товаров. Это делает весовые матрицы особенно полезными в задачах оптимизации. Например, весовая матрица может выглядеть так:
| |
A |
B |
C |
| A |
0 |
5 |
∞ |
| B |
5 |
0 |
2 |
| C |
∞ |
2 |
0 |
Здесь ∞ означает, что между вершинами нет прямого соединения.
Степень вершины
Степень вершины — это количество рёбер, соединённых с данной вершиной.
Разные визуализации одного графа
Интересно, что один и тот же граф можно изображать по-разному. Например, можно нарисовать линии по-разному и разместить вершины на плоскости так, чтобы они не пересекались, или, наоборот, пересекались. При этом все визуализации будут представлять одну и ту же структуру, определяемую весовой или матрицей смежности.
На практике графы находят применение в различных областях, таких как транспортировка, компьютерные сети, социальные сети и многое другое. Понимание графов и их представление позволяет решать многие сложные задачи более эффективно и наглядно.