§2.1.2图的基本概念(2)
子图给定图，，若，则称为的子图（subgraph），称为的母图（supergraph），记作：.
若，但，则称为的真子图（proper subgraph），记作：.
若是的子图，且，则称为的支撑（生成）子图（spanning subgraph）.
注：（1）二分图的任一子图也均为二分图.（2）边数为的图的所有（同构或不同构）支撑子图的个数为.
例1画出的所有不同构的支撑子图,
解：的不同构的支撑子图共有11个，分别为
注：（1）的支撑子图共有个，但不同构的支撑子图仅有11个.
（2）的所有不同构的支撑子图的个数与顶点数为4的所有不同构的简单图的个数是相同的的（都是11个）.为什么？
点导出子图（vertex-induced subgraph）：，
规定：（去掉顶点及与顶点相关联的边）；特别地，.
如
显然，完全图的任一点导出子图必定也是完全图.
在图的所有以为顶点集的子图中，以点导出子图含有的边数为最多.
边导出子图（edge-induced subgraph）：.
规定：（仅去掉边）；特别地，.
注：图的去点导出子图和去边导出子图可类比“皮”与“毛”的关系去解释.
显然，若是简单图，则，有.
定义 图和的和（并，union）：.
联（join）：.
轮（wheel）：.
轮辐：中的和之间的边.
补图（complementary graph）：
（The complement of a simple graph is the simple graph with the vertex set ,two vertices being adjacent in if and only if they are not adjacent in .）
如
注：（1）（union），（intersection），，，；（2）个顶点的空图，.（3），- 用于图之间的运算，，用于集合之间的运算.（4）（对称性）与互为补图.
自补图（self-complementary graph）：a simple graph is self-complementary if .
命题 若是自补图，则（1）；（2）.
证明：（1）由自补图，同构图的定义及补图的定义的注（1）易见；
（2）由（1）得，（整数！）.
但仅能其一为奇数，.▌
例2（比赛顺序的排定）有甲、乙、丙、丁、戊、己6名运动员报名参加A、B、C、D、E、F 6个项目的比赛.各运动员的比赛项目见下表中√所示.
A
B
C
D
E
F
甲
√
√
√
乙
√
√
√
丙
√
√
丁
√
√
戊
√
√
√
己
√
√
√
问应如何安排六个项目的比赛顺序，以使得每个运动员都不连续参加两项比赛？
解：以顶点表示比赛项目，两个顶点之间有一条边相连当且仅当有同一名运动员参加对应的两个比赛项目，作图.
由的补图知，合乎要求的比赛顺序为.▌
链，路，圈链（walk）：a finite none-null sequence whose term are alternatively vertices and edges.
origin：；terminus：；interval vertices：，，…，.
the length（长度） of a walk：the number of edges of a walk.
A closed walk is a walk which has positive length and whose origin and terminus are the same.
迹（trail）：a walk whose edges are distinct.
路（path）：a walk whose vertices are distinct（certainly，its edges are also distinct！）.
Obviously，a path is a trail.
路的表示：a -path，where are respectively the origin and terminus of a path.
圈（回路）（cycle）：a closed trail whose origin（terminus） and interval vertices are distinct，i.e,a closed path.
规定：A loop is also a cycle；the length of cycle is the number of vertices（or edges）of a cycle（Every cycle has the same number of vertices and edges！）.
圈（cycle） ：a cycle of length .
is a loop， is multiedges.
According to the odevity （odd even） of ， is divided into odd cycle（奇圈） and even cycle（偶圈）.
Th1 A graph is bipartite if and only if it contains no odd cycle.
Proof:
▌
注：当为偶数时，是二分图；当为奇数时，不是二分图.
例3试在中，求：（1）任两顶点之间的路的条数；（2）圈的个数；（3）含有某条边的圈的个数.
解：（1）任两顶点之间的长度为1，2，3，…，的路的条数分别为，此两顶点之间的路的条数为.
（2）.
（3）.▌
注：（1）可借助来分析.（2）中任两顶点之间的路的长度的最小，大值分别为，圈的长度最小，大值分别为.
例4求证：若是简单图，且，则中必存在长度为的路.
证明：（反证法）假设是中的一条最长路，且，则.于是，，，使得与相邻.
令，则也是中的一条路，且其长度为，这与假设矛盾.▍
例5（1）求证：若，则图中必含有圈．
（2）求证：若是简单图，且，则中必含有长度不小于为的圈.
（3）若，则图中含有圈．
证明：（1）,则，，使得与相连；同理，，使得与相连；…；，使得与相连.但由是有限图知，，必与中的某一个相连.不妨设与相连，则即为的一个圈.
（2）由（1）知，中含有圈.
设中的最长路为，显然的所有邻接顶点都在上(否则，若，与邻接，但，则仍为一条路，且其长度为，这与是最长路矛盾).令为的所有邻接顶点中下标最大者，显然.令，则是一个圈，且其长度.▍
（3）若含有环或重边，则中含有圈；否则，则为简单图.
若，则由（1）知，中含有圈；否则，则从中去掉所有度为1的顶点（悬挂点），设得图.若，则由（1）知，中含有圈；否则，则从中去掉悬挂点，设得图.
显然，当或2时，不满足，故上述过程进行到某一个图时即可终止.
显然，，故由（1）知，中含有圈，当然中也含有圈.
另证：（反证法）假设中不含有圈，则是森林.，矛盾.▍
注：（1）（1）的逆否命题：若有限图中不含有圈，则的顶点或是孤立点，或是悬挂点．
“等价命题”：若，则有限图中至少含有一个圈．
（2）（3）的逆否命题：若图中不含有圈，则.
例6求证：（1）若是图的两个圈，则是的若干不相交的圈的并．
（2）若是图的两个圈，则，含有的一个圈.
证明：（1）分和讨论.
（2）分和讨论.
▍
注：对称差（symmetric difference）：.
连通图顶点连通：are connected if there exists a -path in a graph；
顶点不连通：otherwise.
注：显然，顶点的连通性是一种等价关系，具有反身性，对称性和传递性.
连通图（a connected graph）：a graph any two vertices of which are connected；
非连通图（a disconnected graph）：otherwise.
连通分支（connected component）：connected components of a graph.
Obviously，a connected component is a maximal connected subgraph of a graph.
应当指出，极大（maximal）不同于最大（maximum）.最大连通子图指含有顶点数和边数最多的连通子图；极大连通子图指本身是连通子图，如再增加顶点或边，就不再连通的子图.由此，图的任一连通分支都是极大连通子图，但只有其中顶点数和边数最多的才是最大连通子图.
连通分支数：the number of all connected components of a graph .
Evidently,a graph is connected； is disconnected.
命题 ，有.
证明：由的定义，显然有；
又去掉一条边至多将的一个连通分支分割为两个连通分支，故.▍
注：此命题对去点未必成立，即去点比去边对图的连通性的破坏性小.
例7求证：若图中恰含有两个奇顶点，则它们必连通．
证明：设图的两个奇顶点为，若为连通图，则由连通图的定义知，必连通；
否则，必存在于的同一个连通分支中（任一图的奇顶点的个数必为偶数；而连通分支本身也是图，且是连通图!），当然也连通.▍
例8（1）求证：若是简单图，且，则必为连通图.
（2）找一个顶点数为的不连通的简单图，使得，其中.
（3）找一个顶点数为，且含有的边数最多的不连通图.
证明：（1）（反证法）假设不连通，，的所有连通分支为，则，.由此，.于是，
矛盾.
（2），令即可.
（3）令即可.▍
例9（1）求证：若是简单图，且，则必为连通图.
（2）找一个不连通的简单图，使得是正则的，其中为偶数，且.
证明：（1）（反证法）假设不连通，W.L.O.G.设，的两个连通分支分别为，且，则必有或.不妨设，又是简单图，则，有，这与矛盾.
（2）令即可.▍
注：表示不超过的最大整数.
例10（1）求证：若是不连通图，则为连通图.
证明：为证为连通图，只需证明：，在中连通.分两种情况讨论：
（1）若在中不相邻，则由补图的定义知，在中相邻，当然也连通.
（2）否则，则在的同一个连通分支中.由不连通知，，使得与在中都不连通，当然也不相邻.再由补图的定义知，与在中都相邻.于是，即为中的连接的一条路，在中连通.▍
注：（1）逆命题不真.如下面的图的补图连通，但不连通：
（2）逆否命题（或由互补关系的对称性）：若不连通，则连通.
（3）由例9和注（2）知，图与之一不连通，则另一必连通.
例11求证：若图连通，且所有顶点的度均为偶数，则，有.
证明：，设为的任一连通分支，则为偶数，且中所有顶点的度的和为（偶数！），与之间的边的条数为（偶数！）；又与连通，.由的选取的任意性知，，从而.▍
子图给定图，，若，则称为的子图（subgraph），称为的母图（supergraph），记作：.
若，但，则称为的真子图（proper subgraph），记作：.
若是的子图，且，则称为的支撑（生成）子图（spanning subgraph）.
注：（1）二分图的任一子图也均为二分图.（2）边数为的图的所有（同构或不同构）支撑子图的个数为.
例1画出的所有不同构的支撑子图,
解：的不同构的支撑子图共有11个，分别为
注：（1）的支撑子图共有个，但不同构的支撑子图仅有11个.
（2）的所有不同构的支撑子图的个数与顶点数为4的所有不同构的简单图的个数是相同的的（都是11个）.为什么？
点导出子图（vertex-induced subgraph）：，
规定：（去掉顶点及与顶点相关联的边）；特别地，.
如
显然，完全图的任一点导出子图必定也是完全图.
在图的所有以为顶点集的子图中，以点导出子图含有的边数为最多.
边导出子图（edge-induced subgraph）：.
规定：（仅去掉边）；特别地，.
注：图的去点导出子图和去边导出子图可类比“皮”与“毛”的关系去解释.
显然，若是简单图，则，有.
定义 图和的和（并，union）：.
联（join）：.
轮（wheel）：.
轮辐：中的和之间的边.
补图（complementary graph）：
（The complement of a simple graph is the simple graph with the vertex set ,two vertices being adjacent in if and only if they are not adjacent in .）
如
注：（1）（union），（intersection），，，；（2）个顶点的空图，.（3），- 用于图之间的运算，，用于集合之间的运算.（4）（对称性）与互为补图.
自补图（self-complementary graph）：a simple graph is self-complementary if .
命题 若是自补图，则（1）；（2）.
证明：（1）由自补图，同构图的定义及补图的定义的注（1）易见；
（2）由（1）得，（整数！）.
但仅能其一为奇数，.▌
例2（比赛顺序的排定）有甲、乙、丙、丁、戊、己6名运动员报名参加A、B、C、D、E、F 6个项目的比赛.各运动员的比赛项目见下表中√所示.
A
B
C
D
E
F
甲
√
√
√
乙
√
√
√
丙
√
√
丁
√
√
戊
√
√
√
己
√
√
√
问应如何安排六个项目的比赛顺序，以使得每个运动员都不连续参加两项比赛？
解：以顶点表示比赛项目，两个顶点之间有一条边相连当且仅当有同一名运动员参加对应的两个比赛项目，作图.
由的补图知，合乎要求的比赛顺序为.▌
链，路，圈链（walk）：a finite none-null sequence whose term are alternatively vertices and edges.
origin：；terminus：；interval vertices：，，…，.
the length（长度） of a walk：the number of edges of a walk.
A closed walk is a walk which has positive length and whose origin and terminus are the same.
迹（trail）：a walk whose edges are distinct.
路（path）：a walk whose vertices are distinct（certainly，its edges are also distinct！）.
Obviously，a path is a trail.
路的表示：a -path，where are respectively the origin and terminus of a path.
圈（回路）（cycle）：a closed trail whose origin（terminus） and interval vertices are distinct，i.e,a closed path.
规定：A loop is also a cycle；the length of cycle is the number of vertices（or edges）of a cycle（Every cycle has the same number of vertices and edges！）.
圈（cycle） ：a cycle of length .
is a loop， is multiedges.
According to the odevity （odd even） of ， is divided into odd cycle（奇圈） and even cycle（偶圈）.
Th1 A graph is bipartite if and only if it contains no odd cycle.
Proof:
▌
注：当为偶数时，是二分图；当为奇数时，不是二分图.
例3试在中，求：（1）任两顶点之间的路的条数；（2）圈的个数；（3）含有某条边的圈的个数.
解：（1）任两顶点之间的长度为1，2，3，…，的路的条数分别为，此两顶点之间的路的条数为.
（2）.
（3）.▌
注：（1）可借助来分析.（2）中任两顶点之间的路的长度的最小，大值分别为，圈的长度最小，大值分别为.
例4求证：若是简单图，且，则中必存在长度为的路.
证明：（反证法）假设是中的一条最长路，且，则.于是，，，使得与相邻.
令，则也是中的一条路，且其长度为，这与假设矛盾.▍
例5（1）求证：若，则图中必含有圈．
（2）求证：若是简单图，且，则中必含有长度不小于为的圈.
（3）若，则图中含有圈．
证明：（1）,则，，使得与相连；同理，，使得与相连；…；，使得与相连.但由是有限图知，，必与中的某一个相连.不妨设与相连，则即为的一个圈.
（2）由（1）知，中含有圈.
设中的最长路为，显然的所有邻接顶点都在上(否则，若，与邻接，但，则仍为一条路，且其长度为，这与是最长路矛盾).令为的所有邻接顶点中下标最大者，显然.令，则是一个圈，且其长度.▍
（3）若含有环或重边，则中含有圈；否则，则为简单图.
若，则由（1）知，中含有圈；否则，则从中去掉所有度为1的顶点（悬挂点），设得图.若，则由（1）知，中含有圈；否则，则从中去掉悬挂点，设得图.
显然，当或2时，不满足，故上述过程进行到某一个图时即可终止.
显然，，故由（1）知，中含有圈，当然中也含有圈.
另证：（反证法）假设中不含有圈，则是森林.，矛盾.▍
注：（1）（1）的逆否命题：若有限图中不含有圈，则的顶点或是孤立点，或是悬挂点．
“等价命题”：若，则有限图中至少含有一个圈．
（2）（3）的逆否命题：若图中不含有圈，则.
例6求证：（1）若是图的两个圈，则是的若干不相交的圈的并．
（2）若是图的两个圈，则，含有的一个圈.
证明：（1）分和讨论.
（2）分和讨论.
▍
注：对称差（symmetric difference）：.
连通图顶点连通：are connected if there exists a -path in a graph；
顶点不连通：otherwise.
注：显然，顶点的连通性是一种等价关系，具有反身性，对称性和传递性.
连通图（a connected graph）：a graph any two vertices of which are connected；
非连通图（a disconnected graph）：otherwise.
连通分支（connected component）：connected components of a graph.
Obviously，a connected component is a maximal connected subgraph of a graph.
应当指出，极大（maximal）不同于最大（maximum）.最大连通子图指含有顶点数和边数最多的连通子图；极大连通子图指本身是连通子图，如再增加顶点或边，就不再连通的子图.由此，图的任一连通分支都是极大连通子图，但只有其中顶点数和边数最多的才是最大连通子图.
连通分支数：the number of all connected components of a graph .
Evidently,a graph is connected； is disconnected.
命题 ，有.
证明：由的定义，显然有；
又去掉一条边至多将的一个连通分支分割为两个连通分支，故.▍
注：此命题对去点未必成立，即去点比去边对图的连通性的破坏性小.
例7求证：若图中恰含有两个奇顶点，则它们必连通．
证明：设图的两个奇顶点为，若为连通图，则由连通图的定义知，必连通；
否则，必存在于的同一个连通分支中（任一图的奇顶点的个数必为偶数；而连通分支本身也是图，且是连通图!），当然也连通.▍
例8（1）求证：若是简单图，且，则必为连通图.
（2）找一个顶点数为的不连通的简单图，使得，其中.
（3）找一个顶点数为，且含有的边数最多的不连通图.
证明：（1）（反证法）假设不连通，，的所有连通分支为，则，.由此，.于是，
矛盾.
（2），令即可.
（3）令即可.▍
例9（1）求证：若是简单图，且，则必为连通图.
（2）找一个不连通的简单图，使得是正则的，其中为偶数，且.
证明：（1）（反证法）假设不连通，W.L.O.G.设，的两个连通分支分别为，且，则必有或.不妨设，又是简单图，则，有，这与矛盾.
（2）令即可.▍
注：表示不超过的最大整数.
例10（1）求证：若是不连通图，则为连通图.
证明：为证为连通图，只需证明：，在中连通.分两种情况讨论：
（1）若在中不相邻，则由补图的定义知，在中相邻，当然也连通.
（2）否则，则在的同一个连通分支中.由不连通知，，使得与在中都不连通，当然也不相邻.再由补图的定义知，与在中都相邻.于是，即为中的连接的一条路，在中连通.▍
注：（1）逆命题不真.如下面的图的补图连通，但不连通：
（2）逆否命题（或由互补关系的对称性）：若不连通，则连通.
（3）由例9和注（2）知，图与之一不连通，则另一必连通.
例11求证：若图连通，且所有顶点的度均为偶数，则，有.
证明：，设为的任一连通分支，则为偶数，且中所有顶点的度的和为（偶数！），与之间的边的条数为（偶数！）；又与连通，.由的选取的任意性知，，从而.▍
