Studoši

Chet
Ne dopušta mi da pošaljem taj file, ali našao sam ga na Studoši materijalima za NASP. Zove se “NAISP_2019-20_tutorial_zadaci”.
Piše zadaci za godinu 2019/2020, ali ima zadataka sa mnogo godina

tito
Je li tko rjesio ovaj zadatak?
Moze li postat svoje rjesenje ili barem rec koj je rez?

nakon eulerizacije, kad trazimo ciklus u grafu, tj. da dodjemo nazad u pocetku tocku, a da smo svakim bridom prosli samo jednom, to se moze napraviti na vise nacina, zar ne? odnosno, zadatak ima vise od jednog tocnog rjesenja?

Adri ako je rezultantni graf takav da ima više eulerovih puteva, yes, onda ima i više načina kako se taj put ostvaruje (izvan trivijalnih početaka u različitoj točki)

Koji je najbolji video koji objašnjava union find?

Zna li netko što očekuju od nas u b zadatku. Nije mi jasno ovo “crtež nije dovoljan”. Zar to nije doslovno povlacanje crte preko bridova?

stoper5 je doslovno povlacenje crte samo jos napisi koji su to bridovi i njihove tezine

stoper5

Je li minimalni presjek skup bridova od s do t koji sve zbrojeno ima najmanju tezinu ili?

stoper5 Kako se uopce rjesava ovaj zadatak? Po kojem algoritmu se to rješava?

stoper5
ima netko rješenje ovog?

Murin da

Kiflica Ford Fulkerson (na yt upisi max flow min cut)

Murin 4 dana kasno ali ja to sebi ponavljam pa tu pisem… minimalni presjek (najmanji zbroj tezina) ujedno daje i maksimalni flow kroz mrezu, jer ocito ako imas npr. spojene cijevi od 3 L, 5 L i 2 L, kolko god vode utrpali unutra, maksimalno moze proci 2 L. Kad pogledas sve sto izlazi iz pocetnog cvora, to je upper bound koliki ti max flow moze biti, a s min cutom ga zapravo smanjujes dok nedobijes najmanji moguci, to je zapravo najveci flow.

Isto tako, kad presjecas, s i t uvijek moraju biti odvojeni (jedan u jednom skupu, drugi u drugom) i pazi da racunas tezine samo onih bridova koji idu iz “lijevog” (s skup) skupa u “desni” (t skup)

ZI 2019./2020.
Zna li tko kako se ovakav zadatak rješava?

Cvija Pa moraš provesti algoritam, a kako se to konkretno radi, pa nacrtaš graf iz tablice, i onda dodaješ bridove dok ne napraviš zatvarač (na 13.1 prezentaciji 21. slajd). I onda u tom novom grafu nađeš hamiltonov ciklus i napraviš ispis iz a

S tim da ako ti je graf već hamiltonski i nije zatvarač, izgleda da moraš uzeti neki hamiltonski ciklus koji ne opisuje ujedno i originalni graf (znači neki shitniji hamiltonski ciklus XD), to bi se dalo zaključiti po ovoj zadnjoj rečenici.

Cvija imas dobar tutorial na materijalima za taj zadatak, ali evo ti moje rješenje, mozda ti pomogne

zaba Koja je logika za uklanjanje ovih bridova u 3. koraku, nije mi baš jasno. I što je opće poanta tog zadatka? Ovo “Početni odabrani Hamiltonov ciklus mora sadržavati barem jedan brid iz maksimalno proširenog grafa G’” mi je malo zbunjujuće.

Imate li neke dobre tutoriale za ove zadatke:

• pronalazak najvećeg protoka
• kineski poštar
• disjoint-set
• trgovački putnik
• pronalazak Eulerovog ciklusa (pretpostavljam Fleury?)
• pronalazak Hamiltonovog ciklusa (pretpostavljam Bondy-Chvatal?)

