图：一个图是一个序偶，记为G=,其中： ① V={V1,V2,V3,…,Vn}是有限非空集合，Vi称为节点，V称为节点集 ②E是有限集合，称为边集，E中的每个元素都有V中的节点对与之对应，称之为边 ③与边对应的节点对既可以是无序的，也可以是有序的 表示方法 集合表示法，邻接矩阵法 邻接矩阵：设图G=，其中V={V1,V2,…,Vn}，并假定节点已经有了从V1到Vn的次序，则n阶方阵AG=(aij)nxn称为G的邻接矩阵，其中aij=1 ∈E或(vi,vj)∈E，否则aij=0 图中不与任何节点相邻接的节点称为孤立节点 两个端点相同的边称为环或者自回路 零图：仅有孤立节点组成的图 平凡图：仅含一个节点的零图

无向图：每条边都是无向边的图 有向图：每条边都是有向边的图 多重图：含有平行边的图 线图：非多重图 简单图：无环的线图

子图：边和定点都是原图的子集，则称该图为原图的子图 真子图：该图为原图的子图，但是不跟原图相等 生成子图：顶点集跟原图相等，边集是原图的子集 导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图 完全图：任何两个节点之间都有边 补图：完全图-简单图 握手定理：图中节点度数的总和等于变数的两倍， 图的重构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同

可达性：对节点vi和vj之间存在通路，则称vi和vj之间是可达的 无向图的连通性：图中每两个顶点之间都是互相可达的 强连通图：有向图G的任意两个顶点之间是相互可达的 判定条件：G中存在一条经过所有节点至少一次的回路 单向连通图：有向图G中任意两个顶点之间至少有一个节点到另一个节点之间是可达的 判定条件：有向图G中存在一条路经过所有节点 弱连通图：有向图除去方向后的无向图是连通的 判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵

欧拉通路（回路）：图G是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为欧拉通路（回路） 欧拉图：存在欧拉回路的图 欧拉通路判定：图G是连通的，并且有且仅有零个或者两个奇度数的节点 欧拉回路判定：图G是连通的，并且所有节点的度数均为偶数 有向欧拉图判定：图G是连通的，并且所有节点的出度等于入度 哈密顿图：图G中存在一条回路，经过所有点一次且仅一次 偶图：图G中的顶点集被分成两部分子集V1，V2，其中V1∩V2=∅，V1∪V2=V，并且图G中任意一条边的两个端点都是一个在V1中，一个在V2中 平面图：如果把无向图G中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G是平面图，否则是非平面图

无向树：连通而不含回路的无向图称为无向树 生成树：图G的某个生成子图是树 有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树

最小生成树：设G=是连通赋权图，T是G的一个生成树，T的每个树枝所赋权值之和称为T的权，记为W(T),G中具有最小权的生成树称为G的最小生成树

设有一棵二元树T，若对所有的树叶赋以权值w1,w2,…,wn,则称之为赋权二元树，若权为wi的叶的层数为L(wi)，则称W(T)=∑WixL(wi)为该赋权二元树的权，W(T)最小的二元树称为最优树