基本概念
图
定义：一集元素和它们之间关系的二元组(V,E)，其中集合V称为顶点集，集合E是V中元素组成的某些无序对的集合，称为边集，顶点的数目
图示
定义：点表示顶点，线段表示边，绘制出平面表示图。
术语
- 关联： 点是边的端点，则点和边在图中相关联。
- 相邻： 两个点有边相连，则点相邻；两个边至少有一个公共端点，则边相邻。
- 环边： 两个端点都重合的两个边。
- 重边： 给定顶点u、v。则图中连接u、v的两条或以上的边称为图中u、v的重边。
- 简单图： 无环边也无重边的图为简单图。
- 完全图： 所有点对之间都有边的图。
- 空图： 边集为空的图。
- 平凡图： 只有一个顶点的空图。
- 零图： 边集和点集都为空的图。（顶点集为空则边集肯定为空）。
- 顶点的度： 图中顶点关联的边数，记为
或 。 - 最大度：
。 - 最小度：
。 - 正则图： 各个顶点度都一样（设度为k）的图，称为k-正则图。
- 图的补图： 补图和原图的点集相同；补图和原图的边集互为补集(设完全图的边集为全集)。
lemma定理
图中各顶点度数之和是边数的两倍，即
推论：图中奇度顶点的数目一定是偶数。
子图
- 子图：对于图G和H，若
且 ，则H是G的子图，记为 。 - 生成子图：H是G的子图且
，则H是G的生成子图。 - 点导出子图：
，记为 。 - 边导出子图：
，记为 。 ：从 中删除顶点 ，包括删除顶点的边，从而获得子图。 ：从 中删除边 ，不删除顶点，从而获得子图。
路和圈
途径：图G中一个点边交替出现的序列 迹：边不重复的途径 路：顶点不重复的迹 闭途径：起点终点相同的途径 闭迹：边不重复的闭途径。 圈：中途点不重复的闭迹。
长度
途径的长度：边的数量 最短路的长度：即距离，两个点之间长度最小的路 奇圈：长度为奇数的圈 偶圈：长度为偶数的圈
二部图
定义：若G的顶点可以划分为两个非空子集X和Y，且单个子集内部没有边，则G为二部图。记为
完全二部图：若二部图G的两个子集为X和Y，且X的每个顶点和Y的每个顶点之间都有边，则G为完全二部图。
定理:一个图是二部图当且仅当它不含奇圈。
连通性
- 点连通：两个点间有路相同。
- 连通图：任意两顶点连通。
- 图的连通分支：把图的顶点划分为一系列非空子集，使得两顶点在同一个子集中当且仅当它们连通。通过这些子集得到的一系列点导出子图就是原图的一个个连通分支。连通分支的个数为连通分支数。
- 点的离心率e(v)：点v到图上距离该点最远的点的距离
- 中心：离心率最小的点
- 半径rad(G)：离心率的最小值
- 直径diam(G)：离心率的最大值
定理：若图G(V,E)连通，则
图的同构
定义：在图
注：同构关系是一个等价关系（自反、对称、传递）。同构的判断属于NP问题。
图的运算
G的补图：
G和H的并：
G和H的和：仅当
G和H的联：
G和H的对称差：当