Bobicki
Za Fleuryjev algoritam sam pronašao ovaj tutorial koji mi je bio prihvatljiv

Za Bondy-Chvatal algoritam je kolega dao hint da postoji tutorial na materijalima… I ja ga planiram još detaljnije pogledati
https://github.com/studosi-fer/NAISP/blob/master/razno/tutoriali/NAISP_tutorial_bondy-chvatal.docx

Za Kineskog poštara sam ovo pogledao

Za trgovačkog putnika, ova 2-mst heuristika, video mi se čini okej i do osme minute objašnjava ono što je potrebno

Protok još tražim dodatna objašnjenja, ali ovaj video sam već pogledao i intuicija mi je jasnija

Bobicki Što se tiče Dijoint-set, misliš na Union find algoritam?
To je doslovno pratiš algoritam kako ide… Pseudokod algoritma imaš na 37 slajdu prezentacije 11_Grafovi2

Može li netko slikati postupak 1. zadatka ZI 2020 sa simplexom? Pitam za prijatelja

Cvija Pošto ne mogu urediti, mislim da je ovdje došlo do zabune. Algoritam koji se koristi u zadacima je na 31 slajdu, to je onaj sa poljima, na 37 slajdu je sa stablima, možda sam tu pogriješio, ispričavam se na pogrešci.

saitama

Bobicki

member
Evo sad ću proći po algoritmu pa možda bude jasnije

Zadatak od kolege
member
Znači, na početku imamo ovakvo stanje
\begin{bmatrix}root && 1 && 2 && 3 && 4 && 5 && 6 \\ next && 1 && 2 && 3 && 4 && 5 && 6\\ length && 1 && 1 && 1 && 1 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Sad radimo Union(1, 2)
Po algoritmu, xs = root(x) = root(1) = 1
ys = root(y) = root(2) = 2

xs i ys nisu jednaki pa provjeravamo njihove duljine (lenght)
ys nema veću duljinu od xs (obje su 1) pa znači da radimo sljedeći set komandi
length[xs] += length[ys]
root[ys] = xs
svi u polju u kojem je korijen bio ys, za korijen im postavi xs
na kraju zamijeni sljedećeg od xs i sljedećeg od ys
Nakon tog seta operacija se dobije
\begin{bmatrix}root && 1 && 1 && 3 && 4 && 5 && 6 \\ next && 2 && 1 && 3 && 4 && 5 && 6\\ length && 2 && 1 && 1 && 1 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Onda ide Union(4, 3), isto sve
\begin{bmatrix}root && 1 && 1 && 4 && 4 && 5 && 6 \\ next && 2 && 1 && 4 && 3 && 5 && 6\\ length && 2 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nakon Union(2, 3) [xs = 1, ys = 4]:
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 6 \\ next && 3 && 1 && 4 && 2 && 5 && 6\\ length && 4 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Te na kraju nakon Union(1, 6)
\begin{bmatrix}root && 1 && 1 && 1 && 1 && 5 && 1 \\ next && 6 && 1 && 4 && 2 && 5 && 3\\ length && 5 && 1 && 1 && 2 && 1 && 1\\ vertices && 1 && 2 && 3 && 4 && 5 && 6 \end{bmatrix}
Nacrtat se može pomoću ove tablice

Jel samo meni ne radi zadnje predavanje, 1.sat od sredine? Ni treći sat

EDIT: Ma da, Brčić radi. Do Krleže je.

je li možda netko ima postupak uvježbavanje neurona na skupni način, već sam probao scrollat gore kako bi pronašao link na sliku gdje se upravo takav tip zadatka rješavao, ali link više ne radi.

ima netko provjeren ovaj zadatak, na materijalima je sve nesto kaoticno

[obrisani korisnik] Rješavao ga je Brčić na zadnjem predavanju (auditornima).

Kiflica Pogledaj protok u mrežama

Kiflica Ford-Fulkerson