一起学习图论

​最近在学习图论，所以打算写一下图论的浅显概念。

一、起源

普瑞格尔河从古城哥尼斯堡市中心流过，河上筑有七座古桥,如图1.1（a）。

1736年，一位数学者向数学家Euler提出这样的问题：从家里出发，七座桥每桥恰通过一次，再回到家里，是否可能？后来Euler对问题进行抽象和论证，如图1.1（b）,从而得到否定的答案，由此开创了图论的元年。

二、基本概念

称一个数学结构G={V,E}，其中V是顶点集合，E是边长的集合。若e属于E,（u,v）属于V×V，则简写为e=uv;我们称u是有向边的尾，v是有向边的头。

把顶点u与v这两点用箭头从u指向v的一条有向曲线连接起来,此曲线的长短与曲直不加考虑，我们称这样的图为有向图（图2.1所示）。当把图2.1的箭头都去掉的话，那么得到的是一个无向图。

我们给出以下定义：

（1）边的端点：e=wv时,称顶u与v是边e的端点。

（2）边与顶相关联：若边e的端点是u与v,则称e与u，v相关联。

（3）邻顶：同一条边的两个端点叫做邻顶。

（4）邻边：与同一个顶相关联的两条边叫做邻边。

（5）环：只与一个顶相关联的边叫做环。

（6）单图：无环无重边的图.

三、一类图

完全图：任二顶皆相邻的图。

remark：完全图具有最多的边数；任意一对顶点间均有边相连。