初赛理论4.图论基础

初赛理论4.图论基础的知识，主要内容有连通块:图的里面有一部分都能连通的是一个连通块。非连通图:从一个点出发，个别点不能达到、连通图:从一个点出发，每个点都可以达到、无向图:无方向的图(相当于正反方向都可以走的有向图）、有向图:有方向的图、图:—系列点和边的集合等。

初赛理论 4.图论基础

• 完全图：每两个点之间都有一条边的图是完全图。 如果完全图有n个点，他就有(n-1)+(n-2)+(n-3)+...+1条边.
• 树：有n个点，n-1条边， 并且每个点都可以两两到达的图是树。
• 拓扑排序：起始点必须先于箭头指着的点完成任务。 必须是有向无环图（BAG）才能进行拓扑排序。 入度是指有几个任务做完后才能进行这个任务， 可以理解为有几个箭头指着这个任务。 出度是指做完这个任务后，有几个任务可以选择。 技巧：不断寻找入度为0的点（入度为0的点任务做完 后，可以删除掉，再接着找入度为0的点）
• 连通块：图的里面有一部分都能连通的是一个连通块。
• 非连通图：从一个点出发，个别点不能达到。
• 连通图：从一个点出发，每个点都可以达到。
• 无向图：无方向的图（相当于正反方向都可以走的有向图）
• 有向图：有方向的图
• 图：一系列点和边的集合