Naslov
Pfaffijan i savršena sparivanja
(The Pfaffian and perfect matchings)

Autori
Granić, Karla

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Prirodoslovno-matematički fakultet

Mjesto
Zagreb

Datum
28.02

Godina
2020

Stranica
35

Mentor
Krčadinac, Vedran

Ključne riječi
savršeno sparivanje ; Pfaffijan ; determinanta
(perfect matching ; Pfaffian ; determinand)

Sažetak
U ovom radu obradili smo savršena sparivanja u grafu i Pfaffijan antisimetrične matrice. U početku upoznajemo definiciju savršenog sparivanja i rezultate koji su nam potrebni za ostatak rada. Nakon toga pokazujemo kriterij za egzistenciju savršenog sparivanja u bipartitnom grafu i u proizvoljnom grafu. Opisujemo probabilistički algoritam koji pitanje egzistencije savršenog sparivanja rješava u polinomijalnom vremenu. Zatim utvrđujemo da permanenta matrice bisusjedstva bipartitnog grafa broji sva savršena sparivanja, međutim izračunavanje permanente je #P-potpun problem za kojeg nije poznat polinomijalni algoritam. U zadnjem dijelu rada obrađujemo Kasteleynov rezultat da u planarnom grafu možemo efikasno prebrojati sva savršena sparivanja, i to preko Pfaffijana antisimetrične matrice susjedstva grafa kojeg smo orijentirali na odgovarajući način.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA