Вся теория графов для ЕГЭ
Основы теории графов
Граф — это математическая модель, состоящая из вершин и соединяющих их рёбер. С помощью графов удобно изображать различные системы связей: дороги между городами, маршруты транспорта, компьютерные сети, связи между людьми и т. д.
Вершины графа обычно обозначают буквами или числами. Если две вершины соединены ребром, их называют смежными.
Неориентированный граф
В неориентированном графе рёбра не имеют направления. Если вершины A и B соединены ребром, то по нему можно двигаться как из A в B, так и из B в A.
Например, таким графом можно представить сеть двусторонних дорог между городами.
Ориентированный граф
В ориентированном графе каждое ребро имеет направление, которое обозначается стрелкой. Такое направленное ребро также называют дугой.
Если существует дуга A→B, это означает, что движение разрешено из вершины A в вершину B, но обратное направление не обязательно существует.
Например, таким графом можно представить систему дорог с односторонним движением.
Смешанный граф
Смешанный граф содержит одновременно ориентированные и неориентированные рёбра. Часть связей в таком графе имеет направление, а часть — нет.
Например, в дорожной сети могут одновременно встречаться односторонние и двусторонние дороги.
Связный граф
Связным называют граф, в котором из любой вершины можно добраться до любой другой вершины, переходя по рёбрам.
Если в графе существуют отдельные группы вершин, между которыми нет пути, такой граф называют несвязным.
Взвешенный граф
Во взвешенном графе каждому ребру ставится в соответствие некоторое число — вес ребра.
Вес может обозначать, например, длину дороги, время движения, стоимость поездки или пропускную способность канала связи.
Представление графа в памяти компьютера
Граф удобно изображать рисунком, но при решении задач на компьютере одного рисунка недостаточно. Возникает вопрос: как сохранить граф в памяти компьютера? Для этого граф обычно записывают в виде матрицы — специальной таблицы чисел.
Матрица смежности
Самый простой способ записи графа — матрица смежности.
Если в графе n вершин, то строится квадратная таблица n×n.
Строки и столбцы этой таблицы соответствуют вершинам графа.
В ячейке на пересечении строки i и столбца j записывают:
1, если вершины i и j соединены ребром;
0, если ребра между ними нет.
Таким образом, матрица смежности показывает, какие вершины связаны друг с другом.
Для неориентированного графа матрица смежности обычно симметрична относительно главной диагонали, потому что если вершина i соединена с вершиной j, то и вершина j соединена с вершиной i.
Для ориентированного графа в ячейке (i, j) записывают 1, если существует дуга из вершины i в вершину j. В этом случае матрица уже может быть несимметричной.
На главной диагонали обычно стоят нули, так как вершину обычно не соединяют саму с собой.
Весовая матрица
Если граф взвешенный, то важно знать не только сам факт связи между вершинами, но и вес ребра: длину, стоимость, время, расстояние и т. д.
Тогда используют весовую матрицу.
Она строится так же: строки и столбцы соответствуют вершинам графа. Но теперь в ячейке (i, j) записывают:
вес ребра, если вершины i и j соединены;
0 (или иногда специальное обозначение), если ребра между ними нет.
То есть весовая матрица хранит уже не просто информацию о наличии связи, а её числовую характеристику.
Для неориентированного взвешенного графа весовая матрица тоже обычно симметрична, так как вес ребра между вершинами ii и jj одинаков в обоих направлениях.
Зачем это нужно
Такое представление графа очень удобно для компьютера. По матрице можно:
быстро определить, есть ли ребро между двумя вершинами;
узнать вес этого ребра;
восстанавливать сам граф;
решать задачи на поиск путей, расстояний и связности.
Именно поэтому в информатике графы часто задают не рисунком, а матрицей смежности или весовой матрицей.