图的字典积
外观
![]() | 此条目可参照英语维基百科相应条目来扩充。 若您熟悉来源语言和主题,请协助参考外语维基百科扩充条目。请勿直接提交机械翻译,也不要翻译不可靠、低品质内容。依版权协议,译文需在编辑摘要注明来源,或于讨论页顶部标记 {{Translated page}} 标签。 |
在图论中,图G和 H的字典积是一个图,使得
如果两个图的边表示两种偏序关系,那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了,判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。