跳至內容

圖的字典積

維基百科,自由的百科全書

圖論中,圖GH的字典積是一個圖,使得

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

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