视频字幕
有向图是图论中的重要概念,它由顶点集合和有向边集合组成。与无向图不同,有向图的每条边都有明确的方向,从一个顶点指向另一个顶点,这样的边称为有向边或弧。在有向图中,顶点的度数分为入度和出度:入度是指向该顶点的边数,出度是从该顶点出发的边数。由于边的方向性,有向图中的邻接关系具有非对称性,即如果顶点A指向顶点B,并不意味着B也指向A。
在有向图中,每个顶点都有两个重要的度数概念:入度和出度。入度是指向该顶点的边数,出度是从该顶点出发的边数。顶点的总度数等于入度加出度。有向图中有一个重要的握手定理:所有顶点的入度之和等于所有顶点的出度之和,且都等于图中边的总数。这是因为每条有向边都有一个起点和一个终点,所以总的出度数等于总的入度数。度数序列是描述图结构的重要工具,它包含了所有顶点的度数信息。
欧拉有向图是图论中的重要概念,它涉及欧拉路径和欧拉回路在有向图中的存在性。对于有向欧拉路径,存在的充要条件是:除了起点和终点外,其他所有顶点的入度都等于出度;起点的出度比入度多1,终点的入度比出度多1,且图必须是弱连通的。对于有向欧拉回路,存在的充要条件更加严格:所有顶点的入度都必须等于出度,且图必须是强连通的。在这个例子中,我们展示了一个满足欧拉回路条件的有向图,每个顶点的入度和出度都相等,形成了一个完整的欧拉回路。
强连通图是有向图中的重要概念,它要求图中任意两个顶点之间都存在有向路径。这比弱连通的要求更严格,弱连通只需要忽略边的方向后图是连通的,而强连通必须在考虑边方向的情况下仍然连通。强连通分量是指图中最大的强连通子图,每个强连通分量内的顶点都可以相互到达。在这个例子中,我们可以看到图被分解为三个强连通分量:顶点A和B形成一个强连通分量,因为它们之间有双向路径;顶点C和D形成另一个强连通分量;顶点E单独形成一个强连通分量。判定强连通性可以使用Kosaraju算法或Tarjan算法等经典算法。
竞赛图是图论中一类特殊的有向图,它是完全有向图,即任意两个不同顶点之间恰好有一条有向边。竞赛图在现实中有广泛应用,比如体育比赛的排名系统、选举投票系统和偏好排序等。竞赛图有两个重要的性质:首先,任何竞赛图都存在哈密顿路径,也就是说总能找到一条路径访问每个顶点恰好一次;其次,如果竞赛图是强连通的,那么它还存在哈密顿回路。在这个四个顶点的竞赛图例子中,我们可以看到每对顶点之间都有且仅有一条有向边,并且我们成功构造了一条哈密顿路径A到C到B到D,验证了竞赛图的重要性质。