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

наД и BOO ребра, инцидвцтше им. Результат этой операции обо­ значим $ ~h . Еоли -4= - одноэлементное подмножество V , то вместо fi'-itr} пишем &-ХГ . И з определения оледует, что & -0 « f . Легко заметить, что порояденннй подграф ^ S > для нехсоторо— го ыножеотаа воршян V можно определить как^-З? -а б"~/4 j где , п г \ Удалением множества Y<^X из графа назы­ вается операция, при которой из rpaiva удаляютоя вое ребра гра­ фа , входящие в множество \ . Результат пр .менения этой опе­ рации обозначим ( f ^ Y . Очевидно, V(^tf-Y) - V((?); YC(r-Y)=y - Y . Eo.i;, Y-{^1 - одноэлементное множеотво. то вместо пищам . Любой подграф r^'afa 9 может быть получен применением опера­ ций удаления вертин и ребер. Граф ff-YC^cX) . "олученннй ии (Г удажшием только ребер, будет оотовным подграфом графа & , т . к . по определе­ нию Граф G~AСА<^У), по.пучвнннй из С удалением только вер­ шин, будет дорождешшм подграфом < Ч ^ А ? графа Q . Пуоть дан граф \ А - произвольное конечное множеотво нарашн \ - множеотво ребер, не входя­ щих в )С •. Y С Добавлением мнозкеотпа верши" Л х гяафуб' назннаатоя опера­ ция, при которой поетчаетоя граф & ' -СУ ' ,К ' ) , обазначаемы? , такой, 4 T o V = \ / ^ A , Е о л и множеот­ во А=iur} одноэлементное, то т вото . ^ +l b f i пишем € • *ъУ Добавлением множества р j e pY назнваетоя еперация, nr't к о - , торой ^получается граф 5 =( V ' , y ' , , обозначаемый <r-^Y , такой, что V = \/ , У я У V Y . Еоли добавляется одно ребро ^ , то вместо ШдШем Q->-^ . §2.4. Стопени ватжшн Степенью вершины V графа называется число ийци- дентннх ей рабер. Степень вершины V" обозначаетоя г/((г,г^)и -i d c v ) . воли иаввотно, о каком графе идет речь. При вшшоленип отапеней вершин i t поевдографов обычно каж­ дая петля в данной вершине учитывается дважды. Есди d(.V)-0, то веришна нааыва соя изолированной. Вар­ шаваV , дяя которой cfcv^ = •/ , нааываатоя виоу^пвй яли концевой. 12