Eileryan cikli goyutyan harcy

[gevpa]

Vorpesi voroshenq, te grafum gojutjun uni ardjoq eilerjan cikl, anhrajesht ! yev bavarar, vor na lini kapakcvac yev nra kamayakan gagati astichany lini zujg, bayc sa voch orientacvac grafi depqum.
Ete inch vor meky giti, voreve anhrajesht ev bavarar payman orientacvac grafum eileryan cikli goyutyan hamar, greq.

[Agregat]

Думаю, что для этого требуется, чтобы количество стоков каждой вершины равнялось количеству истоков.

[gevpa]

Indz el a tenc tvum, bayc es chem karoxanum formal apacuyc tal, chnayac chem gtnum nayev kontr orinak. Du da hastat gites, te uxxaki krahum es

[Tranquilizer]

Nax, apacucum enk kapakcvac grafneri hamar (teche karas unenas izolacvac gagatner voronk voch mi der chxaghan cikli karucman mej).

Erkrordy, apacucum enk aveli yndhanur pndum aynpisi grafneri hamar, voroncum kamayakan erku gagat karan miacvac linen aveli kan mek koghov. Tenc stacvec hima Es yndhanur depkum aveli hesht a apacuyc tal.

Cikl aselov haskanank gagat-kogh-gagat-kogh...-gagat teski shxta, vortegh verji u araji gagatnery hamnknum en. E shxtanery kareli a patkeracnel sharvac shrjani vra, u cankacac elementi hamar sahmanel aj harevan u dzax harevan.

Hima, anhrazheshtutiuny:
Unenk Ejlerian cikl => (yst sahmanman) sagh koghery masnakcum en => (kapakcvac e) sagh gagatnery masnakcum en => (ete sharenk cikly shrjani vra) grafi amen gagat uni ajnkan dzax harevan vorkan el aj harevan, bnakanabar => amen gagat inchkan kogh mtnuma etkan el durs a galis.

Bavararutiuny:
n - gagatneri kanaky
n=1 i hamar aknhajt a (inchpes najev n=2-i hamar)
Entadrenk n i hamar apacucvac a, apacucenk n+1 i hamar.
Yntrenk kamajakan gagat, poxarinenk mer grafum (gagat1->kogh1->yntrac gagat->kogh2->gagat2) teski bolor shxtanery (gagat1->nor kogh->gagat2) teski shxtanerov. Stacank n gagatani graf, mer bolor paymannerin noric bavararogh, vorum yst entadrutian ka Ejlerian cikl. Et ciklum bolor nor avelacrac shxtanery (voronk bolorn el masnakcum en) poxarinelov hinerov, kstanank Ejlerian cikl mer hin n+1 gagatani grafum.

[gevpa]

Ete chisht apacuycid erkrord kesy lav chhaskaca, bayc mersi.
Lucumy gtel em. Hetaqrqvochnery karox en nayel`
Теорема 3.1.3 из "Теории графов" О. Оре

Isk orinak inch karajarkeq ajn grafi hamar, vorum kan ev orientacvac ev voch orientacvac kogher?

[Tranquilizer]

Originally Posted by gevpa

Ete chisht apacuycid erkrord kesy lav chhaskaca, bayc mersi.
Lucumy gtel em. Hetaqrqvochnery karox en nayel`
Теорема 3.1.3 из "Теории графов" О. Оре

Isk orinak inch karajarkeq ajn grafi hamar, vorum kan ev orientacvac ev voch orientacvac kogher?

De vor konkret ases inchy chhaskacar, manramasn kbacatrem.
Naji, indukcia enk anum gagatneri kanakov.

Unenk graf, gitenk vor amen gagat inchkan kogha mtnum etkan el durs a galis. Petka cujc tank vor ka Ejlerian cikl, che?

Erku gagati depkum parza? Ha. Menk kani vor yndlajnvac grafner enk najum, yndhanrapes asac erku gagati depky hetevjaln a: mi gagatic mjusin m hat kogh a gnum, en mjusic el sran m hat kogh a galis. Parza che cikly vonc kkarucvi? Gnum es, het es galis, u tenc m angam.

Hima n gagati depky entadrenk vor unenk. n+1 gagati hamar inch enk anum?
Petk a berenk n gagati depkin. Vercnum enk mi hat cankacac gagat, u hanum enk. Bajc hanum enk iran kpac kogherov. Isk vorpeszi grafi himnakan paymany chxaxtvi, et hanac gagati u kogheri teghy iranc "ekvivalent" kogher enk avelacnum. Asenk hanel enk X gagaty. Iran kpac kogherov. Ete A gagaty minchev et kpac er X-in koghov, X-n el B-in, hima kavelacnenk prosto A-ic B tanogh kogh. Parza?

Hima et taza stacvac grafy n-gagatani grafa, vor en mer pajmanin bavararum a, vor inchkan kogh ur mtnuma etkan el durs a galis. Dra hamar es grafum ka Ejlerian cikl. Isk stegh hima en nor avelacrac koghery hima noric ktrohenk, asenk A-ic B koghy noric kpoxarinenk A-ic X u X-ic B kogherov, vory klini arden mer Ejlerian cikly skzbnakan grafi hamar.

Hujsov em parza..

Isk en grafy vorum kan voch orientacvac kogher. De cankacac voch orientacvac kogh karas poxarines erku hat orientacvacov, u sagh kbervi es xndrin.

[Agregat]

Я бы наоборот пошел обратно.
А.И. исходя из неориентированного графа построить доказательство для ориентированого именно заменяя каждое ребо на пару ребер.

[gevpa]

To Tranquilizer,

Algoritmy najeci chisht a!!!

Bajc voch orientacvac koghy ete pogharinenq erku agheghov, petq a miayn mekov ancnenq, aysinqn chi galis koghmnoroshvac grafi depqin. Orinak`
unenq 4 gagatani graf, vory parunakum a yev orientacvac yev voch
orientacvac kogher.
orientacvac koghern en` (1,2) (3, 4) (4, 1)
voch orientacvac koghern en` (2, 3)
Ays grafum eyleryan cikl goyutyun uni` 1-2-3-4-1
Bayc ete (2, 3) - y pogharinenq ` (2, 3) yev (3, 2) kogherov, apa mer stacvac grafum arden goyutyun chi unena eyleryan cikl.