图的字典积 |
您所在的位置：网站首页 › 字典index › 图的字典积 |
|
此條目没有列出任何参考或来源。 (2021年9月29日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。
此條目可参照英語維基百科相應條目来扩充。若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。
在图论中，图G和 H的字典积是一个图，使得 其顶点集是笛卡尔积 V(G) × V(H); 其任意两个顶点 (u,v) 和 (x,y) 相邻当且仅当在 G 中 u 与 x 相邻或相同，并且在 H 中 v 与 y 相邻。如果两个图的边表示两种偏序关系，那么它们的字典积的边就表示其对应的字典序。 Felix Hausdorff于1914年首次研究了字典积。Feigenbaum 与 Schäffer于1986年证明了，判别图是否为字典积的问题在复杂性上与判别图是否同构的问题等价。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |