20.500.12556/RUL-153059 Inverzije permutacij, permutacijski grafi in tekmovalnostni grafi Inversions of permutations, permutation graphs and competitivity graphs V diplomski nalogi si najprej ogledamo inverzije permutacij, njihove lastnosti, rodovno funkcijo za število permutacij množice [n] z i inverzijami in Bruhatovi delni urejenosti. Nato pokažemo, kako predstavimo permutacije s permutacijskimi grafi, karakteriziramo permutacijske grafe s pomočjo kohezivnega zaporedja vozlišč, pokažemo, da so gosenice edina drevesa, ki so permutacijski grafi, ter pokažemo, da za vsako gosenico obstajata natanko dve permutaciji, ki generirata permutacijski graf izomorfen tej gosenici. Potem si ogledamo, kaj so tekmovalnostni grafi, množice tekmovalcev, množice posrednih in neposrednih tekmovalcev ter algoritem za izračun množic posrednih in neposrednih tekmovalcev, ki ne potrebuje konstrukcije tekmovalnostega grafa. Na koncu uporabimo algoritem na primeru z resničnimi podatki. In the thesis, we first examine inversions of permutations, their properties, the generating function for the number of permutations of the set [n] with i inversions, and Bruhat partial orders. Then, we present how permutations can be represented with permutation graphs and characterize permutation graphs using a cohesive vertex-set order. We show that caterpillars are the only trees that are permutation graphs, and prove that for every caterpillar graph, there are exactly two permutations that generate a permutation graph isomorphic to the caterpillar. Next, we explore competitivity graphs, sets of competitors, sets of eventual competitors, and an algorithm to calculate the sets of eventual competitors that does not require the construction of a competitivity graph. Finally, we apply the algorithm to a concrete example featuring real-world data. permutacije inverzije permutacij rangiranja permutacijski grafi tekmovalnostni grafi permutations inversions of permutations rankings permutation graphs competitivity graphs true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2023-12-15 12:50:02 2023-12-15 12:50:07 2024-09-18 14:45:14 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37194 178802691 Uranic_Luka_-_Inverzije_permutacij,_permutacijski_grafi_in_tekmovalnostni_grafi.pdf Uranic_Luka_-_Inverzije_permutacij,_permutacijski_grafi_in_tekmovalnostni_grafi.pdf 1 CF4383A7FC4460FBCF4D2A3E758A0364 7e8922b07ca38b9dd49458023353d68706ee905a9fc37a8a60aa5aaf0a7b20d6 18bc7920-9b40-11ee-bebf-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=178856 Fakulteta za računalništvo in informatiko Fakulteta za matematiko in fiziko 0 0 0