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

Лагко заметать, что ооли 6-~(М,Х) - гра,^ и Ci= (.^i, V L 'эго компонанти, то С = . Шоксотиа вершин компонент рафа образуют разбпенка F •- { V t , L .~ -/j и } множества вершн графа V , оледонательно, отношеггле принедлеж- ноотк двух вершин графа одной компоненте является эквквалонт- ноотью иа мнокес-ва V (ом.теорему I . I ) . Из данных опредалатай следует, что вершины разных КООТОНЙНТ графа не только не смек­ ни, но и не Moi^'T быть ооедпнеж маршрутом. Теорема 3 . 2 . Граф <?=('',/) 0BH3ffij>i тогда и только тогда, когда дая лккЗого разйяения {Vi, V j j ] множео.^а V на два под- шожеотва оущеотвует ребро, соединяющее некоторую вершину вэ Vi о некоторой варпганой из . Необходимость ( ) . Расомотрим произвольное разбиение множества V . В oir-y овя^нсти графа ^иТбУх,В простая i V - ЬУ) -цепь. Обозначим еа Здесь = vT . Найдем первую олева вершину Р , принадлежа­ щую Vj^ . Пусть зто будет вершна . Тогда Vl^_^ е Vj . Но ом 1^^ как оооедкке вершшш Ц01Ш. Pe6pc »=:{Vu^.,,lJ;i^J является искомым. Достаточность (<?=•) . Докажем связность графа. Выберем две прот!звольнив вершины, '0',иТбУ , Рассмотрим разбиение Vjb'"'] . где V/"'- ®• i.ir} ' ; Л/д^''=Уч\/''''. По условии теоремы существует ребро эг® =( г , if) } > где • Псотроим но­ вое разбиенка {V/", \/д," } . г д е V , и найдем новое ребро } . Здеоы^б1^".^ Пусть построено разбиение К-го шагаЩ"", 1^"'} . В соответст­ вии о описанной процедурой переходим к новому разбиению (Kti ) - го шага } . гд. . •Здеоь 6 и 1^+, смекна некоторой вершине из Ц . Дупем продолжать этот процеос построения новых разбиеюй до тех пор, когда на некотором -м июге будет выполнено условие 1Г^^, = 1 ^ ( и Г б ) • Это условие обязательно будет ны- полаенс через конечное число шагов, так как V'< является соботвенным подмножеством Л/< и множество^: вершин V конечно. Заметим также, что на каждом К -м шаге лю­ бые две вершины мнояествй V/'*'* можно соединить маршрутом, От- свда следует, что условие означает наличие в графе Q- (.IT-' "UT) -маршрута. В силу произвольности вершин справедошв вывод о OBjJSHOOTH графа 6. Доказательство, теоремы 3.2 конструктивно и 0оаво.чя0т по­ строить алгоритм проведи аозмсшюсти соединения любых Двух \ 23 ' ; •