Графы и таблица смежности
Граф — это вершины и рёбра между ними, а таблица смежности описывает тот же граф строками и столбцами. В задании 1 номера вершин в таблице не связаны с буквами на рисунке: соответствие находят по степеням вершин и по степеням их соседей. Длину дороги читают на пересечении строки и столбца, а кратчайший путь ищут, улучшая расстояния от начальной вершины.
Как сопоставить граф и таблицу
Граф на рисунке и таблица описывают одни и те же дороги, но буквы на рисунке и номера в таблице не связаны.
- Посчитайте степень каждой вершины графа: сколько рёбер из неё выходит.
- Посчитайте степень каждого пункта таблицы: сколько заполненных клеток в его строке.
- Вершина с единственной в графе степенью соответствует пункту с той же степенью.
- Вершины с одинаковой степенью различайте по степеням их соседей.
- Длина дороги стоит на пересечении строки и столбца двух найденных номеров.
- Две симметричные вершины различить нельзя: их номера пишут в ответе по возрастанию.
Граф, рёбра и степень вершины
Граф — набор вершин и рёбер. Вершина — точка, например населённый пункт. Ребро — линия между двумя вершинами, например дорога. Если у рёбер есть направление (стрелка), граф ориентированный, а его рёбра называют дугами. Если каждому ребру приписано число (длина, цена, время), граф взвешенный, а число называют весом ребра. Граф связный, если из любой вершины можно дойти до любой другой. Связный граф без циклов называют деревом.
Степень вершины — число рёбер, которые из неё выходят. Каждое ребро соединяет две вершины, поэтому сумма степеней всех вершин в два раза больше числа рёбер.
Пример
Схема дорог показана на рисунке. Найдите степень каждой вершины и число дорог.
- 1.Из А выходят рёбра к Б и В: степень 2. Из Е — к Г и Д: степень 2.
- 2.Из Б — к А, В и Г: степень 3. Из Д — к В, Г и Е: степень 3.
- 3.Из В — к А, Б, Г и Д: степень 4. Из Г — к Б, В, Д и Е: степень 4.
- 4.Сумма степеней , число рёбер .
Ответ: степени А, Е — 2; Б, Д — 3; В, Г — 4; дорог 9
Таблица смежности и весовая матрица
Таблица смежности (матрица смежности) — квадратная таблица, у которой строки и столбцы подписаны вершинами. Клетка на пересечении строки П2 и столбца П5 заполнена, если между П2 и П5 есть ребро: в ней стоит звёздочка или 1. Если вместо звёздочки записан вес ребра, таблицу называют весовой матрицей. Пустая клетка значит, что ребра нет.
В неориентированном графе дорога П2–П5 — это и клетка П2–П5, и клетка П5–П2, поэтому таблица симметрична относительно главной диагонали. Число заполненных клеток в строке равно степени вершины. Список смежности — та же информация короче: для каждой вершины перечислены её соседи, например «П2: П4, П6».
Пример
В весовой матрице в строке П3 заполнены три клетки: в столбце П1 стоит 7, в столбце П4 — 12, в столбце П6 — 4. Какова степень П3? Что стоит в строке П6 в столбце П3? Есть ли дорога П3–П5?
- 1.В строке П3 три заполненные клетки, степень П3 равна 3.
- 2.Таблица симметрична: в клетке П6–П3 стоит тот же вес, что в клетке П3–П6, то есть 4.
- 3.Клетка П3–П5 пуста, дороги между П3 и П5 нет.
Ответ: степень 3; в клетке П6–П3 число 4; дороги П3–П5 нет
Сопоставление графа и таблицы по степеням
В задании 1 граф нарисован с буквами, а таблица подписана номерами П1, П2, … . Номера и буквы не связаны: П1 не обязательно А. Связь между ними задают сами дороги, поэтому соответствующие вершины имеют одинаковые степени.
Выпишите степени вершин графа и степени пунктов таблицы. Если степень встречается в графе только у одной вершины, ей соответствует единственный пункт таблицы с такой же степенью.
Пример
Дороги заданы таблицей, записанной как список смежности: П1: П3, П5; П2: П4; П3: П1, П5; П4: П2, П5; П5: П1, П3, П4. Граф тех же дорог показан на рисунке. Какие номера у пунктов Б и Д? Запишите их в порядке Б, Д.
- 1.Степени в графе: А — 2, Б — 3, В — 2, Г — 2, Д — 1.
- 2.Степени в таблице: П1 — 2, П2 — 1, П3 — 2, П4 — 2, П5 — 3.
- 3.Степень 3 одна: Б — это П5. Степень 1 одна: Д — это П2.
- 4.Проверка: П2 соединён с П4, П4 — с П5. На рисунке Д соединён с Г, Г — с Б. Связи совпадают.
Ответ:
Симметричные вершины
Иногда две вершины имеют одинаковые степени и одинаковых по степени соседей. Например, они соединены друг с другом, а остальными концами — с вершинами одной степени. Такие вершины симметричны: если поменять их местами, граф не изменится. По таблице их различить нельзя, поэтому в задании спрашивают сразу о двух таких вершинах, а номера записывают в порядке возрастания.
Пример задания
Открытый банк ФИПИ
На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
|---|---|---|---|---|---|---|---|
| П1 | * | * | |||||
| П2 | * | * | * | ||||
| П3 | * | * | * | * | |||
| П4 | * | * | |||||
| П5 | * | * | * | ||||
| П6 | * | * | * | ||||
| П7 | * | * | * |
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам A и D на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Степени соседей и длина дороги
Если у нескольких вершин одинаковая степень, посмотрите на их соседей. Выпишите для каждой такой вершины степени соседей, в графе и в таблице. Вершина, у которой набор степеней соседей другой, находится однозначно.
Когда обе вершины дороги найдены, её длину читают в весовой матрице: строка одного номера, столбец другого. Если спрашивают сумму длин двух дорог, найдите номера всех четырёх концов и сложите два числа из таблицы.
Пример задания
Открытый банк ФИПИ
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
|---|---|---|---|---|---|---|---|
| П1 | 9 | 7 | |||||
| П2 | 5 | 11 | |||||
| П3 | 12 | ||||||
| П4 | 9 | 5 | 4 | 13 | 15 | ||
| П5 | 4 | 10 | 8 | ||||
| П6 | 11 | 12 | 13 | 10 | |||
| П7 | 7 | 15 | 8 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число — так, как оно указано в таблице.
Кратчайший путь во взвешенном графе
Длина пути — сумма весов его рёбер. Кратчайший путь ищут алгоритмом Дейкстры. Начальной вершине пишут расстояние 0, остальным — «бесконечность». Берут вершину с наименьшим расстоянием, которую ещё не закрыли, и закрывают её: её расстояние окончательное. Для каждого её соседа сравнивают текущее расстояние соседа и сумму «расстояние вершины + вес ребра». Меньшее число становится новым расстоянием соседа. Шаги повторяют, пока не закроют нужную вершину.
Прямая дорога не обязательно самая короткая: путь через несколько пунктов может быть короче. Поэтому сравнивают все варианты, а не идут по самым коротким рёбрам подряд.
Пример
Длины дорог (в км) показаны на рисунке. Найдите длину кратчайшего пути из А в Е.
- 1.Закрываем А (0). Соседи: Б — 4, В — 2.
- 2.Закрываем В (2). Б: , это меньше 4, ставим 3. Г: . Д: .
- 3.Закрываем Б (3). Г: , это меньше 10, ставим 8.
- 4.Закрываем Г (8). Д: , это меньше 12, ставим 10. Е: .
- 5.Закрываем Д (10). Е: , это меньше 14, ставим 13. Путь А, В, Б, Г, Д, Е.
Ответ: км
Минимальное остовное дерево
Остовное дерево связного графа — дерево, которое проходит через все его вершины и состоит из рёбер графа. В дереве с вершинами ровно рёбер. Минимальное остовное дерево — остовное дерево с наименьшей суммой весов: например, самая дешёвая сеть дорог, которая связывает все пункты.
Его строит алгоритм Краскала. Упорядочьте рёбра по возрастанию веса. Берите рёбра по очереди и добавляйте ребро, если оно не замыкает цикл с уже взятыми рёбрами. Остановитесь, когда взято рёбер.
Пример
Дороги между шестью пунктами: А–Б 4, А–В 2, Б–В 1, Б–Г 5, В–Г 8, В–Д 10, Г–Д 2, Г–Е 6, Д–Е 3. Какие дороги надо оставить, чтобы все пункты были связаны, а сумма длин была наименьшей?
- 1.Рёбра по возрастанию: Б–В 1, А–В 2, Г–Д 2, Д–Е 3, А–Б 4, Б–Г 5, Г–Е 6, В–Г 8, В–Д 10.
- 2.Берём Б–В, А–В, Г–Д, Д–Е: циклов нет.
- 3.А–Б замыкает цикл А, Б, В: пропускаем.
- 4.Б–Г связывает группу А, Б, В с группой Г, Д, Е. Взято 5 рёбер для 6 вершин, дерево готово.
- 5.Сумма: .
Ответ: Б–В, А–В, Г–Д, Д–Е, Б–Г; сумма