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

тальных долей; такой граф обозначается Pi - I^lJ , i - if • Пользуясь определетгюлч cnepsmiK над графами, легко псказата, что =Кр^+" !- Кр^. В ч; нсоти. + . Еоли граф несвязный, то он будет двудольныги тогда и -ibKo тогда, когда каадая его кошононта является двудольгаг,! щи тр:ь эиал'-ным графом. Учитывая это, будем в дальксйаом раосмв1р'ЛБа;'ь связные rpajH. Простой призн"" двудольнооти графа дает оладущая теорема. 'Гворйма S.IkKemira). Граф ^?=(V'Д)яri.;l:лaтcя двудольшм тог­ да « только тогда, когда вое его простые цяклн имеют чатщ'л дли­ ну. Необходимооть f ^ ( V , , X ) - ,двудольный г р а . Пуоть Х = ft-i',, • • •» - произвольний простой Ц1ПСЛ fpni^fia /у . Ок оодериат И разных вершин и имеет длину И , Допустим, что . Тогда вое вориины цикла Z пмвгадаа нячетш'в оуб- индексы, принадлежат , а аерщига, имеющие четныо субиндексы, прияададжат Vjij . Осоедииа вершины цикла Z принадлежат разным долям, т . к . они смежны. Таким образом, и И -четно . Доотаточноот'^- С ) . По уоловик. ;се простые циклы •четны. Выберем произвольную веришну V } ^ V . Опредогам множества - = { e i ^ . < £ V ; p c ; i r , V ) - четко} , •{ iTi j U , : Имеем разбиение iVt,\/A,} множества V . Покажем, что граф ij' m e - . 0'г вид ^ =(^(,У'д.. X ) • Допуотям противное. Рассмотрим разные случаи. 1 . Пуоть 3 П о опраделанию множества V^, f f V i j l t J - нечетно и - нечатно. ОЙсаначим P| kPjj^ кратчай­ шие ироотае (V'i'if'iii (."Oi-tT) - цепи; а) еоли Р, tiBx, .не имеют об- -щх вершин, кроме Щ ,'то простой цикл "2 me ­ et нечетную диину \ХС1)1" IУ(Pi)li-iy(^x^)lH. Надачиа такого ци л а противоречит условию; б) если Р, имеют общие вершины, кроме V\ , оосзиачим пооледнюа из таких вершин (от ) чераз u t . Торд' отрззки прос'"нх цепей Р, и от г!.?"к К. и к рабро a:=ltt.,trj образуют простой цикл нечетной даны (в обоих возможных олучаях (рио.8.2,а)и U>'eVi(pHo.B-2,d). что противоречит уолсвию. 2 . Предположение, что 3IL . € \/( : U омгГ также приводит к противоречию о усовием о четности црортых циклов, которое дока- зываатоя яо аналогии со олучаем I . Таким образом, доказано, что в каждом из множеств Vf и V^, нот смажных варшн, т . е . граф яБляет- оя двудольным и имеет вид; <? ~ ( V i tVn.^ X ) . 47