20.500.12556/RUL-173613 Problem kitajskega poštarja delo diplomskega seminarja The chinese postman problem V delu diplomskega seminarja z naslovom Problem kitajskega poštarja sta predstavljena dva različna primera problema kitajskega poštarja. V prvem delu je obravnavan algoritem za reševanje problema na neusmerjenem grafu, v drugem delu pa algoritem za reševanje problema na usmerjenem grafu. Pri obeh primerih se ukvarjamo s problemom, katere povezave dodati v graf za zagotovitev obstoja Eulerjevega obhoda, pri čemer morajo biti stroški dodanih povezav čim manjši. Za neusmerjene grafe je predstavljen algoritem, ki vozlišča lihe stopnje paroma poveže z najkrajšimi potmi, pri usmerjenem grafu pa je obravnavana Madžarska metoda, ki rešuje problem najcenejšega popolnega prirejanja. Predstavljen je tudi alternativni pristop s problemom razvoza. In this degree titled "The chinese postman problem," two different variants of the Chinese postman problem are presented. The first part deals with an algorithm for solving the problem on an undirected graph, while the second part addresses an algorithm for solving the problem on a directed graph. In both cases, we are concerned with the problem of which edges to add to the graph to ensure the existence of an Eulerian cycle, where the cost of the added edges must be minimized. For undirected graphs, an algorithm is presented that pairs vertices of odd degree via shortest paths, while for directed graphs, the Hungarian method is discussed, which solves the minimum cost perfect matching problem. An alternative approach using the transshipment problem is also presented. problem kitajskega poštarja Eulerjev obhod iskanje najkrajših poti T-spoj prirejanje Madžarska metoda problem razvoza Chinese postman problem Eulerian cycle shortest path problem T-join matching Hungarian algorithm transshipment problem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-19 08:15:05 2025-09-19 08:15:09 2025-09-24 08:40:26 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 153979 250115587 19006.pdf 19006.pdf 1 2E306A664E9A3C0C21CD069AF5C3D1F6 42489cd3d351b8cd89ced0c25cf0f5998fe1e3afddefaa8bfdcbef2afc9070e6 d1f99781-951f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=218219 Fakulteta za matematiko in fiziko 0 0 0