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

Подграфы Теория графов

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

Что такое подграфы

Подграф — это часть графа, в которой мы берем некоторые его вершины и ребра. Другими словами, граф H является подграфом графа G, если вершины и ребра H являются подмножеством вершин и ребер G.

Ниже слева показан граф. Части исходного графа, которые не являются частью подграфа, показаны серым цветом и пунктирными линиями, хотя обычно их просто опускают:

eyJpZCI6ImNiYjEwY2U3NWIzNTlkNjk1OTYzZDI5ZTk1YzAwOGY5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7ced512d60320350e64771e4971b265d478cae4828580082add32647f472033b

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

Существует несколько видов подграфов, которые мы и разберем далее в уроке.

Индуцированные подграфы

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

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

Для наглядности посмотрим на графы ниже:

eyJpZCI6IjMzOWQwYTNlNDJkMzlhOTc3MzNkNGUxMDcxOThhMWFjLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=61d579c90c006888972673ebca5808cd6590ea28ad75ac555fb2fa19001072f4

Здесь изображено три графа:

  • Исходный граф, из которого следуют следующие два подграфа

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

  • Индуцированный подграф. Он включает вершины и и повторяет все ребра с этими вершинами —

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

eyJpZCI6ImYxYTBmMDU4ZGQyN2MyYzI5MWY1MGEyMjhkOTg3Y2E3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=4d4914f074b60ee2c7878e4f46fdf923e2a15378610a6c0e54f0085fa946d709

Ниже показан граф и два подграфа после удаления вершин:

  • Исходный граф

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

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

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

Подграфы и клики

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

Посмотрим на примере:

eyJpZCI6IjkyYTMyYTIwYjFiN2NhNjAwODJlYzk4YjMxMTk3NzlmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=cd3a70074aaf1ee07232622d30929fffbb53e0e84961dd97250df64acbc9c87c

На этом графе у нас есть две клики:

  • Из четырех вершин в левом нижнем углу (обозначена красным)

  • Из трех вершин в правом верхнем углу (обозначена зеленым)

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

Особенно часто клики упоминают в работе с циклами и путями в графах. Примеры пути и цикла в графе:

eyJpZCI6Ijk2NmM4MGFiMTMyMzYyMTQ2MDA5YzI0ZWFjZDgzNGU5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=b554a8672598c071d8cb403acb937be29e313dc4a347c9456f135d737d527007

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

Независимое множество

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

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

Так независимое множество выглядит в графе:

eyJpZCI6IjE1NzdjMDRmZjAzMDBlNDYxYzIyYjFlNGMwMTI4Njg4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=9b9e7e6892c41162975db672582f7c2ed2f4635884c16093e6c4e51bb5093528

Выводы

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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