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

151Й шожео'гвом вершин множество S . Максимальность подграфа < S > поггамаатоя в смысле отношения включения графов, т. а, так, что любой его надгра'", не оовпадаювдм о <_S>, содержит зли ввршггу, не пркнаотежащую S , или ребро, не принадле-ищее К . Таким об­ разом, максимальность <S> означает, что \/H=(W,Y)(HT<S>&<S>CH =?> Граф G~(y>)() называется пуотым ил!1 £ 1улъ-графом, воли У~0' . Обозначим пуотой гряф о / Bepimma ®! через 0 ^ . Пус­ той граф о множеотвом вершин V" обозначаете 0(V) • Граф l 9 ~ ( V f X ) называется полшш, если Wi Vr i s f т . е . любые две верпишы омежны. Полныг^ грзф о И»1 вершинами обозначается Ки • Полный граф о. множеством воршин V обозна­ чается К(V) . Граф Кц няг1шзав'1 л таюке И -кликой. Пусть Gi'Cy,)({) - оотовныа подграфы графа Тогда граф иа5нв!автоя дополнением графа в гра­ фе (? , если I т . е . дополнение 1^,афа в (х это остовной подграф грфа G , который оодергскт те и только- те ребра графа G , которые не содеряштся в ^7^ . Дополнение графа &-СЧ)Х) в ЦМ ) называется просто до­ полнением графа G и обозначается (г , Два верганы в G- омежны тогда и_только тогда, когда_оки на смежш в & , Очавад- но. < ? - 6 : , KCV)= 0 ( V ) и i } ( / ) = } <CV ) . На рис.2.4 покаэанн граф G' , даа его оотовных подграфа, нол)иый граф К_ и шроаденный подграф <S> да S = - { • ^ ^ • Гз Рис.2.4 52.3. Удаление и добавлергаа ветапт и ребоо Пусть дан граф б-СУ^Х^', - подмножество множества вершин. Удалением множества в е ршини з графа ($• называется операция, при которой из графа 6- удаляитоя все варшиш; мпожеот- I I