Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Связанность графов Теория графов

В теории графов много разных типологий и делений на виды. В этом уроке мы рассмотрим еще одну типологию и познакомимся с понятием связанности. Эти знания помогут эффективнее строить графы, особенно в тех задачах, когда речь идет о расстояниях.

Связный и разомкнутый граф

Граф называется связным, если можно проложить путь между каждой парой его вершин. Если хотя бы две вершины не соединены, граф называется несвязным или разомкнутым. Посмотрим на примере ниже:

eyJpZCI6ImQwYzI4ZDEyN2VmNTUyZDBiM2JkNmVkNTZjMDRkNmI3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5073dd71caef297c14b8d7f4ac1653bee78298d2fb6530d280ba5608e1760457

Также в разговоре о связанности графов важен еще один термин — компонента графа. Это максимальный связный подграф, который нельзя сделать больше, не потеряв связанность при этом.

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

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

У связного графа может быть только одна компонента. Компонента из одной вершины, называется изолированной вершиной.

Как и другие, связные графы можно делить на большее количество компонентов. Разберем, как это можно сделать.

Вершина и ребро разреза

У вершин и ребер есть два важных типа:

  • Вершина разреза — это вершина, удаление которой разбивает граф на большее количество компонентов, чем было

  • Ребро разреза — это ребро, которое при удалении разбивает граф на большее количество компонентов, чем было

Если удалить из связного графа вершину разреза или ребра разреза, то граф разъединится. Например:

eyJpZCI6ImU2MTQ5ZDNiYjNhYmI1NzY5YjkxN2E4Zjc2ZDk2M2U0LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=74a4060e05f4fc603620dbe15b42efc72f49974087c7eb2bb4052485bb1541e0

В этом графе вершины и — разрезанные, так как удаление любой из них приведет к разъединению графа. Ребро — разрезанное по той же причине. Других разрезанных вершин и разрезанных ребер в графе нет.

Разрезанные вершины и ребра действуют как «узкие места», когда речь идет о связности. Например, любой путь в графе выше от крайней левой до крайней правой вершины должен проходить через и ребро .

Если удалить разрезанную вершину, это разобьет связный граф на две составляющие или больше. Например, удаление центра звезды разобьет вершину на множество компонентов. Удаление разрезанного ребра может разбить только связный граф только на две составляющие.

Расстояние

Промежуток между двумя вершинами графа называется расстоянием и показывает, насколько вершины удалены друг от друга.

Например, если обозначить расстояние между двумя вершинами , значит, это длина кратчайшего пути между в графе.

Посмотрим на этот граф:

eyJpZCI6IjkzYTM5ZjY0MWM1NTg4NDQyN2I1OWVlMWEwNjk4MThlLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=6930f79882c174965372b37919689b2bf9133f7cbb67a46033bbdd4d381c3ca2

На приведенном ниже графике и находятся на расстоянии от . Вершина находится на расстоянии от , а вершина — на расстоянии от :

Кроме того, существует несколько путей из в , но длина самого короткого пути — , поэтому это и есть расстояние.

Выводы

В этом уроке мы познакомились с еще несколькими важными терминами из теории графов:

  • Связный граф — граф, в котором можно проложить путь между каждой парой его вершин

  • Разомкнутый граф — граф, в котором хотя бы две вершины не соединены

  • Компонента — максимальный связный подграф, который нельзя сделать больше, не потеряв связанность при этом

  • Вершина или ребро разреза — это вершина или ребро, удаление которых разбивает граф на большее количество компонентов, чем было


Самостоятельная работа

Задача №1

Представьте полный граф, который имеет вершин. Найдите количество ребер, которые он может содержать.

Нажмите, чтобы увидеть ответ

Формула для общего числа ребер в графе имеет такой вид:

Количество ребер

Задача №2

Если граф имеет ребер, то сколько у него вершин?

Нажмите, чтобы увидеть ответ

Как мы знаем,

Количество ребер

Решая вышеприведенное квадратное уравнение, получаем:

Так как количество вершин не может быть отрицательным.

Следовательно,


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и соглашаетесь с «Условиями использования»

Изображение Тото

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу