Školjka

Napomena: inducirani graf nekog grafa $G$ po nekom skupu $V$ je graf ciji su cvorevi $V$, te bridovi su svi bridovi iz $G$ koji su u $V \times V$ \\ \\ Neka je: \\ $ f(G) = $ broj poredaka cvoreva takvih da, ako je $(a,b) \in G$, onda se $a$ pojavljuje u poretku prije $b$ ( $G$ je proizvoljan usmjeren graf ) \\ $ A = (\{1, 2, 3\}, \{\}) $ \\ $ B = (\{1, 2, 3, 4\}, \{(1, 3), (2, 3), (2, 4)\}) $ \\ $ C = (\{1, 2, 3, 4, 5, 6, 7\}, \{(1,7), (1,4), (1,3), (2,3), (4,5), (3,5), (3,6)\}) $ \\ $ D = (\{1\}, \{\}) $ \\ \\ Ako su $X$ i $Y$ neka dva proizvoljna grafa sa respektivno $n$ i $m$ cvoreva, definiramo $X \cdot Y$ kao graf $(V, E)$ koji: \\ ima $n+m$ cvoreva $V = \{1, 2, \dots n+m\}$ \\ induciran graf po $\{1, \dots n\}$ je izomorfan $X$ \\ induciran graf po $\{n+1, \dots m\}$ je izomorfan $Y$ \\ $ \{1, \dots n\} \times \{n+1, \dots n+m\} \subseteq E $ \\ \\ Za svaka dva grafa $X$ i $Y$ vrijedi $f(X \cdot Y) = f(X) \cdot f(Y) $ \\ $ f(A) = 6, f(B) = 5, f(C) = 67, f(D) = 1 $ \\ Graf $ R = A \cdot B \cdot C \cdot D^6 $ ima $20$ cvoreva, te $f(R) = 2010$ \\ To jest, $R$ je konstrukcija pjevaca t. d. broj poredaka je tocno $2010$ \\ \\ Nisam nasao nikakvu intuiciju za konstrukciju grafa $C$, brutao sam na racunalu.