Что такое направленный граф. Определение ориентированного графа. Ориентированные и неориентированные графы
На первом занятии, вводя понятие графа, мы рассматривали в качестве примера состязания спортивных команд. Мы. соединяли две команды, скажем А и С, ребром АС в том случае, когда эти команды уже играли друг с другом. Однако такой граф не дает ответа на один весьма существенный вопрос: кто именно выиграл игру?
Этот недостаток легко может быть устранен. Если команда А выиграла у С, условимся ставить на ребре АС стрелку, направленную от А к С. Предположим, что нам известны результаты всех уже сыгранных игр, и добавим к графу рис. 1 соответствующие стрелки; пусть при этом получится граф, изображенный на рис. 58.
Рис 58.
На этом графе показано, что команда А выиграла у С, команда F проиграла А, а В выиграла все игры - с С, Е, F и т. д.
Ребро графа называется ориентированным , если одну вершину считают началом ребра , а другую - концом .Граф, все ребра которого ориентированы, называется ориенти рованным графом .
Одна и та же вершина ориентированного графа может служить началом для одних ребер и концом для других. Соответственно различают две степени вершины: степень выхода и степень входа.
Степенью выхода вершины А ориентированного графа называется число выходящих из А ребер (обозначение: d+(A)).
Степенью входа вершины А ориентированного графа называется число входящих в А ребер (обозначение: d-(A)).
А что, если какая-то игра окончилась вничью? Мы можем отразить ничейные результаты на графе, оставляя соответствующие ребра неориентированными. При этом мы получим так называемый сме шанный граф , на котором имеются как ориентированные, так и неориентированные ребра.
Путем в ориентированном графе G от А1 до Аn называется последовательность ориентированных ребер <А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, такая, что конец каждого предыдущего ребра совпадает с началом следующего и ни одно ребро не встречается более одного раза.
Рис. 59
Если в ориентированном графе G нашелся путь от А до В, то обратного пути от В к А может и не быть (рис. 59).
Если существует ориентированный путь от А до В, то говорят, что В достижи ма из А,
В графе G на рисунке 38 В достижима
из А, А не достижима из В.
Простым путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом.
Длиной пути называется число ребер в этом пути.
Расстоянием от А до В в ориентированном графе называется длина наикратчайшего пути от А до В. Если пути от А до В не существует, то расстояние от А до В называют бесконечным и обозначают?. Расстояние от А до В будем обозначать S (АВ). Для графа на рисунке 38
S (АВ) = 1, S (СВ) - 2, S (ВС) = ?.
Задача 9.1.
В приморском курортном городе после установления одностороннего движения оказалось, что число улиц, по которым можно въехать на каждый перекресток, равно числу улиц, по которым можно из него выехать. Докажите, что можно предложить такой маршрут патрулирования, который начинается и оканчивается в одном месте и проходит через каждый участок улиц ровно один раз.
Решение.
Построим орграф G, задающий движение в городе.
Орграф называется связным, если от любой его вершины до любой другой можно перейти по дугам без учета их ориентации. Связный орграф называется эйлеровым, если в нем есть эйлеров цикл.
Теорема 12. Связный орграф является эйлеровым тогда и только тогда, когда для каждой его вершины v выполняется равенство d - (v ) = d + (v ) .
Теорема доказывается точно так же, как и теорема в задаче 4.2.
Из условия задачи следует, что для вершин построенного графа G выполняется равенство d-(v) = d+(v). Следовательно, граф G эйлеров, и эйлеров цикл определит нужный маршрут патрулирования.
Задача 9.2.
На плоскости отмечено конечное число точек. Некоторые пары точек являются началами и концами векторов, причем число векторов, входящих в любую точку равно числу векторов, выходящих из нее. Найдите сумму векторов.
Решение.
Точки плоскости вместе с векторами образуют орграф G.Цикл орграфа, все вершины которого различные, называется контуром.
Теорема 13. Связный орграф G эйлеров тогда и только тогда, когда G является объединением контуров, попарно не имеющих общих ребер.
Доказательство. Необходимость.Пусть G - эйлеров орграф. Рассмотрим его любую вершину u1. Выйдем из вершины u1по некоторой дуге (u1, u2).Это возможно сделать, так как орграф Gсвязный. Поскольку d-(u2) = d+(u2), то из вершины u2можно выйти по дуге (u2, u3). Орграф Gимеет конечное число вершин, поэтому, в конце концов, мы попадем в некоторую вершину w, в которой были раньше. Часть цепи, которая начинается и оканчивается в вершине w, является контуром С1. Удалим дуги контура С1 из орграфа G. В получившемся орграфе G1(возможно несвязном) степени входа и выхода вершин, принадлежавших С, уменьшились на единицу, степени входа и выхода остальных вершин не изменились. Следовательно, для любой вершины v орграфа С1 будет выполняться равенство d-(v) = d+(v). Поэтому в орграфе G1 можно выделить контур C2 и т.д.
Достаточность доказывается путем объединения контуров в эйлеров цикл (см. доказательство теоремы в задаче 4.2).
Теорема доказана. Возможно, орграф G, задающий векторы в нашей задаче, не является связным. Применив доказанную теорему к каждой связной части орграфа, получим разбиение векторов на контуры. Сумма векторов, принадлежащих одному контуру, равна нулю. Следовательно, сумма всех векторов равна нулю.
Пусть V, D - произвольные множества, причем V ??. Обозначим через V 2 декартов квадрат множества V .
Ориентированным графом или, короче, орграфом G называется тройка (V, D, ц ) : где ц - некоторое отображение множества D в множество V 2 . Элементы множеств V и D называются соответственно вершинами и дугами орграфа G . Множества вершин и дуг орграфа G удобно обозначать через VG и DG соответственно. Если f - дуга, то ц (f ) является упорядоченной парой (и, v ), где и : v Ј V . Дуга f выходит из вершины и и заходит в вершину v ; в свою очередь и и v называются концевыми вершинами дуги f ; в дальнейшем будем писать f = (а иногда даже - f = uv , если нет опасности возникновения путаницы).
При записи произвольного орграфа он, как правило, будет представляться в виде G = (V, D ).
Орграфы принято изображать при помощи диаграмм, аналогичных диаграммам для графов. Разница состоит лишь в том, что линия, изображающая дугу, имеет направление.
С каждым орграфом G = (V, D ) естественно связать граф G o = (V, Е ), называемый основанием данного орграфа. Для получения основания необходимо в орграфе G заменить каждую дугу f = ребром е = uv
На рис. 8 изображены орграф и его основание
Рисунок 8
Орграф G называется связным, если связным является его основание. Ориентированым маршрутом или, короче, ормаршрутом в орграфе G называется чередующаяся последовательность вершин и дуг
В которой
Такой маршрут принято называть (v о , v t ) - ормаршрутом; вершины v o и v t называются соответственно начальной и конечной вершинами такого ормаршрута. Если v o = v t , то ормаршрут называют замкнутым. Количество дуг, составляющих ормаршрут, - это длина ормаршрута.
Ормаршрут, не содержащий повторяющихся дуг, называют орцепью. Простая орцепь - это орцепь без повторяющихся вершин (кроме, быть может, совпадающих начальной и конечной вершин). Замкнутая простая орцепь называется орциклом или контуром.
Нетрудно проверить, что существование (и, v ;) - ормаршрута гарантирует существование простой (и, v ) - орцепи.
Говорят, что вершина v достижима из вершины и , если существует (и, v) ормаршрут. Орграф G сильно связен или орсвязен, если любая его вершина достижима из любой другой вершины. Очевидно, сильно связный орграф является связным; обратное утверждение, разумеется, не верно.
Граф G называется ориентируемым, если он является основанием некоторого сильно связного орграфа.
Теорема 1.3 . Связный граф G ориентируем тогда и только тогда, когда каждое его ребро не является мостом.
Доказательство . Пусть граф G является основанием орграфа Н и G содержит мост е . Тогда в Н имеется дуга f =, где и, v - концы ребра е . Очевидно, в Н нет (u, v ) - ормаршрутов. Следовательно, граф G не является ориентируемым.
Обратно, пусть граф G не имеет мостов, т.е. каждое ребро графа G содержится в некотором цикле. Поскольку любой цикл является ориентируемым графом, в графе G существует максимальный ориентируемый подграф Н . Убедимся, что Н = G . Допустим, что это равенство не выполнено. В силу связности графа G существует ребро е, инцидентное вершине v из Н и не лежащее в Н . По предположению ребро е лежит в некотором цикле С . Обозначим через Q множество ребер цикла, не принадлежащих подграфу Н . Нетрудно понять, что, добавив к Н все ребра из множества Q , мы снова получим ориентируемый подграф в противоречие с выбором Н .
Пусть G - произвольный орграф. Полустепенью исхода degv вершины v называется число всех дуг, имеющих v в качестве начала. Аналогично, полустепень захода degv - это число всех дуг, для которых вершина v является концом. Орграф, содержащий п вершин и т дуг будем называть (n, т ) - орграфом.
Полустепени исхода и полустепени захода связаны следующим очевидным образом.
Лемма 1 . Пусть G - произвольный (n, т ) - орграф. Тогда
Это утверждение аналогично лемме 1 из разд. 1.1; его часто называют орлеммой о рукопожатиях.
Ориентированный граф (кратко орграф ) - (мульти) граф , рёбрам которого присвоено направление. Направленные рёбра именуются также дугами , а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом .
Основные понятия
Формально, орграф D = (V , E) {\displaystyle D=(V,E)} состоит из множества V {\displaystyle V} , элементы которого называются вершинами , и множества E {\displaystyle E} упорядоченных пар вершин u , v ∈ V {\displaystyle u,v\in V} .
Дуга (u , v) {\displaystyle (u,v)} инцидентна вершинам u {\displaystyle u} и v {\displaystyle v} . При этом говорят, что u {\displaystyle u} - начальная вершина дуги, а v {\displaystyle v} - конечная вершина .
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг , вида v 0 { v 0 , v 1 } v 1 { v 1 , v 2 } v 2 . . . v n {\displaystyle v_{0}\{v_{0},v_{1}\}v_{1}\{v_{1},v_{2}\}v_{2}...v_{n}} (вершины могут повторяться). Длина маршрута - количество дуг в нём.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь - без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь .
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур .
Орграф сильно связный , или просто сильный , если все его вершины взаимно достижимы ; односторонне связный , или просто односторонний , если для любых двух вершин, по крайней мере, одна достижима из другой; слабо связный , или просто слабый , если при игнорировании направления дуг получается связный (мульти)граф;
Максимальный сильный подграф называется сильной компонентой ; односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа D {\displaystyle D} называют орграф , вершинами которого служат сильные компоненты D {\displaystyle D} , а дуга в D ⋆ {\displaystyle D^{\star }} показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Дополнительные определения
Направленный ациклический граф или гамак есть бесконтурный орграф.
Ориентированный граф, полученный из заданного сменой направления рёбер на противоположное, называется обратным .
Изображение и свойства всех орграфов с тремя узлами
Легенда: С - слабый, ОС - односторонний, СС - сильный, Н - является направленным графом, Г - является гамаком (ациклический), Т - является турниром
| 0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
| пустой, Н, Г | Н, Г | ОС | CC | CC | полный, CC | |
|---|---|---|---|---|---|---|
| ОС, Н, Г | CC, Н, Т | CC | ||||
| C, Н, Г | ОС, Н, Г, Т | ОС | ||||
| C, Н, Г | ОС |
В предыдущих главах мы представили некоторые основные результаты теории неориентированных графов. Однако для описания некоторых ситуаций неориентированных графов недостаточно. Например, при представлении схемы уличного движения графом, ребра которого соответствуют улицам, для указания допустимого направления движения ребрам необходимо присваивать ориентацию. Другим примером является программа для ЭВМ, моделируемая графом, ребра которого представляют поток управления от одних множеств инструкций к другим. В таком представлении программы для указания направления потока управления ребрам также необходимо присвоить ориентацию. Еще одним примером физической системы, для представления которой требуется ориентированный граф, является электрическая цепь. Применения ориентированных графов и соответствующие алгоритмы рассматриваются в гл. 11-15.
В этой главе предлагаются вниманию основные результаты теории ориентированных графов. Обсуждаются вопросы, связанные с существованием ориентированных эйлеровых цепей и гамильтоновых циклов. Рассматриваются также ориентированные деревья и их связь с ориентированными эйлеровыми цепями.
5.1. Основные определения и понятия
Начнем с введения нескольких основных определений и понятий, относящихся к ориентированным графам.
Ориентированный граф состоит из двух множеств: конечного множества V, элементы которого называются вершинами, и конечного множества Е, элементы которого называются ребрами или дугами. Каждая дуга связана с упорядоченной парой вершин.
Для обозначения вершин используются символы а для обозначения дуг - символы . Если , то называются концевыми вершинами при этом - начальная вершина, - конечная вершина . Все дуги имеющие одну пару начальных и конечных вершин, называются параллельными. Дуга называется петлей, если инцидентная вершина является одновременно начальной и конечной ее вершиной.
В графическом представлении ориентированного графа вершины изображаются точками или кружками, а ребра (дуги) - отрезками
линий, соединяющими точки или кружки, представляющие их концевые вершины. Кроме того, дугам присваивается ориентация, показываемая стрелкой, направленной от начальной вершины к конечной.
Например, если такие, что Их), ориентированный граф можно представить рис. 5.1. В этом графе - параллельные дуги, а - петля.
Рис. 5.1. Ориентированный граф.
Говорят, что дуга инцидентна своим концевым вершинам. Вершины называются смежными, если они являются концевыми для одной дуги. Если дуги имеют общую концевую вершину, то они называются смежными.
Дуга называется исходящей из своей начальной вершины и заходящей в свою конечную вершину. Верщина называется изолированной, если она не имеет инцидентных дуг.
Степенью вершины называется число инцидентных ей дуг. Полустепенью захода вершины является число заходящих в V] дуг, а полустепенью исхода - число исходящих из дуг. Символами и б" обозначают минимальнее полустепени исхода и захода ориентированного графа. Аналогично символами обозначают максимальные полустепени исхода и захода соответственно.
Множества любой вершины определяются следующим образом: . Например, в графе на рис. 5.1 .
Заметим, что петля увеличивает полустепени как захода, так и исхода этой вершины. Следующее утверждение является следствием того, что каждая дуга увеличивает на 1 сумму полустепеней как захода, так и исхода ориентированного графа.
Теорема 5.1. В ориентированном графе с дугами
Сумма полустепеней захода=Сумма полустепеней исхода=m.
Подграфы и порожденные подграфы ориентированного графа определяются так же, как и в случае неориентированных графов (разд. 1.2).
Неориентированный граф, получающийся в результате снятия ориентации с дуг ориентированного графа G, называется лежащим в основе неориентированного графа G и обозначается через .
Ориентированным маршрутом ориентированного графа называется такая конечная последовательность вершин
Что является дугой графа G. Такой маршрут обычно называется ориентированным -маршрутом, причем начальная вершина, - конечная вершина маршрута, а все другие вершины - внутренние. Начальная и конечная вершины ориентированного маршрута называются его концевыми вершинами. Отметим, что дуги, а следовательно, и вершины могут появляться в ориентированном маршруте более одного раза.
Ориентированный маршрут называется открытым, если его концевые вершины различны, в противном случае - замкнутым.
Ориентированный маршрут называется ориентированной цепью, если все его дуги различны. Ориентированная цепь является открытой, если ее концевые вершины различны, в противном случае - замкнутой.
Открытая ориентированная цепь называется ориентированным путем, если различны все ее вершины.
Замкнутая ориентированная цепь называется ориентированным циклом или контуром, если ее вершины, за исключением концевых, различны.
Говорят, что ориентированный граф ациклический или бесконтурный, если он не имеет контуров. Например, ациклическим является ориентированный граф на рис. 5.2.
Рис. 5.2. Ациклический ориентированный граф.
Рис. 5.3. Сильно связный ориентированный граф.
Последовательность вершин ориентированного графа G называется маршрутом в G, если она является маршрутом лежащего в основе неориентированного графа Например, последовательность в графе на рис. 5.2 является маршрутом, но не ориентированным.
Аналогичным образом определяются цепь, путь и цикл ориентированного графа.
Ориентированный граф называется связным, если связным является лежащий в его основе неориентированный граф.
Подграф ориентированного графа G называется компонентой графа G, если он является компонентой графа
Вершины ориентированного графа G называются сильно связными, если в G существуют ориентированные пути из и обратно. Если сильно связна с то, очевидно, , сильно связна с . Всякая вершина сильно связна сама с собой.
Если вершина сильно связна с вершиной то, как легко видеть, вершина сильно связна с вершиной Следовательно, в этом случае просто говорят, что вершины сильно связны.
Ориентированный граф называется сильно связным, если сильно связны все его вершины. Например, сильно связным является граф на рис. 5.3.
Максимальный сильно связный подграф ориентированного графа G называется сильно связной компонентой графа G. Если ориентированный граф сильно связен, то он имеет единственную сильно связную компоненту, а именно самого себя.
Рассмотрим ориентированный граф . Легко видеть, что всякая его вершина принадлежит точно одной сильно связной компоненте графа G. Следовательно, множества вершин сильно связных компонент образуют разбиение множества вершин У графа
Рис. 5.4. Граф и его конденсация.
Например, ориентированный граф на рис. 5.4, а имеет три сильно связные компоненты с множествами вершин и образующими разбиение множества вершин ориентированного графа.
Интересно, что в ориентированном графе могут быть дуги, не входящие ни в какие сильно связные компоненты графа. Например, ни в какие сильно связные компоненты не входят дуги в графе на рис. 5.4, а.
Таким образом, хотя свойство «сильной связности» влечет разбиение множества вершин графа, оно может не порождать разбиение множества дуг.
Объединение, пересечение, сумма по mod 2 и другие операции над ориентированными графами определяются точно так же, как и в случае неориентированных графов (разд. 1.5).
Граф, получающийся в результате стягивания всех дуг сильно связных компонент ориентированного графа G, называется конденсированным графом графа G. Конденсация графа, приведенного на рис. 5.4, а, представлена на рис. 5.4, б.
Вершины графа соответствуют сильно связным компонентам графа G и называются конденсированными образами компонент.
Ранг и цикломатическое число ориентированного графа те же, что и у соответствующего неориентированного графа. Это означает, что если ориентированный граф G имеет дуг, вершин и компонент, то ранг и цикломатическое число графа G определяются выражениями
Теперь определим минимально связные ориентированные графы и изучим некоторые их свойства.
Ориентированный граф G называется минимально связным, если он сильно связный, а удаление любой дуги лишает его свойства сильной связности.
Рис. 5.5. Минимально связный ориентированный граф.
Минимально связным является, например, граф, представленный на рис. 5.5.
Очевидно, что минимально связные графы не могут иметь параллельных дуг и петель.
Мы знаем, что неориентированный граф минимально связен тогда и только тогда, когда он является деревом (упр. 2.13). По теореме 2.5 дерево имеет не менее двух вершин степени 1. Следовательно, минимально связные неориентированные графы имеют по крайней мере две вершины степени 1.
Установим аналогичный результат для ориентированных графов. Степень всякой вершины сильно связного ориентированного графа должна быть не менее 2, поскольку каждая вершина должна иметь исходящую и заходящую дуги. В следующей теореме мы доказываем, что в минимально связном ориентированном графе имеются по крайней мере две вершины степени 2.
Перед тем как начать изучение непосредственно алгоритмов, необходимо обладать базовыми знаниями касательно самих графов, понимать, как они представляются в компьютере. Здесь не будут подробно описаны все аспекты теории графов (этого и не требуется), но только те, незнание которых заметно усложнит усвоение данной области программирования.
Несколько примеров дадут немного поверхностного представления о графе. Так типичным графом является схема метро или какой-либо другой маршрут. В частности программисту знакома компьютерная сеть, также являющаяся графом. Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точки – это отдельные серверы, а линии – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами (узлами ), а линии – ребрами (дугами ). Таким образом, граф – это совокупность вершин, соединённых ребрами.
Математика оперирует не содержанием вещей, а их структурой, абстрагируя ее из всего того, что дано как целое. Пользуясь именно этим приемом, мы можем заключать о каких-либо объектах как о графах. А поскольку теория графов это часть математики, то для нее нет абсолютно никакого значения, что в принципе представляет собой объект; важно лишь то, является ли он графом, т. е. обладает ли обязательными для графов свойствами. Поэтому, прежде чем привести примеры, мы выделяем в рассматриваемом объекте лишь то, что как нам кажется, позволит показать аналогию, отыскиваем общее.
Вернемся к компьютерной сети. Она обладает определенной топологией, и может быть условно изображена в виде некоторого числа компьютеров и путей их соединяющих. На рисунке ниже в качестве примера показана полносвязная топология.
Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.
Вот некоторые важные обозначения, используемые в теории графов:
- G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
- |V| – порядок (число вершин);
- |E| – размер графа (число рёбер).
В нашем случае (рис. 1) |V|=5, |E|=10;
Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 2).
В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.
В орграфе, в отличие от неориентированного графа, имеется возможность двигаться из вершины h в вершину s без промежуточных вершин, лишь тогда когда ребро выходит из h и входит в s, но не наоборот.
Ориентированные графы имеют следующую форму записи:
G=(V, A), где V – вершины, A – направленные ребра.
Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.
В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)], другие – ненаправленные [(e, d), (e, b), (d, c)…].
Два или более графов на первый взгляд могут показаться разными по своей структуре, что возникает вследствие различного их изображения. Но это не всегда так. Возьмем два графа (рис. 4).
Они эквивалентны друг другу, ведь не изменяя структуру одного графа можно построить другой. Такие графы называются изоморфными , т. е. обладающими тем свойством, что какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. На рисунке 4 изображены два изоморфных графа.
Когда каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра, тогда такой граф взвешенный . В разных задачах в качестве веса могут выступать различные виды измерений, например длины, цены маршруты и т. п. В графическом представлении графа весовые значения указываются, как правило, рядом с ребрами.
В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с последующей посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом. Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e), (a), (b), (c)]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’=(V’, E’) является подграфом графа G=(V, E), только тогда когда V’ и E’ принадлежат V, E.
