20.500.12556/RUL-171264 Neodvisno število Kneserjevega grafa Independence number of Kneser graph Kneserjev graf K (n,k) je graf, katerega vozlišča so vse podmnožice moči k množice {1,2,..., n}. Dve vozlišči v grafu sta sosednji natanko tedaj, ko sta množici, ki ju predstavljata vozlišči, disjunktni. V diplomskem delu definiramo neodvisno množico, neodvisno število in neodvisni količnik grafa. Ogledamo si, na kakšen način lahko najdemo neodvisno število v splošnem grafu in definiramo problem iskanja največje neodvisne množice. Nato definiramo Kneserjeve grafe in preučimo, kaj so njihove neodvisne množice. Navedemo in dokažemo Erdős-Ko-Radojev izrek, ki poda zgornjo mejo za moč neodvisnih množic Kneserjevih grafov. Nato pokažemo, da v vsakem Kneserjevu grafu obstaja neodvisna množica, katere moč je enaka tej zgornji meji. Na podlagi tega določimo neodvisno število in neodvisni količnik Kneserjevega grafa. V nadaljevanju definiramo grafe Kneserjevega tipa, ki so posplošitve Kneserjevih grafov in na njihovi osnovi zapišemo alternativno definicijo Kneserjevih grafov. Na koncu navedemo in dokažemo izrek, ki poda spodnjo mejo za neodvisni količnik grafa Kneserjevega tipa. Ugotovimo, da je za Kneserjeve grafe spodnja meja iz izreka enaka njihovim neodvisnim količnikom. Kneser graph is a graph whose vertices are the subsets of {1,2,..., n} with k elements, two of them being adjacent if the corresponding subsets are disjoint. In the thesis, we define independent set, the independence number of a graph and the independence ratio of a graph. We explore how the independence number can be determined in any graph and define the maximum independent set problem. We then define Kneser graph and examine its independent sets. We present and prove the Erdős-Ko-Rado theorem, which gives an upper bound on the size of an independent set in Kneser graph. We show that this bound can always be met, which allows us to determine the independence number and independence ratio of Kneser graph. Further, we define Kneser-type graphs, which generalize Kneser graph, and, based on these, we offer an alternative definition of Kneser graph. Finally, we state and prove a theorem that establishes a lower bound on the independence ratio of Kneser-type graph. We show that in Kneser graph the lower bound from the theorem is equal to its independence ratio. neodvisna množica neodvisno število neodvisni količnik Kneserjev graf presečne družine Erdős-Ko-Radojev izrek grafi Kneserjevega tipa independent set independence number independence ratio Kneser graph intersecting families Erdős-Ko-Rado theorem Kneser-type graphs true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-08-21 12:30:00 2025-08-21 12:30:05 2025-09-03 06:02:16 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 38013 247438083 Gregoric_Ajda_-_Neodvisno_stevilo_Kneserjevega_grafa.pdf Gregoric_Ajda_-_Neodvisno_stevilo_Kneserjevega_grafa.pdf 1 7B9CCAB928E20A69EAF01A87094F65EB 38e7128ff914cebaf0971747b28f8f87ceb0f7b9bda866118a33a269d58aa81e b2bee4d7-7e79-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=214465 Fakulteta za računalništvo in informatiko 0 0 0