Графы и таблицы связей
Вершины, рёбра, степень и таблица смежности: какие свойства сохраняются при переименовании и почему соответствие бывает неоднозначным.
Для описания сети дорог нужны сами пункты и сведения о том, какие из них соединены. Точное положение на карте при этом может быть несущественно. Граф сохраняет объекты и связи между ними; таблица позволяет записать те же связи по строкам и столбцам. Два изображения могут выглядеть по-разному и при этом описывать одну систему.
Вершины и рёбра
Граф состоит из вершин и рёбер. Вершина представляет объект, ребро соединяет пару объектов. В дорожной схеме вершина обозначает пункт, а ребро обозначает дорогу без промежуточных пунктов. Вершины, соединённые одним ребром, называются соседними.
В дальнейшем рассматривается простой неориентированный граф. В дорожной модели это означает, что дороги двусторонние, нет дорог из пункта в него же, а между двумя пунктами проходит не больше одной прямой дороги. Поэтому степень вершины равна числу её соседей, а таблица читается одинаково в обоих направлениях.
На схеме шесть вершин и шесть рёбер. A и B соседние, A и E нет. Из A можно попасть в E через B, однако такой переход использует два ребра: AB и BE. Путь A-B-E существует, а ребра AE в графе нет.
Форма рисунка и вес ребра
Перемещение вершин, изгиб или растяжение линий не меняют граф, пока сохраняются пары соединённых вершин. Поэтому расстояние между точками на рисунке не определяет длину дороги. Если на линии обозначен промежуточный пункт, она состоит из двух рёбер; простое пересечение линий без обозначенного пункта новой вершины не добавляет.
Число, приписанное ребру, называется весом. Оно может обозначать длину дороги, время или стоимость проезда. Например, вес AB = 7 означает длину 7 км только при соответствующем указании в условии. Если AB = 7 км, а BE = 8 км, длина пути A-B-E равна 15 км. Это сумма весов двух рёбер.
Таблица смежности
Одна строка и один столбец отводятся каждой вершине. Ячейка на их пересечении описывает прямую связь выбранной пары. Такая квадратная таблица называется матрицей смежности. Для записи только наличия связей удобно использовать 1 и 0.
| Вершина | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 0 | 0 | 0 |
| D | 1 | 0 | 0 | 0 | 0 | 0 |
| E | 0 | 1 | 0 | 0 | 0 | 1 |
| F | 0 | 0 | 0 | 0 | 1 | 0 |
Единицы в строке A стоят под B, C и D: это соседи A. В ячейке A-E стоит 0, хотя путь через B существует. Таблица отражает именно непосредственные связи.
Ячейки A-B и B-A совпадают, поскольку дорога двусторонняя. Поэтому таблица симметрична относительно главной диагонали. На самой диагонали нули: рёбер из вершины в неё саму в простом графе нет.
В заданиях наличие дороги также обозначается звёздочкой, а вместо единицы может быть записана длина. Таблица с длинами хранит и связи, и веса. Смысл пустой ячейки, нуля или прочерка задаёт условие; переносить обозначения из одного задания в другое без проверки нельзя.
Степень вершины
Степень вершины равна числу соединённых с ней рёбер. В простом графе это также число соседей. У A соседи B, C, D, поэтому её степень равна 3. У D один сосед A, поэтому степень D равна 1. В таблице с длинами подсчитываются ячейки, обозначающие дороги, а не сумма чисел в них.
Каждое ребро имеет два конца. При сложении степеней оно учитывается дважды, по одному разу у каждого конца:
Сумма степеней вершин = 2 × число рёбер.
Для приведённого графа: 3 + 3 + 2 + 1 + 2 + 1 = 12. Значит, рёбер 12 / 2 = 6. Равенство помогает обнаружить пропущенную или дважды посчитанную связь.
Соответствие между двумя описаниями
При замене букв номерами меняются обозначения, но сохраняются все связи и их отсутствие. Каждой букве сопоставляется один номер, и каждый номер используется один раз. Графы, для которых существует такое соответствие, называются изоморфными.
Степень вершины при переименовании сохраняется. Однако одинаковая степень не делает две вершины неразличимыми. В примере у A и B по три соседа, но у A есть сосед D степени 1, а у B такого соседа нет. Это позволяет различить A и B.
Если совпадают и степени соседей, могут различаться связи между ними или более длинные цепочки. Отдельный совпавший признак только оставляет вариант возможным; окончательное соответствие должно сохранять все связи. В разборе №1 показано сравнение по соседям и треугольникам.
Симметрия и неоднозначность
Иногда перестановка вершин действительно сохраняет весь граф. Например, к вершине K присоединены два тупика P и Q, у каждого из которых только одна дорога, к K. Обмен P и Q ничего не меняет в связях. Такая перестановка выражает симметрию графа, даже если рисунок внешне несимметричен.
Если этим тупикам соответствуют номера 2 и 5, структура не позволяет решить, какой из них P. Но пара номеров по возрастанию уже определена: 25. Сумма длин KP и KQ тоже не зависит от обмена, поскольку складываются те же две дороги.
Длина только KP может зависеть от выбранного соответствия. Если допустимые варианты дают разные результаты, данных недостаточно для однозначного ответа: нужно проверить схему и дополнительные сведения условия. Произвольный выбор одного варианта этого не исправляет.
Когда длины указаны только в таблице, сами по себе они не различают буквы на схеме. Для этого нужна связь с дополнительным условием, например указание, какая из двух дорог длиннее. Если такое условие дано, оно также участвует в сопоставлении.
Применение в заданиях
Как сопоставить граф и таблицу, если у нескольких вершин одинаковое число соседей? Всегда ли для ответа нужно восстанавливать всё соответствие?
Эти вопросы разобраны на примерах в статье «Задание №1. Сопоставление графа и таблицы».