作业帮 > 数学 > 作业

我大概翻译了一下 证明 如果G(V,E)是一个强连通有向图,则以下三个性质成立:1.G有一个回路,包含E中所有边2.任何

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/08 13:50:20

我大概翻译了一下
证明 如果G(V,E)是一个强连通有向图,则以下三个性质成立:
1.G有一个回路,包含E中所有边
2.任何两个节点都是互相可达的
3.G中边的集合可以被分解为cycles
(我在国外念书 真的不确定这些英语数学单词中文专业名字应该叫什么。你们参考一下第一条回答吧。不好意思啊。
先翻译一下:
证明如果G(V,E)是一个有向的强连通图,那么下面的几个性质是等价的:
(i)G有一个欧拉路径,即一个包含了G中所有边的闭迹
(ii)V中每个顶点的入度等于出度
(iii)G的边集可以分割成圈
强连通图(Strongly Connected Graph)是指一个有向图(Directed Graph)中任意两点v1、v2间存在v1到v2的路径(path)及v2到v1的路径的图.
闭迹:一条闭路,经过的所有边都不同.(闭路:起点和终点在同一点的路径)
入度:有向图中某点作为图中边的终点的次数之和.
出度:有向图中某点作为图中边的起点的次数之和.
圈(cycle)是指一条除了起点等于终点外,其他的点和边两两相异的路径.
顶点不重复的闭迹称为圈