Reference:《现代图论》 ——北京航空航天大学出版社
图的基本概念
1.1图的定义
图是一个三元组，记作G=<V,E, φ>
其中，V称为顶点集，E称为边集， φ称为E->V*V（笛卡尔积）的对应关系。
1.1.1其他定义
邻接结点：关于同一条边的两个结点
孤立结点：不与任何结点相连接的结点（度数为0）
邻接边：关联于同一个结点的两条边
环：两端点相同的边
平行边/重边：两结点间方向相同的若干条边
对称边：两端点相同但方向互为相反的两条有向边
1.1.2其他定义
无向图：每条边都是无向边
有向图：每条边都是有向边
混合图：图中不全是有向边，也不全是无向边
零图/空图：仅包含一些孤立结点的图（非无结点）
平凡图：仅包含一个孤立结点的图
1.1.3其他定义
多重图：含有平行边的图
简单图：无环且无平行边的图
完全图：任何不同两结点之间都有边相连的简单无向图
注：
1.无向图可以视为特殊有向图
2.n个结点的完全图K(n) 有C(n,2) = n * (n - 1) / 2条边
3.图G的顶点个数称为图G的阶
4.对于一个有向图D，去掉边上的方向得到无向图G称为D的基础图，反之，任何一个无向图G,将G的边指定一个方向得到的有向图称为G的一个定向图
例题：求证，在任意6个人的聚会上，要么有3人曾相识，要么有3人不曾相识。
提示：图论，至少三条同色边。
1.2图的结点度
1.2.1定义
设G为任意图，x为G的任意结点，与结点x相关联的边数（环要计算两次）称为x的度数。记作deg(x)或者d(x)
入度/出度在此省略。
1.2.2定理
每个图中，结点度数之和等于边数的两倍。即
每个图中，度数为奇数的结点个数必然是偶数个
在任何有向图中，所有结点的入度之和等于所有结点的出度之和
例：判断下列是否可构成一个简单无向图
(1).2,2,2,4,5,6(F)
(2).1,2,3,4,4,5(F)
1.3图的同构
1.3.1定义
设G1=<V1,E1>和G2=<V2,E2>均为简单图，若存在一个从V1到V2的双射f,且f对V1中所有的x和y,x与y在G1中相邻，当且仅当f(x)与f(y)在G2 中相邻，则称G1和G2同构，记作
(简单的说），就是当两个简单图同构的时候，两个图的结点之间具有保持相邻关系的一一对应。
必要条件：1.两图结点数相等 2.边数相等 3.度数相同的结点个数相等
(Tips:将图作出后进行形象拉伸也可大致判断。）
1.3.2定义
度序列：简单无向图G，如果V(G) = {V1~Vp)称非负整数序列d(V1) >= d(V2) >= d(Vp)为图G的度序列。
如果一个非递增的、非负整数序列可表示为某个简单无向图的度序列，则称该序列为图序列。
图序列判定算法：
1.已知非递增，非负整数序列S，删除S中的1个数k得到序列S1
2.若S1中的前k个数均不小于1，则将这k个数分别减去1得到S2，否则S就不是图序列
3.若S2全是0，则S是图序列，否则将S2重新排列得到非递增序列S3
4.令S = S3，跳转到步骤1。
1.4子图
1.4.1定义
设G=<V,E, φ>，G1=<V1,E1, φ1>，如果 且 是上的限制，则称G1是G的子图。
若G1G 且G1 G，则称G1是G的真子图
若G1G 且 V1 = V， 则称G1是G的生成子图\支撑子图
1.4.2补图
略。
1.5路与连通
1.5.1定义
设u和v是任意图G的两个结点，图G的一条u--v链是有限的结点和边的交替序列u0e1u1e2...u(n-1)e(n)u(n)
其中n（即链中出现的边数，称为链的长度）
u和v称为链的端点，其余结点称为链的内部点
一条uv链，当u v称为开的，否则为闭的
边互不相同的链称为迹
点互不相同的链称为路