构成无向简单图的条件是什么

发布网友发布时间：2022-04-22 02:56

共2个回答

热心网友时间：2023-07-08 19:46

没有平行边且无环的无向图。

在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。含平行边的图称为多重图，既不含平行边也不含环的图称为简单图。

扩展资料

对于一个无向图来说，如果它是连通的，那么它的任意两个顶点之问必存在一条路径，因此，通过这一路径可从一个顶点“到达”另一个顶点，若从顶点“可以到达u，则从u也可以到达“，也即v和u之间是互相可以到达的。

对于有向图，情形就不同，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。设D是一个有向图，且u、v∈D，若存在从顶点u到顶点v的一条路径，则称从顶点v到顶点u可达。

可达的慨念与从u到v的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。

可达性为一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。

参考资料来源：百度百科-有向图

参考资料来源：百度百科-非简单图

热心网友时间：2023-07-08 19:46

无向简单图就是指，没有自环、没有平行边的无向图。满足 |E| <= |V| (|V|-1) /2。还有问题请补充，满意请采纳。