回路
有n 个顶点的图成为 n 阶图，没有边的图称为零图。
1阶零图称为平凡图，平凡图只有顶点，没有边，设 e=（vi,vj）则称 vi，vj 是e 的端点，e 与vi vj 关联 如果 vi!=vj 也就是说不存在自环，则称 vi，vj 与e 的关联次数为以，如果 vi==vj 则称vi 与 e 的关联次数 为 2.
简单图：没有重复边或者说是平行边。
子图符号 G[ V ] 指的是点导出子图，G[E]指的是边导出子图
规定：自身与自身一定是联通的
初级通路： 在 n 阶图中从顶点u到v存在通路，则从u到v 存在长度为n-1的初级通路。
连通图： 任意两点之间都是联通的，平凡图是连通图。
连通分支：V 关于R 的等价类导出子图为G（V1）、G（V2）、、、、叫做G 的联通分支，其联通的每个支点的个数记作p（G），如果G 是连通图 ，则p（G）=1，若p（G）>=2,则G 一定是非联通图。
如果说通路中所有边各异则称图为简单通路，在此基础上如果说起点和终点重合，则称其为回路，
贿赂是特殊的通路。
如果说通路中的所有点各异所有边各异，则称通路为简单通路或路径，在此基础上，如果说起点和终点重合，则称其为初级回路或者说是圈，长度为奇数的圈叫做奇圈，偶数的叫做偶圈，如果说通路中有重复便出现，则称其为复杂通路。
u 和 v 之间最短的通路叫做短程线通路，d（u，v） u 与 v 之间的短程线通路的长度。
性质如果 u 与 v 不连通，则 d （u，v）=无穷大。
如何比较连通性 ：使得一个连通图的联通型破坏（成为二联通）所需需要破坏边数越多，图的连通性越差。
G-v 从G中删除v 及其关联的边。
G-V‘ 从G中删除V’所有顶点及其关联的边。
G-e 从G中删除边e 。
G-E‘从G中删除E’ 中所有的边。
为了使得图的联通性增强，我们可以选择删除一些顶点和一些边。
点割集：如果能最少删除几个点使得图变得不连通，那么这几个点组成的集合叫做点割集，注意点割集不唯一，但在确定的点割集，其元素个数是最少的。
边割集：如果能最少删除几条便使得图变得不连通，那么这几条边组成的集合叫做边割集，注意边割集不唯一，但在确定的边割集，其元素个数是最少的。
桥：连接连个连通图的唯一一条路径。
性质 K（n）没有点割集；
n阶零图 没有点割集也没有边割集。
若G 联通，E‘为边割集，则 p3（G-E’）=2；
若G 联通，V‘为点割集，则 p（G-V’）>=2；
点连通度K（G）与边连通度莱姆他（G）元素最小的点割集中元素的个数，元素最小的边割集中元素的个数。
可达 从 u 到 v 有道路 则称 u 可达 v, 若同时 v 可达 u 则称 u 与 v 相互可达。
D强联通：对于 任意 u，v ，u与v相互可达。
D单向联通：对于 任意 u，v ，u可达v或v可达u。
D 弱联通 ：如果略去D中的各边的方向所得到的无向图是连通图，则称其为弱联通图或连通图
无向图的关联矩阵：令mij 为顶点 vi 与边ej 的关联次数，称（mij）n*m 为G 的关联矩阵记作M（G）。
mij 的取值有三种 分别是 不关联，1 关联次数为1，2 关联次数为2即ej 是以 vi 为端点的环。
有向无环图的关联矩阵：
设有向无环图 D <V,E>, 令mij 表是关联度，mij =1， vi 为e j 的始边（出度），0 vi 与ej 不关联，mij=-1，vi 是ej 的终点（入度），则称（mij ）n*m 为 D 的关联矩阵记作 M （D）；
有向图的邻接矩阵 ：
设有向无环图 D <V,E> 令 aij表示顶点vi 连接到到顶点vj 边的条数，则称（aij）n*m 为 D 的邻接矩阵，记作A（D）简记为 A；
无向图的相邻矩阵， 设无向简单图G =<V,E>,令 aij 为顶点 vi 到顶点 vj 之间边的条数，则称（aij）n*m为G 的相邻矩阵记作 A（G）。
图的可达矩阵：
设图 G<V,E>,令pij 来表示 vi 是否能到大vj 如果 pij =1， 则说明可达，如果pij=0，说明不可达记作P（G）。
P（G）的主对角线元素全为1，点与自身可达。
G是强连通图当且仅当P（G）的所有元素均为一。
如果能得到 的可达矩阵 A，A 就表示 所有长度为一的可达关系，那么 矩阵A*A就表示所有长度为2的可达关系，其中矩阵元素的大小是指，可达路径的条数。
Ⅱ：几种特殊的图：
二部图，也称二分图，对于一个无向图G<V,E>,如果能将其顶点集分为 V1，V2 两个不相交的子集，使得G中的任意一条边的两个顶点不在同一个点集中，则称G 为 二分图，V1和V2 被称作互补顶点自己 ，显然n 阶零图（包含平凡图）都叫做 二分图（不含变得图就是零图）
若V1 中任一顶点与V2 中任一顶点均有且仅有一条边相连，则称这个二分图为完全二分图，二分图是可以被二染色的，若|V1|=s、|V2|=r ，则完全二分图的边数为 r*s 点数 为 r+s。
定理 ：说G 是二分图当且当G中无奇数长度的回路时。
二分图的最大匹配：
设二分图 G<V1 ，V2，E>，如果E‘中的边互相不相邻，则称E'是 G 的匹配， 如果在 E’中在增加任意一条边后所得到的边子集不再是匹配，则称E‘是G 的极大匹配，在所有极大匹配中，边数最多的称作最大匹配。
完备匹配，当其中一个点集都被用最少的边数匹配好了之后，就把这个二分图称作完备图，特别的，如果两个点集都被完备匹配则称为完美匹配。
Hall 定理： 设二分图 G<v1，v2，E> 其中|V1|<=|V2| ，则G中存在V1 到 V2 的完备匹配当且仅当V1 中任意 k 个顶点 至少与 V2 中任意 k 个顶点相邻。
欧拉图：
设G<E,V> 是连通图，如果说G经过每条边一次并且仅一次的回路成为欧拉回路，具有欧拉回路的图就叫做欧拉图，这种定义方法是根据图的性质啦定义的。
只有欧拉通路但没有欧拉回路的图不算是欧拉图：
存在欧拉通路或欧拉回路的充分必要条件，无向图 G 有欧拉回路，当且仅当当 G 是连通图且没有奇数度的顶点。
G 有欧拉通路但没有欧拉回路，当且仅当G 是连通图且恰好有两个 奇数度顶点，在恰好有两个顶点的欧拉通路中两个奇数度顶点一定是端点。
定理：有向图D 是欧拉回路当且仅当D是联通的 且所有顶点的入度等于出度，有向图D有欧拉通路但无欧拉回路，当且仅当D 是联通的且除了两个例外的顶点外，其余顶点的入度均等于入度，这两个顶点中，一个顶点的初度比如都大1 ，另一个顶点的入度 比出度小1.
回路
有n 个顶点的图成为 n 阶图，没有边的图称为零图。
1阶零图称为平凡图，平凡图只有顶点，没有边，设 e=（vi,vj）则称 vi，vj 是e 的端点，e 与vi vj 关联 如果 vi!=vj 也就是说不存在自环，则称 vi，vj 与e 的关联次数为以，如果 vi==vj 则称vi 与 e 的关联次数 为 2.
简单图：没有重复边或者说是平行边。
子图符号 G[ V ] 指的是点导出子图，G[E]指的是边导出子图
规定：自身与自身一定是联通的
初级通路： 在 n 阶图中从顶点u到v存在通路，则从u到v 存在长度为n-1的初级通路。
连通图： 任意两点之间都是联通的，平凡图是连通图。
连通分支：V 关于R 的等价类导出子图为G（V1）、G（V2）、、、、叫做G 的联通分支，其联通的每个支点的个数记作p（G），如果G 是连通图 ，则p（G）=1，若p（G）>=2,则G 一定是非联通图。
如果说通路中所有边各异则称图为简单通路，在此基础上如果说起点和终点重合，则称其为回路，
贿赂是特殊的通路。
如果说通路中的所有点各异所有边各异，则称通路为简单通路或路径，在此基础上，如果说起点和终点重合，则称其为初级回路或者说是圈，长度为奇数的圈叫做奇圈，偶数的叫做偶圈，如果说通路中有重复便出现，则称其为复杂通路。
u 和 v 之间最短的通路叫做短程线通路，d（u，v） u 与 v 之间的短程线通路的长度。
性质如果 u 与 v 不连通，则 d （u，v）=无穷大。
如何比较连通性 ：使得一个连通图的联通型破坏（成为二联通）所需需要破坏边数越多，图的连通性越差。
G-v 从G中删除v 及其关联的边。
G-V‘ 从G中删除V’所有顶点及其关联的边。
G-e 从G中删除边e 。
G-E‘从G中删除E’ 中所有的边。
为了使得图的联通性增强，我们可以选择删除一些顶点和一些边。
点割集：如果能最少删除几个点使得图变得不连通，那么这几个点组成的集合叫做点割集，注意点割集不唯一，但在确定的点割集，其元素个数是最少的。
边割集：如果能最少删除几条便使得图变得不连通，那么这几条边组成的集合叫做边割集，注意边割集不唯一，但在确定的边割集，其元素个数是最少的。
桥：连接连个连通图的唯一一条路径。
性质 K（n）没有点割集；
n阶零图 没有点割集也没有边割集。
若G 联通，E‘为边割集，则 p3（G-E’）=2；
若G 联通，V‘为点割集，则 p（G-V’）>=2；
点连通度K（G）与边连通度莱姆他（G）元素最小的点割集中元素的个数，元素最小的边割集中元素的个数。
可达 从 u 到 v 有道路 则称 u 可达 v, 若同时 v 可达 u 则称 u 与 v 相互可达。
D强联通：对于 任意 u，v ，u与v相互可达。
D单向联通：对于 任意 u，v ，u可达v或v可达u。
D 弱联通 ：如果略去D中的各边的方向所得到的无向图是连通图，则称其为弱联通图或连通图
无向图的关联矩阵：令mij 为顶点 vi 与边ej 的关联次数，称（mij）n*m 为G 的关联矩阵记作M（G）。
mij 的取值有三种 分别是 不关联，1 关联次数为1，2 关联次数为2即ej 是以 vi 为端点的环。
有向无环图的关联矩阵：
设有向无环图 D <V,E>, 令mij 表是关联度，mij =1， vi 为e j 的始边（出度），0 vi 与ej 不关联，mij=-1，vi 是ej 的终点（入度），则称（mij ）n*m 为 D 的关联矩阵记作 M （D）；
有向图的邻接矩阵 ：
设有向无环图 D <V,E> 令 aij表示顶点vi 连接到到顶点vj 边的条数，则称（aij）n*m 为 D 的邻接矩阵，记作A（D）简记为 A；
无向图的相邻矩阵， 设无向简单图G =<V,E>,令 aij 为顶点 vi 到顶点 vj 之间边的条数，则称（aij）n*m为G 的相邻矩阵记作 A（G）。
图的可达矩阵：
设图 G<V,E>,令pij 来表示 vi 是否能到大vj 如果 pij =1， 则说明可达，如果pij=0，说明不可达记作P（G）。
P（G）的主对角线元素全为1，点与自身可达。
G是强连通图当且仅当P（G）的所有元素均为一。
如果能得到 的可达矩阵 A，A 就表示 所有长度为一的可达关系，那么 矩阵A*A就表示所有长度为2的可达关系，其中矩阵元素的大小是指，可达路径的条数。
Ⅱ：几种特殊的图：
二部图，也称二分图，对于一个无向图G<V,E>,如果能将其顶点集分为 V1，V2 两个不相交的子集，使得G中的任意一条边的两个顶点不在同一个点集中，则称G 为 二分图，V1和V2 被称作互补顶点自己 ，显然n 阶零图（包含平凡图）都叫做 二分图（不含变得图就是零图）
若V1 中任一顶点与V2 中任一顶点均有且仅有一条边相连，则称这个二分图为完全二分图，二分图是可以被二染色的，若|V1|=s、|V2|=r ，则完全二分图的边数为 r*s 点数 为 r+s。
定理 ：说G 是二分图当且当G中无奇数长度的回路时。
二分图的最大匹配：
设二分图 G<V1 ，V2，E>，如果E‘中的边互相不相邻，则称E'是 G 的匹配， 如果在 E’中在增加任意一条边后所得到的边子集不再是匹配，则称E‘是G 的极大匹配，在所有极大匹配中，边数最多的称作最大匹配。
完备匹配，当其中一个点集都被用最少的边数匹配好了之后，就把这个二分图称作完备图，特别的，如果两个点集都被完备匹配则称为完美匹配。
Hall 定理： 设二分图 G<v1，v2，E> 其中|V1|<=|V2| ，则G中存在V1 到 V2 的完备匹配当且仅当V1 中任意 k 个顶点 至少与 V2 中任意 k 个顶点相邻。
欧拉图：
设G<E,V> 是连通图，如果说G经过每条边一次并且仅一次的回路成为欧拉回路，具有欧拉回路的图就叫做欧拉图，这种定义方法是根据图的性质啦定义的。
只有欧拉通路但没有欧拉回路的图不算是欧拉图：
存在欧拉通路或欧拉回路的充分必要条件，无向图 G 有欧拉回路，当且仅当当 G 是连通图且没有奇数度的顶点。
G 有欧拉通路但没有欧拉回路，当且仅当G 是连通图且恰好有两个 奇数度顶点，在恰好有两个顶点的欧拉通路中两个奇数度顶点一定是端点。
定理：有向图D 是欧拉回路当且仅当D是联通的 且所有顶点的入度等于出度，有向图D有欧拉通路但无欧拉回路，当且仅当D 是联通的且除了两个例外的顶点外，其余顶点的入度均等于入度，这两个顶点中，一个顶点的初度比如都大1 ，另一个顶点的入度 比出度小1.