|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [讨论]请教：能否用相邻矩阵判断两个图同构？ (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=39279) |
|
-- 作者：wildzeven -- 发布时间：10/24/2006 8:28:00 PM -- [讨论]请教：能否用相邻矩阵判断两个图同构？ 看书时想到这个问题，是否存在：两图同构<=>它们的相邻矩阵通过初等行（或列）变换后相等？ 两个图同构的话它们的相邻矩通过初等行（列）变换后必定可以相等（当然这个初等变换仅限于行与行（或列与列）之间的互相交换），那么两个图的相邻矩阵经过初等行（列）变换后相等呢，能否推出两图同构？不成立的话，怎么找一个反例？ 另外我对同构的一个浅显理解是：就是其实两图可以画成同一个图，不知这个理解是不是显得不太严谨？恳请高手们不吝赐教，多谢。 |
|
-- 作者：Logician -- 发布时间：10/24/2006 8:54:00 PM -- Q: 两图同构<=>它们的相邻矩阵通过初等行（或列）变换后相等？ A: 对。 Q: 我对同构的一个浅显理解是：就是其实两图可以画成同一个图，不知这个理解是不是显得不太严谨？ [此贴子已经被作者于2006-10-25 15:56:31编辑过]
|
|
-- 作者：wildzeven -- 发布时间：10/28/2006 11:30:00 PM -- 多谢版大回复～ 仔细想了一下，我觉得这个相邻矩阵变换的时候还得行和列同时变，即假如某两行交换了则对应的列也得交换，否则最后行与列对应的顶点就不一致了。是不是这样？如果是这样看起来用这个来判断两图同构还是显得比较烦琐～ |
|
-- 作者：Logician -- 发布时间：10/29/2006 12:20:00 AM -- 是的。 所以目前并没有找到判断两个图是否同构的多项式时间算法（以顶点数n作为输入规模）。 |
|
-- 作者：hanfengcpc -- 发布时间：12/27/2007 12:04:00 AM -- 请问，有现成的程序算法吗？ |
|
-- 作者：teng_t1986 -- 发布时间：12/27/2007 9:32:00 AM -- 这是NP完全问题…… |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
265.625ms |