Rivalry2

HTML Diff

3 added 3 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <h2>Что такое подграфы</h2>

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

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

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

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

7 <h2>Индуцированные подграфы</h2>

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

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

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

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

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

12 <ul><li>Исходный граф, из которого следуют следующие два подграфа</li>

13 <li>Неиндуцированный подграф. Он включает вершины a, b, c и d, но не повторяет все ребра с этими вершинами. На исходном графе показаны пять ребер с этими вершинами AB, AC, BC, BD, CD. На подграфе всего два ребра - не хватает BC, AB и CD</li>

14 <li>Индуцированный подграф. Он включает вершины a, b, c и d и повторяет все ребра с этими вершинами - AB, AC, BC, BD, CD</li>

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

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

17 <ul><li>Исходный граф</li>

18 <li>Подграф с удаленной вершиной a - значит, мы должны удалить четыре ее ребра</li>

19 <li>Подграф с удаленными вершинами b и c - значит, мы должны удалить ребра с этими вершинами и в итоге разбить граф на две части</li>

20 - </ul>Если G - граф, а S - подмножество его вершин, то мы удалить вершины и обозначить новый граф через G - S. Если S состоит только из одной вершины v, то вместо этого мы будем писать G - v. Если удаляем только одно ребро e, обозначим это G - e.

20 + </ul>Если G - граф, а S - подмножество его вершин, то мы удаляем вершины и обозначаем новый граф через G - S. Если S состоит только из одной вершины v, то вместо этого мы будем писать G - v. Если удаляем только одно ребро e, обозначим это G - e.

21 <h2>Подграфы и клики</h2>

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

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

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

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

25 <ul><li>Из четырех вершин в левом нижнем углу (обозначена красным)</li>

26 <li>Из трех вершин в правом верхнем углу (обозначена зеленым)</li>

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

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

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

30 <h2>Независимое множество</h2>

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

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

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

34 <h2>Выводы</h2>

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