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