Neodvisno število Kneserjevega grafaGregorič, Ajda (Avtor) Oblak, Polona (Mentor) neodvisna množicaneodvisno številoneodvisni količnikKneserjev grafpresečne družineErdős-Ko-Radojev izrekgrafi Kneserjevega tipaKneserjev 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.20252025-08-21 12:30:00Diplomsko delo/naloga171264sl