跳转到内容

图的字典积

维基百科,自由的百科全书

图论中,图GH的字典积是一个图,使得

  • 其顶点集是笛卡尔积 V(G) × V(H);
  • 其任意两个顶点 (u,v)(x,y) 相邻当且仅当在 Gux 相邻或相同,并且在 Hvy 相邻。

如果两个图的边表示两种偏序关系,那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了,判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。