Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 08.06.2004, 13:26   #1
Младенец
 
gevpa's Avatar
 
Join Date: 06 2004
Location: NoWhere
Posts: 4
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default Eileryan cikli goyutyan harcy

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.
Reply With Quote
Old 08.06.2004, 14:15   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Думаю, что для этого требуется, чтобы количество стоков каждой вершины равнялось количеству истоков.
Reply With Quote
Old 08.06.2004, 15:06   #3
Младенец
 
gevpa's Avatar
 
Join Date: 06 2004
Location: NoWhere
Posts: 4
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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
Reply With Quote
Old 08.06.2004, 17:55   #4
Младенец
 
Join Date: 03 2004
Location: US
Posts: 20
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default apacuyc

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.
Reply With Quote
Old 08.06.2004, 18:26   #5
Младенец
 
gevpa's Avatar
 
Join Date: 06 2004
Location: NoWhere
Posts: 4
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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?
Reply With Quote
Old 08.06.2004, 18:43   #6
Младенец
 
Join Date: 03 2004
Location: US
Posts: 20
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

Quote:
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.

Reply With Quote
Old 08.06.2004, 20:36   #7
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Я бы наоборот пошел обратно.
А.И. исходя из неориентированного графа построить доказательство для ориентированого именно заменяя каждое ребо на пару ребер.
Reply With Quote
Old 10.06.2004, 10:41   #8
Младенец
 
gevpa's Avatar
 
Join Date: 06 2004
Location: NoWhere
Posts: 4
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Default

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.
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 04:00.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.