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

i. .луотим, что вертина 1Г имеет )ц i- ождений в 2 . Так как вое • ребра в 2 разные, то при каждом вховдегши вершина ТГ инцидент­ на двум новшл ребрам, т.е. d i V } ~ S/Wt - четна. Связность & следует из iro, что все верганн оодарвдтся в одном цикле ^ * 2. "б" =?• "в". Связность & дана в условии "б". Покажем . что граф & является объединением рабр-^но-непересаквгощихоя проО** TfiDw диклов. Выберем произвольную вершину V и -ачнем обхол 'j рабер о некоторого ребра, инцидентного Щ . Пуоть это будет реб­ ро JC, ^ iiri,vT\. Так как степени вершин четны, то, "войдя" в вершину "Ur rfo однок!у ребру Xf , можно будет "выйти" .13 нее по другому ребру = . Продолжим этот процесс, удаляя пройл дэннне ребра и обрааующиеоя цри этом изолированные вершины. Че­ рез конечное чиоло шагов, в силу конечнооти графа и ввиду TO I 'O, что из вергашя Щ мы уже один раз вышли, ьловь "войдем" в вер­ шину iTi , и.6. получим цикл Х о д ) . Будем считать, что - простой цикл. В противном случае, как это оледует и з §3.1, его мояно дредотавить как объединение реберно-нвпереовкеющихоя ироо'^ тнх циклов. Итак, йоотроен простой цикл Если он оодержйт все ребра (? , то и^^цеоо обхода ребер закончен и утверждение "в" дисазано. В противном случае выберем ребро ^ ^ ВЩ ) , инцидентное Некоторой вериине г/}, бН<1Г, ) . Повторим Опиоаяг- ный процессначиная ив вв1шны . Полечим простой цикл , реберно-нвпврвовкаодййоя о 1 Щ } . Tai-ч образом, в', силу связности и Конечнооти графа, через конетаое число К laroB граф (? будет аредотевлен в виде ^ = Z i l T i ) . Заме- - т- что некоторые и э вершин Vk могут совпадать. 3. "в" =$> "а". Если <у • удовлетворяет условию "в", то на­ чинаем обхсд графа, например, с вершины (рио.10.1). Двигаемся по простому ци^лу ^ (1Ц). Пспав в векоторуя вершину v;;^ , принадде- • жащуя неоколькям простым циклам, нервтодам на новый простой цикл Р и о д о л 2Сг'к) , если есть такая аоянсж- нооть» Очевидно, такой црсцвсо даот возможность посиройть й^е ров цикл в Графе & . Докавенная теорема дает простое и удобноедаяUpaHTinciB уо-• ловив "б" оущеотйованяя эйлерова цшсла в графе,, (мyдьтиppaфв, •^ • • поевдогх^е); В случае псёвдографа при цоссроенйи валерова цик^ ' : ла доела ггопадания в йвкото15>« вершину i T вувнс p 6 o t o вое пвт- 62