§2.1.1图的基本概念(1)
图图（graph）：用（顶）点代表对象，顶点之间的边表示对象之间的关系.
“图是关系的数学表达”.
注：图和几何图形不同.几何图形描述物体的形状和结构；图仅反映对象之间的关系，图中顶点的相对位置，顶点之间的边的长短粗细对反映对象之间的关系并不重要.如“三角形两边之和大于第三边”等几何定理在图论中不再成立.
图的表示：，其中为顶点集，为边集.一般地，要求，但无此要求.
顶点(vertex，结(节)点，node)：；边(edge)：；端点(endpoint)：.
顶点数：；边数：.
边数 称为图的规模（size）.
注：集合的阶（cardinality）：集合中含有的元素的个数.
三种关系：顶点与顶点相邻（邻接）（adjacent）；边与边相邻（邻接）；顶点与边关联（incident）.
有限图（finite graph）：；
无限图（infinite graph）：otherwise.
注：以后如不加说明，在本课程中出现的图总是指有限图.
空图（empty graph）：；
非空图（nonempty graph）：otherwise.
平凡图（trivial graph）：；
非平凡图（nontrivial graph）：otherwise.
连杆（link）：两个端点不重合的边；
环（loop）：两个端点重合的边；
重边（multiedge，平行边，parallel edge）：several edges with the same two distinct endpoints.
注：以后如不加说明，“边”总是指连杆.
简单图（simple graph）：不含有重边和环的图；
重图（multigraph）：不含有环（可含有重边）的图.
显然，若图是简单图，则（何时取等号？）.
平面图（plane graph）：a graph any two edges of which intersect only at their endpoints；
非平面图（nonplane graph）：otherwise.
可平面图（planar graph）：a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints；
非可平面图（nonplanar graph）：otherwise.
注：一个非平面图有可能是可平面图！
权（weight）：给每条边以一个数字（如距离，长度，流量，费用等）；
赋权图（weighted graph）：边带有权的图.
无向图（graph）：边无方向的图；
有向图（digraph，directed graph）：otherwise.
混合图（mixed graph）：有的边有方向，有的边无方向的图．
注：以后如不加说明，“图”无向图.
图的同构（graphic isomorphism）
定义 对图，若一一映射（bijection），使得，有，则称与同构（isomorphic），记作.
简言之，两个图的结构完全一样即同构.
同构的两个图
当图的规模较大时，判断图是否同构很困难.
注：（1）同构是图的一种等价关系，具有反身性，对称性和传递性.
（2）同构的两个图有相同的顶点数和边数，反之不真；顶点数或边数不相同的两个图不可能同构.如
（3）同构关系保持图的对应顶点的度和邻接性.
（4）任一个顶点的简单图必同构于的某一子图.
例1（1）试画出顶点数为3的所有不同构的简单图.
（2）试画出顶点数为4的所有不同构的简单图.
解：（1）顶点数为3的不同构的简单图共有4个，分别为
（2）顶点数为4的不同构的简单图共有11个，分别为
若干特殊的图完全（完备）图（complete graph）：任两个互异顶点之间均恰好有唯一一条边相连的图.
表示：.
注：由完全图的定义易见，在顶点数相同的所有简单图中，的边数最多，且边数为.
性质：若是简单图，则（1）；（2）是完全图.
证明：（1）注；（2）显然.，若不是完全图，则由知，必含有环或重边，与是简单图矛盾.▌
例2有个药箱，每两个药箱恰好装有一种相同的药，每种药也恰好装在两个药箱里，问有多少种药？
解：以个药箱为顶点，两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药，作完全图.药的种数.▌
二分（部）图（偶图，bipartite graph）： s.t,，.
的不同构的连通的二分图共有5个：
一般地，规定二分图为简单图.
例4一个二分图：3-方体图（3-cube）
▌
注：方体（cube）
The cube is the graph whose vertices are the ordered tuples（有序元组） of 0’s and 1’s，two vertices being joined if and only if they differ in exactly one coordinate（坐标，分量）.
e.g.
性质 方体是二分图，且.
证明：由方体的定义可知，方体的顶点与分量取值为0，1的维向量一一对应.故方体的顶点数分量取值为0，1的维向量的个数.
方体的一个顶点，对应某一个分量取值为0，1的维向量v.显然，与向量v仅有一个分量不相同的分量取值为0，1的维向量恰有个，即与顶点相关联的边的条数为.又方体的每一条边都关联两个顶点，故方体的边数.
按照每一个顶点对应的分量取值为0，1的维向量的各分量的和的奇偶性，将方体的所有顶点分为奇、偶两个部分.显然，每一部分的顶点之间没有边相连，故方体是二分图.▌
完全二分图（complete bipartite graph）：a simple bipartite graph in which each vertex of is joined to each vertex of ，where ，，.
表示：.
例4一个完全二分图：
▌
性质：（1）；（2）若是二分图，则；且.
证明：（1）由完全二分图的定义；
（2）设，，，，则
；
由（2）知，.▌
星（star）：
星是一种重要的完全二分图，常用来研究计算机网络，星的度为的顶点表示网络服务器（server），其余个顶点表示计算机（computer）.
顶点的度顶点的度（次，degree）：the number of edges of a graph incident with （each loop is counted as two edges）.
最小度（minimum degree）：；
最大度（maximum degree）：.
奇顶点（odd-degree vertex）：a vertex whose degree is odd；
偶顶点（even-degree vertex）：a vertex whose degree is even.
悬挂点（suspended vertex）：a vertex with the degree 1.
悬挂边（suspended edge）：a edge incident with the suspended vertex.
孤立点（isolated vertex）：a vertex with the degree 0.
注：（1）另一种表示方法：.
（2），，.
（3）若是简单图，则；当然，.
（4）若是简单图，且，则.
（5）对二分图，有.
正则图（regular graph）：a graph all vertices of which have the same degree .
如，分别为正则图，正则图，方体是正则图.
显然，若，则为正则图,
例5 求证：若是正则二分图，则.
证明：不妨设是正则图，则由正则图的定义和顶点的度的定义的注（5）有，
.▍
例6 求证：若为简单图，且，则中至少有两个顶点的度数相等.
证明：W.L.O.G.中无孤立点，（反证法）假设中各顶点的度数均不相等，则中各顶点的度数为，于是；但由为简单图知，，矛盾.
另证：W.L.O.G.设为简单图，且不含有孤立点，则.
（反证法）假设中的各顶点的度均不相等，则，矛盾.
直观解释：，共个顶点.▍
例7 求证：在任一不少于两个人的人群中，必至少有两个人有相同个数的朋友.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人是朋友，作图.
显然，为简单图，且，故由例7知结论成立.▍
Th1（图论第一定理，欧拉定理）.
（The sum of degrees of all the vertices is twice of the number of edges in any graph）
Proof：Each edge is incident with two vertices(its two endpoints),therefore is counted twice in .▍
Corollary（握手定理）In any graph，the number of odd-degree vertices is even.
Proof,Let {odd-degree vertices},{even-degree vertices}.
Then (even!).
Since is even， is even；By definition of ， is even.▍
Note：“握手定理”的由来：某次宴会上，熟人见面互相握手.求证：握过奇数次手的人的个数必为偶数.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图.
由Corollary知，中奇顶点的个数为偶数，即握过奇数次手的人有偶数个.▍
例8某次宴会上，共有28769个人.熟人见面互相握手.求证：若每个人都至少握手一次，则其中必至少有1人至少握手两次.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图.于是，问题求证中至少存在一个度数超过2的顶点.
（反证法）假设中不存在度数超过2的顶点，则由每个人都至少握手一次知，中每个顶点的度数都恰为1.即的全部28769（奇数！）个顶点的度数都是1，与Corollary矛盾.▍
例8（续）某次学术会议有263人参加.每人至少和3个人讨论一次.求证：至少有1人和4人以上讨论过.
证：反证法.▍
例9求证：.
证明：.▍
例10求证：若为正则图，则.
证明：.▍
例11求证：若图中无孤立点，且，则中至少有一个悬挂点.
证明：（反证法）假设中无悬挂点，则.矛盾.▍
注：（1）（逆否命题）若图中无孤立点和无悬挂点，则.
（2）条件“中无孤立点”可增强为“是连通图”，结论仍成立.
例12图的各顶点的度按不增顺序排成的序列称为图的度序列（degree sequence）.问以下数列能否为某简单图的各顶点的度序列？
（1）1，1，2，3，2；（2）7，6，5，4，3，3，2；（3）6，6，5，4，3，3，1（4）5，4，2，2，2，1，1；（5）10，6，3，2，2，1，1，1.
解：（1）不能.奇顶点的个数为3；（2）不能.，；
（3）假设此数列是图的度序列，，，，必和其余6个顶点均相邻；同理，也必和其余6个顶点均相邻.故，矛盾；
（4）不能.奇顶点的个数为3；（5）不能.，.▍
例13问以下数列能否是某简单图的各顶点的度序列？如是，请画出图.
（1）5，3，2，2，1，1；（2）4，4，3，2，2，1；（3）2，1，1，0.
解：
▍
例14求证：若图有个顶点，条边，则中至少有一个顶点的度不小于3.
证明：（反证法）假设中所有顶点的度都小于3（即），则，矛盾.▍
图图（graph）：用（顶）点代表对象，顶点之间的边表示对象之间的关系.
“图是关系的数学表达”.
注：图和几何图形不同.几何图形描述物体的形状和结构；图仅反映对象之间的关系，图中顶点的相对位置，顶点之间的边的长短粗细对反映对象之间的关系并不重要.如“三角形两边之和大于第三边”等几何定理在图论中不再成立.
图的表示：，其中为顶点集，为边集.一般地，要求，但无此要求.
顶点(vertex，结(节)点，node)：；边(edge)：；端点(endpoint)：.
顶点数：；边数：.
边数 称为图的规模（size）.
注：集合的阶（cardinality）：集合中含有的元素的个数.
三种关系：顶点与顶点相邻（邻接）（adjacent）；边与边相邻（邻接）；顶点与边关联（incident）.
有限图（finite graph）：；
无限图（infinite graph）：otherwise.
注：以后如不加说明，在本课程中出现的图总是指有限图.
空图（empty graph）：；
非空图（nonempty graph）：otherwise.
平凡图（trivial graph）：；
非平凡图（nontrivial graph）：otherwise.
连杆（link）：两个端点不重合的边；
环（loop）：两个端点重合的边；
重边（multiedge，平行边，parallel edge）：several edges with the same two distinct endpoints.
注：以后如不加说明，“边”总是指连杆.
简单图（simple graph）：不含有重边和环的图；
重图（multigraph）：不含有环（可含有重边）的图.
显然，若图是简单图，则（何时取等号？）.
平面图（plane graph）：a graph any two edges of which intersect only at their endpoints；
非平面图（nonplane graph）：otherwise.
可平面图（planar graph）：a graph which can be drawn in a plane(平面) so that any two edges of it intersect only at their endpoints；
非可平面图（nonplanar graph）：otherwise.
注：一个非平面图有可能是可平面图！
权（weight）：给每条边以一个数字（如距离，长度，流量，费用等）；
赋权图（weighted graph）：边带有权的图.
无向图（graph）：边无方向的图；
有向图（digraph，directed graph）：otherwise.
混合图（mixed graph）：有的边有方向，有的边无方向的图．
注：以后如不加说明，“图”无向图.
图的同构（graphic isomorphism）
定义 对图，若一一映射（bijection），使得，有，则称与同构（isomorphic），记作.
简言之，两个图的结构完全一样即同构.
同构的两个图
当图的规模较大时，判断图是否同构很困难.
注：（1）同构是图的一种等价关系，具有反身性，对称性和传递性.
（2）同构的两个图有相同的顶点数和边数，反之不真；顶点数或边数不相同的两个图不可能同构.如
（3）同构关系保持图的对应顶点的度和邻接性.
（4）任一个顶点的简单图必同构于的某一子图.
例1（1）试画出顶点数为3的所有不同构的简单图.
（2）试画出顶点数为4的所有不同构的简单图.
解：（1）顶点数为3的不同构的简单图共有4个，分别为
（2）顶点数为4的不同构的简单图共有11个，分别为
若干特殊的图完全（完备）图（complete graph）：任两个互异顶点之间均恰好有唯一一条边相连的图.
表示：.
注：由完全图的定义易见，在顶点数相同的所有简单图中，的边数最多，且边数为.
性质：若是简单图，则（1）；（2）是完全图.
证明：（1）注；（2）显然.，若不是完全图，则由知，必含有环或重边，与是简单图矛盾.▌
例2有个药箱，每两个药箱恰好装有一种相同的药，每种药也恰好装在两个药箱里，问有多少种药？
解：以个药箱为顶点，两个顶点之间有一条边相连当且仅当两个药箱有一种相同的药，作完全图.药的种数.▌
二分（部）图（偶图，bipartite graph）： s.t,，.
的不同构的连通的二分图共有5个：
一般地，规定二分图为简单图.
例4一个二分图：3-方体图（3-cube）
▌
注：方体（cube）
The cube is the graph whose vertices are the ordered tuples（有序元组） of 0’s and 1’s，two vertices being joined if and only if they differ in exactly one coordinate（坐标，分量）.
e.g.
性质 方体是二分图，且.
证明：由方体的定义可知，方体的顶点与分量取值为0，1的维向量一一对应.故方体的顶点数分量取值为0，1的维向量的个数.
方体的一个顶点，对应某一个分量取值为0，1的维向量v.显然，与向量v仅有一个分量不相同的分量取值为0，1的维向量恰有个，即与顶点相关联的边的条数为.又方体的每一条边都关联两个顶点，故方体的边数.
按照每一个顶点对应的分量取值为0，1的维向量的各分量的和的奇偶性，将方体的所有顶点分为奇、偶两个部分.显然，每一部分的顶点之间没有边相连，故方体是二分图.▌
完全二分图（complete bipartite graph）：a simple bipartite graph in which each vertex of is joined to each vertex of ，where ，，.
表示：.
例4一个完全二分图：
▌
性质：（1）；（2）若是二分图，则；且.
证明：（1）由完全二分图的定义；
（2）设，，，，则
；
由（2）知，.▌
星（star）：
星是一种重要的完全二分图，常用来研究计算机网络，星的度为的顶点表示网络服务器（server），其余个顶点表示计算机（computer）.
顶点的度顶点的度（次，degree）：the number of edges of a graph incident with （each loop is counted as two edges）.
最小度（minimum degree）：；
最大度（maximum degree）：.
奇顶点（odd-degree vertex）：a vertex whose degree is odd；
偶顶点（even-degree vertex）：a vertex whose degree is even.
悬挂点（suspended vertex）：a vertex with the degree 1.
悬挂边（suspended edge）：a edge incident with the suspended vertex.
孤立点（isolated vertex）：a vertex with the degree 0.
注：（1）另一种表示方法：.
（2），，.
（3）若是简单图，则；当然，.
（4）若是简单图，且，则.
（5）对二分图，有.
正则图（regular graph）：a graph all vertices of which have the same degree .
如，分别为正则图，正则图，方体是正则图.
显然，若，则为正则图,
例5 求证：若是正则二分图，则.
证明：不妨设是正则图，则由正则图的定义和顶点的度的定义的注（5）有，
.▍
例6 求证：若为简单图，且，则中至少有两个顶点的度数相等.
证明：W.L.O.G.中无孤立点，（反证法）假设中各顶点的度数均不相等，则中各顶点的度数为，于是；但由为简单图知，，矛盾.
另证：W.L.O.G.设为简单图，且不含有孤立点，则.
（反证法）假设中的各顶点的度均不相等，则，矛盾.
直观解释：，共个顶点.▍
例7 求证：在任一不少于两个人的人群中，必至少有两个人有相同个数的朋友.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人是朋友，作图.
显然，为简单图，且，故由例7知结论成立.▍
Th1（图论第一定理，欧拉定理）.
（The sum of degrees of all the vertices is twice of the number of edges in any graph）
Proof：Each edge is incident with two vertices(its two endpoints),therefore is counted twice in .▍
Corollary（握手定理）In any graph，the number of odd-degree vertices is even.
Proof,Let {odd-degree vertices},{even-degree vertices}.
Then (even!).
Since is even， is even；By definition of ， is even.▍
Note：“握手定理”的由来：某次宴会上，熟人见面互相握手.求证：握过奇数次手的人的个数必为偶数.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图.
由Corollary知，中奇顶点的个数为偶数，即握过奇数次手的人有偶数个.▍
例8某次宴会上，共有28769个人.熟人见面互相握手.求证：若每个人都至少握手一次，则其中必至少有1人至少握手两次.
证明：以人为顶点，两个顶点之间有边相连当且仅当两个人握过手，作图.于是，问题求证中至少存在一个度数超过2的顶点.
（反证法）假设中不存在度数超过2的顶点，则由每个人都至少握手一次知，中每个顶点的度数都恰为1.即的全部28769（奇数！）个顶点的度数都是1，与Corollary矛盾.▍
例8（续）某次学术会议有263人参加.每人至少和3个人讨论一次.求证：至少有1人和4人以上讨论过.
证：反证法.▍
例9求证：.
证明：.▍
例10求证：若为正则图，则.
证明：.▍
例11求证：若图中无孤立点，且，则中至少有一个悬挂点.
证明：（反证法）假设中无悬挂点，则.矛盾.▍
注：（1）（逆否命题）若图中无孤立点和无悬挂点，则.
（2）条件“中无孤立点”可增强为“是连通图”，结论仍成立.
例12图的各顶点的度按不增顺序排成的序列称为图的度序列（degree sequence）.问以下数列能否为某简单图的各顶点的度序列？
（1）1，1，2，3，2；（2）7，6，5，4，3，3，2；（3）6，6，5，4，3，3，1（4）5，4，2，2，2，1，1；（5）10，6，3，2，2，1，1，1.
解：（1）不能.奇顶点的个数为3；（2）不能.，；
（3）假设此数列是图的度序列，，，，必和其余6个顶点均相邻；同理，也必和其余6个顶点均相邻.故，矛盾；
（4）不能.奇顶点的个数为3；（5）不能.，.▍
例13问以下数列能否是某简单图的各顶点的度序列？如是，请画出图.
（1）5，3，2，2，1，1；（2）4，4，3，2，2，1；（3）2，1，1，0.
解：
▍
例14求证：若图有个顶点，条边，则中至少有一个顶点的度不小于3.
证明：（反证法）假设中所有顶点的度都小于3（即），则，矛盾.▍
