Multimedialne seminarium z ekono- i socjofizyki
sala nr 5, ul. Smyczkowa 5/7
2013-12-03 (18:30)
Tomasz Gubiec (Wydział Fizyki UW)
Pomiędzy grafem pełnym a minimalnym drzewem rozpinającym
Between full graph and minimal spanning tree
Na seminarium odpowiem na pytania: dlaczego ekonofizycy interesują sięteorią grafów? Jakie podgrafy grafu pełnego używane są do opisuukładów złożonych? Dlaczego minimalne drzewo rozpinające stało się aż tak popularne i dlaczego nie jest wystarczające do opisu układów złożonych?Zaproponuję własną rodzinę podgrafów o dowolnie wybranej liczbie krawędzi zawierających minimalne drzewo rozpinające, które mogą być interpretowane jako jego uogólnienie. Przedstawię algorytm generujący wspomniane grafy oraz schemat dowodu jego poprawności.