Теория графов и комбинаторика

40 можно считать, что ош1 не имеют общих вершин ( V!) Этого можно добиться проотым переобозначением вершин одного и з графов. В общем случае • fe.I. Бинарные опетепта 1 . Объедп!Гвнием г ^фо в и называется граф (f'^(VfX) , г д е V = V|UVAj^ )^=^iOXx, . Обозначается объединение графов так: ^ = , 2. Соединением графов наэьгааетот граф G~C\%k ) , для которого . Соеди- "чние графов ^ , обозначаемое (Р=(r<f , оодержит вое "•аршины и , •ребра графов'6^1 и ^ также ребра, соедиЕ^чицие каждую верши­ ну графе Gi о каждой вершиной графа <гд,. 3. Произведением графов и б-ц. незываетоя граф ; для которого пара У1 тогда и только тогда, «огда я иУ If оы Произведение графов обозначается Р = ; 4 . Композицаей графов нрзываетоя граф G ' множество. вершин яото. эго равно ¥ = V ^ x Уд, , н две вершинн омеяны тогда и только тогда, когда (dpi Q!tflj>iy/)\f Легко проверить, что если г р а ^ не имеет общих вершая, то количаотво рвршн и ребер графов Mojrjio вычислить по фop^Jiyлaм; для U (?д^ . • Д Л Я • ^ 1. iv/=P« f f '<i , i X k f = P4a,+Pj,<^,; для ff.ojj, 5 . Пераовчением графов и , обозначаемым к а к^^Пб^ , на аываетоя граф =' <V,X ) , дта которого V= V, Л , V= Х» / 1 , Граф &.{f\ ffi, содержит те и только т е вегвианы г ребра графов Gi ш которые содержатся а Е <?< и в (?I,. В случаях, когда эта операция смысла на имеет. . 6. Кольцевой суммой графов (?f и ^д,, обозначаемой , назыааегоя граф ^ - ( , \ / , Х ) , который не имеет изолированных BBjffiHH и ооотоит только из ребер, приоутотвуищйх либо в & i , либо ь 9 ^ , но ле в обоих графах одновременно (У = Ф У/, ) . 38