Sparivanje -molim pomoc

[johnny]

Moze li mi netko molim vas pomoci i prodiskutirati ovaj zadatak sa roka 20.6.2005.


Treba odrediti maximalno sparivanje i odgovoriti postoji li maksimalno sparivanje koje sadrzi jedinicu na mjestu (7,2)


Dana matrica susjedstva je 1 1 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 1
0 1 1 1 0 0 0 0
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 1 1 0 0
gdje je pocetno sparivanje boldano.
e sad ako krenem standardnim algoritmom dakle, trazim put prosirenja od x5 onda dobivam lanac x5-y2-x1-y1-x6-y7-x2-y3-x4-y4 .no postoji i mogucnost da kad dodjem do x4, da ne idem na y4 vec na y2-x1-y1...itd. pa dobivam nesto kao ciklus
Zapravo moje je pitanje da li da tu mogucnost jednostavno zanemarim i onda mi je ovaj prvi lanac prosirenja novo sparivanje tj. cak i maximalno ili sam ja u svemu tome nesto krivo razumio...?
Unaprijed zahvaljujem

[Grga]

Ovako na prvi pogled, ne mozes dobiti x6-y7 jer je tamo 0

_________________
Bri

[Ignavia]

i meni se tako cini, malo mi se mute te jedinice i nule...
ne razumijem sto te tocno muci? isprobas sve puteve prosirenja i ako ne postoji vise ni jedan, to je to. mozda je nekad lakse pretpostavit da si pronasao maksimalno sparivanje i ne isprobavat dalje (ak ti se tak cini od oka) i onda ako nadjes minimalni pokrivac sa tim brojem linija, sve je super, tj. tvoje sparivanje je stvarno maksimalno

nakon sto odredis maksimalno sparivanje, maknes 7. redak i 2. stupac i na toj, novoj matrici, ponovno odredjujes max sparivanje. ako je ono za 1 manje od onog u pocetnoj matrici, onda postoji max sparivanje koje sadrzi jedinicu na mjestu (7,2), u suprotnom (ako je za 2 manje) ne. Ako ti se dogodi da je jednako, onda nisi dobro odredio max sparivanje u pocetnoj matrici (ili si fulao u 2.). hmmm. razumijes? zato sto kad dodas nazad taj redak i stupac, sparivanje ti je automatski za 1 vece... (u pocetnoj) jooj... najbolje da se mi nadjemo na jednoj kavici
ispricavam se zbog ovog kaosa, razumjet cu ako mi spustis karmu

_________________
moj prostor

[johnny]

Hvala to je pomoglo no jos uvijek me zbunjuje ovaj put prosirenja:
Ako idem iz x5-y2-x1-y1-x6-y7-x2-y3-x4-y2-x1-y1-x6-y7-x2-y3....tada mi lanac ne zavrsava vec dobivam nesto kao beskonacnu petlju jer mi put nigdje ne zavrsava, nego se samo vrti u krug ponavljajuci iste puteve tj.dobivam da se lanac ponavlja, pa me zanima sta radim krivo
Sto se karme tice....pa nisam tolko zao

[koryanshea]

[johnny]

Zahvaljujem na pomoci! Nazalost krivo sam prepisao zadatak ali u međuvremenu skuzih sparivanja