Композиция графов
(лексикографическое произведение графов) G1=(X1, U1) и G2=(X2, U2) - граф G=G1[G2], состоящий из множества вершин Х=X1?X2, и две вершины s=(x1, x2) и t=(y1, y2) смежны в G тогда и только тогда, когда x1 смежна с y1 или x1=y1 и x2 смежна с y2.