图论基础
图论基础——小白系列
图论是信息竞赛中最为博大精深的一部分，在各种比赛和各类试题中得到了广泛的应用。
今天我们来介绍一下学习图论需要了解的基础内容
概念
什么是一张图？
就是像这样
圆圈代表“点”，线代表“边”，多个点由几条边连起来就是图
特别的，如果一张图中每两个点之间恰好有一条边相连，我们便称之为“完全图”
有同学也许会问，什么叫“恰好有一条边”？难道还要多条边的情况？
诶还真有，当两个点之间有两条或两条以上的边直接相连时，
我们称之为“重（chong）边”
像这样
有点丑…表介意
有些时候，题目会说图中边具有边权
那么什么是边权呢？
其实边权就是说经过这条边到达其他点所需要付出的代价或是对答案进行的贡献
简单理解为这条边的“长度”
点权也是一样的道理
有向图
什么是有向图？
就是说这个图中的边带了方向
比如这样
和上面我们举的无向图不同
在这个图中，边的箭头代表的边的指向，也就是方向
这就意味着从1号点出发可以到达2号和3号点，但不能到4号点。而从4号点出发可以到达1 号点
负边
很简单，当一个边的边权为负数时我们称之为“负边”
环
什么是环？
在一个图中，从某个点出发不经过相同的边回到自己，这时它走的路线就是一个环
无向图的环：
有向图的环：
注意，这样的有向图并不是环，在一个环上，任意一点都可以到达环中的其他点
下面这个图显然做不到这点
度
在一个有向图中，一个点引出去的边的数量，是这个点的出度，而指向这个点的边的数量，是这个点的入度
看下图
在这张图中，1号点的入度为3，出度为2
而在一张无向图中，并没有出入边之分，所以我们把一个点所连的边的数量称为这个点的度
1号点的度为3，4号点的度为2
其实学习图论要懂的基础知识就这么多，当然还有些特殊概念我在此没有提及
当我们学到对应算法时我会进行介绍
实际上学习一种新的算法需要的不是你的头脑有多么聪明，而是在于你是否有一颗肯坚持的心
就像某位大神说的，只要你有那个方向的分运动，你就会朝那里越来越近
之后我们会从简单到复杂给大家陆续介绍图论中各种有趣的算法
谢谢大家的支持