Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Maximum matching

[es] :: Art of Programming :: Maximum matching

[ Pregleda: 2278 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

stf

Član broj: 51276
Poruke: 65
*.171.eunet.yu.



Profil

icon Maximum matching25.04.2006. u 16:45 - pre 218 meseci
Pre jedno mesečak dana sam uradio na USACO-u neki zadatak sa mečinzima. Ja sam radio preko Network Flow-a što se prošlo relativno brzo, ali sam posle našao na onom njihovom forumu da postoji neko brže rešenje. E sad, zanimaju me dve stvari:

1) Postoji li neki drugi način za rešavanje Maximum matching-a, a da nije preko Network Flow-a?

2) I još nešto: Koliko sam primetio, ako se rešavaju mečinzi ovako kako sam ja radio moguće je samo odrediti koliko iznosi maksimalan broj čvorova, ali ne i koji čvorovi su povezani kojom ivicom u tom mečingu. Pa me zanima kako se to određuje...

P.S. Ovo se sve odnosi na biparitne grafove!

Pozdrav,
Boneli
If you don't live for something, you will die for nothing.
 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.



Profil

icon Re: Maximum matching25.04.2006. u 20:27 - pre 218 meseci
Pa kada napravish rezidualnu mrezu grafa, one grane koje su tezine 0 pripadaju mechingu.

A sto se tiche drugih metoda za odredjivanje, imash u top temu Srdjanov maturski rad na tu temu ...
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.151.eunet.yu.



Profil

icon Re: Maximum matching25.04.2006. u 21:22 - pre 218 meseci
Gledao sam taj maturski rad i pogledaću još po nekim linkovima za ove druge metode.

Ali za ovo drugo: Lako je meni da zaključim koji svi čvorovi pripadaju mečingu, ali ne znam kako da odredim (kad nađem Maximum matching) za svaki čvor iz jednog dela grafa (jedne bipatricije) sa kojim je čvorom sparen iz drugog dela grafa...

---------------------------------------
Kasnije:

Citat:
Pa kada napravish rezidualnu mrezu grafa, one grane koje su tezine 0 pripadaju mechingu.


Nisam isprva ni lepo pročitao šta si napisao.
Sad sam ovo isprobao na primeru i radi.
Hvala ti, pozz!

[Ovu poruku je menjao stf dana 26.04.2006. u 07:23 GMT+1]
If you don't live for something, you will die for nothing.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.net.t-com.hr.

Sajt: www.dump.hr


Profil

icon Re: Maximum matching26.04.2006. u 09:05 - pre 218 meseci
Dali je to "Maximum bipartite matching" ?
Jeli mogu ikako doci do tog maturskog?
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.156.eunet.yu.



Profil

icon Re: Maximum matching26.04.2006. u 10:59 - pre 218 meseci
Citat:
Dali je to "Maximum bipartite matching" ?

Da, to je to.

Citat:
Jeli mogu ikako doci do tog maturskog?

Pogledaj top temu i tamo gde su ''Uparivanja'' imaš u attachment-u.
If you don't live for something, you will die for nothing.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.net.t-com.hr.

Sajt: www.dump.hr


Profil

icon Re: Maximum matching26.04.2006. u 20:42 - pre 218 meseci
thx
 
Odgovor na temu

[es] :: Art of Programming :: Maximum matching

[ Pregleda: 2278 | Odgovora: 5 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.