圖的字典積

在圖論中，圖G和 H的字典積是一個圖，使得

• 其頂點集是笛卡爾積 V(G) × V(H);
• 其任意兩個頂點 (u,v) 和 (x,y) 相鄰若且唯若在 G 中 u 與 x 相鄰或相同，並且在 H 中 v 與 y 相鄰。

如果兩個圖的邊表示兩種偏序關係，那麼它們的字典積的邊就表示其對應的字典序。 Felix Hausdorff於1914年首次研究了字典積。Feigenbaum 與 Schäffer於1986年證明了，判別圖是否為字典積的問題在複雜性上與判別圖是否同構的問題等價。