有向图的正方形
是的，这将是一项家务（我自学不是大学）问题，但我不是要求解决方案。 相反，我希望澄清这个问题本身。
在CLRS第3版，第593页中，删去了22.1-5，
有向图G =（V，E）的平方是当且仅当G包含至多有两个路径的图G ^ 2 =（V，E ^ 2）使得（u，v）∈E ^ 2。 u和v之间的边描述用于从G的邻接表和邻接矩阵表示中计算G2的有效算法。分析算法的运行时间。
但是，在CLRS第2版（我无法再找到该书链接）中，第530页，同样的消费品，但略有不同的描述：
有向图的平方G =（V，E）是图G ^ 2 =（V，E ^ 2）使得（u，w）∈E ^ 2当且仅当某些v∈V时， u，v）∈E和（v，w）∈E.也就是说，G ^ 2包含u和w之间的一条边，只要G包含一条具有u和w之间正好两条边的路径。 描述G的邻接列表和邻接矩阵表示的G中计算G ^ 2的高效算法。分析算法的运行时间。
对于“正好具有两条边”的旧税号，我可以理解并且可以解决它。 例如，对于邻接表，我只是做v-> neighbour-> neighbour.neighbour，然后把（v，neighbour.neighbour）添加到新的E ^ 2中。
但对于“最多两条边”的新消费税，我感到困惑。
“当且仅当G包含u和v之间至多两条边的路径”意味着什么？
由于一条边可以满足条件“最多两条边”，如果u和v只有一条只包含一条边的路，我应该把（u，v）加到E ^ 2上吗？
如果u和v有一条有2条边的路径，但也有3条边有另一条路，我可以将（u，v）加到E ^ 2上吗？
是的，这正是它的意思。 E^2应包含(u,v)当且仅当E包含(u,v)或有w在V ，使得E同时包含(u,w)和(w,v)
换句话说， E^2根据新定义是联盟E和E^2根据旧的定义。
关于你的最后一个问题： u和v之间存在什么其他途径并不重要（如果他们这样做）。 所以，如果u和v之间有两条路径，一条有两条边，一条有三条边，那么(u,v)应该在E^2 （根据这两个定义）。
由d（u，v）<= 2的那些顶点V'和G ^ 2的边G'定义的图G，G ^ 2的平方是G的所有那些边，其具有从V “
链接地址: http://www.djcxy.com/p/65285.html