Koalicijski grafi poti in ciklovZupan, Marjetka (Avtor) Klavžar, Sandi (Mentor) razdelitev množice vozliščdominantna množicakoalicijakoalicijska razdelitevkoalicijski grafKoalicija v grafu $G = (V(G), E(G))$ je par nedominantnih disjunktnih množic $V_1 \subseteq V(G)$ in $V_2 \subseteq V(G)$, katerih unija $V_1 \cup V_2$ je dominantna množica grafa $G$. Koalicijska razdelitev grafa $G$ je takšna razdelitev vozlišč $\pi = (V_1, V_2, \ldots, V_k)$, da je vsaka množica $V_i \in \pi$ bodisi dominantna in sestavljena iz enega vozlišča (stopnje $|V(G)| - 1$) bodisi nedominantna in tvori koalicijo z neko drugo nedominantno množico $V_j \in \pi$. Koalicijski graf grafa $G$ glede na koalicijsko razdelitev $\pi$ je graf $CG(G, \pi)$, ki ima za vozlišča množice $V_1, \ldots, V_k \in \pi$, vozlišči pa sta sosednji natanko tedaj, ko pripadajoči množici $V_i, V_j \in \pi$ tvorita koalicijo. V tem delu bomo opredelili koalicijske grafe poti in ciklov. Pokazali bomo, da je teh le končno mnogo, in natančno določili, kateri grafi so to.20242024-09-08 08:15:19Delo diplomskega seminarja/zaključno seminarsko delo/naloga161233sl