В этом уроке мы разберем, что такое подграфы, какие они бывают и как выглядят. Эти инструменты упростят работу со сложными графами
Что такое подграфы
Подграф — это часть графа, в которой мы берем некоторые его вершины и ребра. Другими словами, граф H является подграфом графа G, если вершины и ребра H являются подмножеством вершин и ребер G.
Ниже слева показан граф. Части исходного графа, которые не являются частью подграфа, показаны серым цветом и пунктирными линиями, хотя обычно их просто опускают:
Обратите внимание, что если ребро входит в подграф, то обе его конечные точки должны входить в него. Не имеет смысла иметь ребро без конечной точки.
Существует несколько видов подграфов, которые мы и разберем далее в уроке.
Индуцированные подграфы
Чтобы лучше понять этот вид подграфов, обратимся к еще одному понятию — инцидентным вершинам. Так называют вершины, если у них есть общее ребро. Например, если между вершинами A и B есть ребро, значит A и B считаются инцидентными.
Индуцированными называют подграфы, в которых все вершины включает в себя все ребра исходного графа, инцидентные этой вершине.
Для наглядности посмотрим на графы ниже:
Здесь изображено три графа:
-
Исходный граф, из которого следуют следующие два подграфа
-
Неиндуцированный подграф. Он включает вершины и , но не повторяет все ребра с этими вершинами. На исходном графе показаны пять ребер с этими вершинами . На подграфе всего два ребра — не хватает и
-
Индуцированный подграф. Он включает вершины и и повторяет все ребра с этими вершинами —
Когда нам нужно удалить вершины из графа, мы также должны удалить все ребра, инцидентные этим вершинам. Посмотрим на таком примере:
Ниже показан граф и два подграфа после удаления вершин:
-
Исходный граф
-
Подграф с удаленной вершиной — значит, мы должны удалить четыре ее ребра
-
Подграф с удаленными вершинами и — значит, мы должны удалить ребра с этими вершинами и в итоге разбить граф на две части
Если — граф, а — подмножество его вершин, то мы удалить вершины и обозначить новый граф через . Если состоит только из одной вершины , то вместо этого мы будем писать . Если удаляем только одно ребро , обозначим это .
Подграфы и клики
В работе с подграфами часто употребляется термин «клика» — это подмножество вершин графа, любые две из которых соединены ребром. Другими словами, это объединение смежных вершин.
Посмотрим на примере:
На этом графе у нас есть две клики:
-
Из четырех вершин в левом нижнем углу (обозначена красным)
-
Из трех вершин в правом верхнем углу (обозначена зеленым)
Чтобы точнее понять, что такое клика, представьте социальную сеть. По сути — это граф. Люди — это вершины, а ребра — это отношения людей между собой. Кликой в этом графе можно назвать группу друзей, коллег или любых других знакомых людей.
Особенно часто клики упоминают в работе с циклами и путями в графах. Примеры пути и цикла в графе:
Когда мы говорим, что граф содержит путь или цикл, значит, в нем есть подграф с кликой в несколько вершин, который является путем или циклом.
Независимое множество
Существует и противоположность клики — независимое множество. Это набор вершин в графе, в котором ни одна вершина не является смежной с другой.
Снова представим граф — социальную сеть. Независимое множество в нем — это набор людей, которые все незнакомы друг с другом.
Так независимое множество выглядит в графе:
Выводы
В этом уроке вы узнали больше о подграфах, кликах и независимых множествах. Теперь вы сможете эффективнее работать с сложными графами и большим количеством вершин, ведь вы сможете разделить запутанный граф на несколько подграфов и изучить отдельные клики.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
