Задание 1
тема 1 из 1

Графы и таблица смежности

Граф — это вершины и рёбра между ними, а таблица смежности описывает тот же граф строками и столбцами. В задании 1 номера вершин в таблице не связаны с буквами на рисунке: соответствие находят по степеням вершин и по степеням их соседей. Длину дороги читают на пересечении строки и столбца, а кратчайший путь ищут, улучшая расстояния от начальной вершины.

Главная тема в задании1На карте навыков

Как сопоставить граф и таблицу

Граф на рисунке и таблица описывают одни и те же дороги, но буквы на рисунке и номера в таблице не связаны.

  • Посчитайте степень каждой вершины графа: сколько рёбер из неё выходит.
  • Посчитайте степень каждого пункта таблицы: сколько заполненных клеток в его строке.
  • Вершина с единственной в графе степенью соответствует пункту с той же степенью.
  • Вершины с одинаковой степенью различайте по степеням их соседей.
  • Длина дороги стоит на пересечении строки и столбца двух найденных номеров.
  • Две симметричные вершины различить нельзя: их номера пишут в ответе по возрастанию.

Граф, рёбра и степень вершины

Граф — набор вершин и рёбер. Вершина — точка, например населённый пункт. Ребро — линия между двумя вершинами, например дорога. Если у рёбер есть направление (стрелка), граф ориентированный, а его рёбра называют дугами. Если каждому ребру приписано число (длина, цена, время), граф взвешенный, а число называют весом ребра. Граф связный, если из любой вершины можно дойти до любой другой. Связный граф без циклов называют деревом.

Степень вершины — число рёбер, которые из неё выходят. Каждое ребро соединяет две вершины, поэтому сумма степеней всех вершин в два раза больше числа рёбер.

Пример

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

АБВГДЕ
Шесть пунктов и дороги между ними.
  1. 1.Из А выходят рёбра к Б и В: степень 2. Из Е — к Г и Д: степень 2.
  2. 2.Из Б — к А, В и Г: степень 3. Из Д — к В, Г и Е: степень 3.
  3. 3.Из В — к А, Б, Г и Д: степень 4. Из Г — к Б, В, Д и Е: степень 4.
  4. 4.Сумма степеней 2+3+4+4+3+2=182 + 3 + 4 + 4 + 3 + 2 = 18, число рёбер 18:2=918 : 2 = 9.

Ответ: степени А, Е — 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. 1.В строке П3 три заполненные клетки, степень П3 равна 3.
  2. 2.Таблица симметрична: в клетке П6–П3 стоит тот же вес, что в клетке П3–П6, то есть 4.
  3. 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. 1.Степени в графе: А — 2, Б — 3, В — 2, Г — 2, Д — 1.
  2. 2.Степени в таблице: П1 — 2, П2 — 1, П3 — 2, П4 — 2, П5 — 3.
  3. 3.Степень 3 одна: Б — это П5. Степень 1 одна: Д — это П2.
  4. 4.Проверка: П2 соединён с П4, П4 — с П5. На рисунке Д соединён с Г, Г — с Б. Связи совпадают.

Ответ: 5252

Симметричные вершины

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

Пример задания

Открытый банк ФИПИ

На рисунке схема дорог 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, остальным — «бесконечность». Берут вершину с наименьшим расстоянием, которую ещё не закрыли, и закрывают её: её расстояние окончательное. Для каждого её соседа сравнивают текущее расстояние соседа и сумму «расстояние вершины + вес ребра». Меньшее число становится новым расстоянием соседа. Шаги повторяют, пока не закроют нужную вершину.

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

Пример

Длины дорог (в км) показаны на рисунке. Найдите длину кратчайшего пути из А в Е.

4215810263АБВГДЕ
Возле каждого ребра записана длина дороги.
  1. 1.Закрываем А (0). Соседи: Б — 4, В — 2.
  2. 2.Закрываем В (2). Б: 2+1=32 + 1 = 3, это меньше 4, ставим 3. Г: 2+8=102 + 8 = 10. Д: 2+10=122 + 10 = 12.
  3. 3.Закрываем Б (3). Г: 3+5=83 + 5 = 8, это меньше 10, ставим 8.
  4. 4.Закрываем Г (8). Д: 8+2=108 + 2 = 10, это меньше 12, ставим 10. Е: 8+6=148 + 6 = 14.
  5. 5.Закрываем Д (10). Е: 10+3=1310 + 3 = 13, это меньше 14, ставим 13. Путь А, В, Б, Г, Д, Е.

Ответ: 1313 км

Минимальное остовное дерево

Остовное дерево связного графа — дерево, которое проходит через все его вершины и состоит из рёбер графа. В дереве с nn вершинами ровно n−1n - 1 рёбер. Минимальное остовное дерево — остовное дерево с наименьшей суммой весов: например, самая дешёвая сеть дорог, которая связывает все пункты.

Его строит алгоритм Краскала. Упорядочьте рёбра по возрастанию веса. Берите рёбра по очереди и добавляйте ребро, если оно не замыкает цикл с уже взятыми рёбрами. Остановитесь, когда взято n−1n - 1 рёбер.

Пример

Дороги между шестью пунктами: А–Б 4, А–В 2, Б–В 1, Б–Г 5, В–Г 8, В–Д 10, Г–Д 2, Г–Е 6, Д–Е 3. Какие дороги надо оставить, чтобы все пункты были связаны, а сумма длин была наименьшей?

  1. 1.Рёбра по возрастанию: Б–В 1, А–В 2, Г–Д 2, Д–Е 3, А–Б 4, Б–Г 5, Г–Е 6, В–Г 8, В–Д 10.
  2. 2.Берём Б–В, А–В, Г–Д, Д–Е: циклов нет.
  3. 3.А–Б замыкает цикл А, Б, В: пропускаем.
  4. 4.Б–Г связывает группу А, Б, В с группой Г, Д, Е. Взято 5 рёбер для 6 вершин, дерево готово.
  5. 5.Сумма: 1+2+2+3+5=131 + 2 + 2 + 3 + 5 = 13.

Ответ: Б–В, А–В, Г–Д, Д–Е, Б–Г; сумма 1313

Потренируйте навык

Все задания на этот навык

Решать