万博体育manbetx这样的一个映射m称之为一个同构

当前位置:万博体育manbetx > 万博体育manbetx > 万博体育manbetx这样的一个映射m称之为一个同构
作者: 万博体育manbetx|来源: http://www.hljmtgd.com|栏目:万博体育manbetx

文章关键词:万博体育manbetx,同构图

  图论当中的术语,假设G=(V,E)和G1=(V1,E1)是两个图,如果存在一个双射m:VV1,使得对所有的x,yV均有xyE等价于m(x)m(y)E1,则称G和G1是同构的,这样的一个映射m称之为一个同构,如果G=G1,则称他为一个自同构。

  如图3.6,第一个图形和第二个图形的区别在于环的数量。第一个图形为一个环,第二个为两个环,万博体育manbetx所以不是同构图。

  若删去z1和u1,删去v1和w1,连接z1和w1,成为一个v1u1的链和z1w1x1y1的环,依旧不是同构图,因为必须环数相同,链数相同。

  但这还是缺少一个条件,比如图形A存在两个环a1和a2,a1有3个结点,a2有5个结点,图形B也有两个环,b1有4个结点,b2有4个结点,依旧不是同构图,这里的条件就是环上或链上的借点数相同,和结点顺序无关。

  引入例题,HDU3926-Hand in Hand,判断两次组成的图形是否是同构图。

  思路之一:通过并查集确定环数/链数,和环内/链内的人数,再排序进行比较。

  排序时按照人数排序,若人数相同要按照状态排序。注意这几点或许会比较容易过。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!