(图论)图的基本概念--第一章
- 格式：ppt
- 大小：3.37 MB
- 文档页数：27
下载文档原格式
合集下载
第一章(图论的基本概念)
第二节 图的顶点度和图的同构(4)
图序列:简单图的度序列. (d1, d 2 , , d p )(d1 d 2 d p ) 定理4 非负整数序列 是图序列当 p 且仅当 d i 是偶数,并且对一切整数k, 1 k p 1, 有
i 1
第二节 图的顶点度和图的同构(1)
定义1 设G是任意图,x为G的任意结点,与结点x关联的 边数(一条环计算两次)称为x的度数.记作deg(x)或d(x). 定义2 设G为无向图,对于G的每个结点x,若d(x)=K,则 称G为K正则的无向图.设G为有向图,对于G的每个结点 x,若d+(x)=d-(x), 则称G为平衡有向图.在有向图G中, 若 (G) (G) (G) (G) K , 则称G为K正则有向图. 定理1(握手定理，图论基本定理)每个图中,结点度数的 总和等于边数的二倍,即 deg(x) 2 E .
•
A
N
S
B
欧拉的结论 • 欧拉指出:一个线图中存在通过每边一次仅一次 回到出发点的路线的充要条件是: • 1)图是连通的,即任意两点可由图中的一些边连 接起来; • 2)与图中每一顶点相连的边必须是偶数. • 由此得出结论:七桥问题无解. 欧拉由七桥问题所引发的研究论文是图论的开 篇之作,因此称欧拉为图论之父.
xV
定理2 每个图中,度数为奇数的结点必定是偶数个.
第二节 图的顶点度和图的同构(2)
• 定理3 在任何有向图中,所有结点入度之和等于所有结 点出度之和. • 证明 因为每条有向边必对应一个入度和出度,若一个结 点具有一个入度或出度,则必关联一条有向边,因此,有向 图中各结点的入度之和等于边数,各结点出度之和也等 于边数. • 定义 度序列,若V(G)={v1,v2,…,vp},称非负整数序列 (d(v1),d(v2),…,d(vp))为图G的度序列.
图论--图的基本概念
图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。
注意：元素可以重复出现的集合称作多重集合。
某元素重复出现的次数称作该元素的重复度。
例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。
从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。
1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。
通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。
与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。
通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。
⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。
（2）顶点数称作图的阶，n个顶点的图称作n阶图。
（3）⼀条边也没有的图称作零图，n阶零图记作N n。
1阶零图N1称作平凡图。
平凡图只有⼀个顶点，没有边。
（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。
（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。
（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。
（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。
图论第01讲
•
两个问题：
（1）经过每个顶点一次且仅一次； （2）代价最小的Hamilton回路。
(目前无有效的方法求解)
•
货郎问题（Traveling Salesman Problem）
一个货郎到各村去卖货，要求每个村子 至少去一次，最后返回出发点，为其设计一 种销售路线，使总耗时最短。
求解方法：把路线全排列，求其中最小的。
1930年，波兰数学家库拉托父斯基 (Kuratowski)证明了平面图可以画在平面上；
•
里程碑：1936年，匈牙利数学家寇尼希 (D.Konig)发表名著《有限图和无限图理论》 ，使得图论成为一门独立的数学学科；
蓬勃发展：1946年，随着世界上第一台计算机 的问世，使图论的发展突飞猛进。 其后，图论在现代数学、计算机科学、工程技 术、优化管理等领域有大用而得以大力发展。
图论第01讲
•
课程简介
▪ 《图论》是计算机科学与技术专业、信息 安全专业的选修课程。 通过本课程的学习，使学生对图论的 历史背景、研究内容、相关技术及其发展 有一个较为全面地了解，从而将所学知识 和技术运用于实际应用领域奠定基础。
•
▪ 本课程所介绍的内容包括：
图论的发展历程和经典问题； 图的基本概念； 有关树和图的算法； 网络流问题； 匹配问题、色数问题；
•如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?
•
不少数学家都尝试去解析这个事例。而 这些解析，最后发展成为了数学中的图论。
莱昂哈德·欧拉(Leonhard Euler)在1736 年圆满地解决了这一问题，证明这种方法并 不存在。他在圣彼得堡科学院发表了图论史 上第一篇重要文献。欧拉把实际的问题抽象 简化为平面上的点与线组合，每一座桥视为 一条线，桥所连接的地区视为点。这样若从 某点出发后最后再回到这点，则这一点的线 数必须是偶数。
图论期末考试整理复习资料
目录第一章图的基本概念 (1)二路和连通性 (3)第二章树 (3)第三章图的连通度 (4)第四章欧拉图与哈密尔顿图 (5)一，欧拉图 (5)二．哈密尔顿图 (6)第五章匹配与因子分解 (9)一．匹配 (9)二．偶图的覆盖于匹配 (10)三．因子分解 (11)第六章平面图 (14)二．对偶图 (16)三．平面图的判定 (17)四．平面性算法 (20)第七章图的着色 (24)一．边着色 (24)二．顶点着色 (25)第九章有向图 (30)二有向树 (30)第一章图的基本概念1.点集与边集均为有限集合的图称为有限图。
2.只有一个顶点而无边的图称为平凡图。
3.边集为空的图称为空图。
4.既没有环也没有重边的图称为简单图。
5.其他所有的图都称为复合图。
6.具有二分类（X, Y）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。
7.完全偶图：是指具有二分类（X, Y）的简单偶图，其中X的每个顶点与Y 的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为Km,n8. 定理1 若n 阶图G 是自补的（即），则n = 0, 1（mod 4）9. 图G 的顶点的最小度。
10. 图G 的顶点的最大度。
11. k-正则图: 每个点的度均为 k 的简单图。
例如,完全图和完全偶图Kn,n 均是正则图。
12. 推论1 任意图中，奇点的个数为偶数。
13.14. 频序列：定理4 一个简单图G 的n 个点的度数不能互不相同。
15. 定理5 一个n 阶图G 相和它的补图有相同的频序列。
16.17.18. 对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1)19. 定义： 联图 在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G220. 积图：积图 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u =(u1,u2)和v = (v1,v2)，当(u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 时就把 u 和 v 连接起来所得到的图G 称为G1和G2积图。
图论（1）--图的基本概念
图论（1）--图的基本概念有向图和⽆向图的建⽴以及赋权图引⼊Q：什么是图论？A：图论是数学的⼀个分⽀。
它以图为研究对象。
图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，⽤连接两点的线表⽰相应两个事物间具有这种关系。
现在我们来探讨⽆向图和有向图的概念以及如何去建⽴最基本的图的模型什么是图对于初⼊图论的⼈来说，复杂的定义可能会直接劝退他们，现在我来举⼀个⾮常简单的例⼦。
这就是最常见的图，由于它没有指向，即没有明确的⽅向，它被称为⽆向图。
图是由顶点和边组成的，你应该很容易就知道那些元素是顶点，那些是边。
下⾯的具有⽅向的便是有向图：若有的边有向，有的边⽆向，则称为混合图。
接下来我们将引⼊更多的概念：若两个顶点有边相连，则称两个顶点相相邻，两个点称为起点/终点或端点如1指向2，则这两个顶点相邻，这两个顶点被称为断点，⽽1被称为起点，2被称为终点。
仅含⼀个顶点的边称为⾃环在⽆向图中，包含顶点v的边的个数，称为顶点的度。
在有向图中，以v为起点的边的个数，称为点的出度，以v为终点的边的个数，称为顶点的⼊度。
⽆向图的建⽴建⽴简单⽆向图，我们使⽤Matlab，版本为R2017a。
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并⽣成⼀个图% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4]; %s为顶点，必须保证连续且从1开始的正整数t1 = [2,3,1,1]; %边 s与t之间是⼀⼀对应的G1 = graph(s1, t1);plot(G1) %画出效果图效果图：带汉字的⽆向图：% 注意字符串元胞数组是⽤⼤括号包起来的哦s2 = {'学校','电影院','⽹吧','酒店'};t2 = {'电影院','酒店','酒店','KTV'};G2 = graph(s2, t2);plot(G2, 'linewidth', 2) % 设置线的宽度% 下⾯的命令是在画图后不显⽰坐标set( gca, 'XTick', [], 'YTick', [] );效果图：有向图的建⽴：% ⽆权图 digraph(s,t)s = [1,2,3,4,1];t = [2,3,1,1,4];G = digraph(s, t);plot(G)set( gca, 'XTick', [], 'YTick', [] );注意边的顺序和⽅向，依次为1指向2,2指向3,3指向1,4指向1和1指向4效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。
图论-图的基本概念
若 i, j 中有奇数，比如 i 是奇数，则路 P 上 v0 到 vi 的一段与边 v0vi 构成一个偶圈； 若 i, j 都是偶数，则路 P 上 vi 到 v j 的一段与边 v0vi 及 v0v j 构成一个偶圈。证毕。 例 1.1.4 设 G 是简单图，若δ (G) ≥ 3 ,则 G 中各个圈长的最大公因数是 1 或 2。 证明：由上例知，G 中有长分别为 i + 1, j + 1和 j − i + 2 的圈。若 i + 1, j + 1， j − i + 2 三 数有公因数 m > 2 ，则 m | ( j − i) ，于是 m | 2 ，这是不可能的。因此 i + 1, j + 1， j − i + 2
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
证明：按每个顶点的度来计数边，每条边恰数了两次。 推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0）。 4. 子图
子图(subgraph)：如果 V (H ) ⊆ V (G) 且 E(H ) ⊆ E(G) ，则称图 H 是 G 的子图，记为 H ⊆G。
生成子图(spanning subgraph): 若 H 是 G 的子图且V (H ) = V (G) ，则称 H 是 G 的生成子图。
这便定义出一个图。
2. 图的图示
通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的）。 这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
v1
v2
e1
e6 e5
e2
e4
v5
e7
v3
e3 v4
注：（1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
图论
图论1．图的基本概念图：由一些点和连接两点间的连线组成图1在这个图中，521,,,v v v 称为这个图的顶点，顶点之间的连线621,,,e e e 称为这个图的边。
通常我们用V 表示一个图中所有顶点的集合，用E 表示一个图中所有边的集合。
于是一个图G 通常被定义为()E V G ,=，在上图中{}521,,,v v v V =，{}621,,,e e e E = 图的阶数：一个图中含有的顶点数。
例如上图中含有5个顶点，故上图称为5阶图 有向边（弧）：如果在图的定义中要求边e 对应的序偶><b a ,是有序的，即前后顺序是不能颠倒的，则称边e 为有向边或弧。
无向边：如果在图的定义中要求边e 对应的序偶><b a ,是无序的，即前后顺序是可以颠倒的，则称边e 为无向边无向图：如果一个图中的每一条边都是无向边，则称这个图为无向图 有向图：如果一个图中的每一条边都是有向边，则称这个图为有向图 如果图的某个顶点和某条边是相联的，则称它们是相关联的顶点的次数：在无向图中把与某个顶点相关联的边数称为该顶点的次数。
环算两次，顶点v 的次数记为()v d在有向图中从顶点v 出去的边数，称为顶点v 的出度，记为()v d +进入顶点v 的边数，称为顶点v 的入度，记为()v d-，()()()v d v dv d -++=定理：一个图中所有的顶点的次数之和等于边数之和的两倍 推论：任何图中奇数次顶点的总数必为偶数例：一次聚会中，认识奇数个人的人数必为偶数 孤立点：次数为0的顶点。
图2 图3多重边：在图中，如果两个顶点之间的边多于一条，那么这几条边就称为多重边。
多重图：含有多重边的图环：如果图中某条边的起点和终点为同一个顶点，那么称这条边为环 简单图：既没有多重边又没有环的图在图中如果顶点i v 和j v 之间至少存在一条边，那么称顶点i v 和j v 是相邻的。
如果边i e 和j e 之间至少有一个共同顶点，则称边i e 和j e 是相邻的子图：设有图()111,E V G =和()221,E V G =，如果21V V ⊆并且21E E ⊆，则称图1G 是图2G 的一个子图生成子图：，如果21V V =并且21E E ⊆，则称图1G 是图2G 的一个生成子图图4图5链：以顶点开始以顶点结束的顶点和边的非空有限交替序列 例如43152v e v e v 就是一条链，而4312v e v v 却不是一条链圈：如果一条链的起点和终点是同一个顶点，则称这条链是一个圈如21152v e v e v路：当一条链中所有边和所有顶点均不相同时就称这条链为路 回路：如果一个圈中的所有边均不向图并且除第一个顶点和最后一个顶点相同外其余顶点都不相同，则称这个圈为回路连通图：如果某个图中的任何两个顶点之间至少存在一条链，则称这个图为连通图在实际的应用中，经常会涉及到图中各个顶点之间的某种联系，例如，在城市公路交通图中，需要说明两个路口之间的路段的长度，这时就需要给图的边赋以某个数值（称为线权）或给顶点赋以某个数值（称为点权），我们把这种赋以了数值的图称为加权图或网络。
图论讲义-图的基本概念
到目前为止，判断两图同构 还只能从定义出发。判断过 程中不要将两图同构的必要 条件当成充分条件。
注意：在研究图的过程中，顶点的位置以及边的曲直长短 都是无关紧要的。而且也没有假定这些顶点和边都要在一 个平面上（正方体的顶点和棱也可构成图）。我们研究的 只是顶点的多少及这些边是连接那些顶点的。
五、顶点的度
若e=(u,v)，则表示u到v的一条边（Edge），此时的
图称为无向图(Undigraph)。
有向图（Digraph）、无向图(Undigraph)
V1 V4
V1
V5 V2 V3 V2 V3
V4
有向图（Digraph）、无向图(Undigraph)
例1、设V={v1,v2,v3,v4,}，E={e1,e2,e3,e4,e5}，满足e1=(v1,v2)，
六、路与图的连通性
v1 v2 v5
图G中，取Γ1=v1v2v3，
v3
v4
G
Γ2=v1v2v3v4v2， Γ3=v1v2v3v2v3v4 则 Γ1,Γ2,Γ3依次为长为2,4,5的 通路，其中Γ1与Γ2为简单通路， Γ1为基本通路。 由定义可看出,G中v1v2v5v1为 长为3的圈，v1v2v3v4v2v5v1为 长为6的简单回路。
e2=(v2,v3)，e3=(v2,v3)，e4=(v3,v4)，e5=(v4,v4),则G=(V,E)是一个图。图 中边集E的边也可直接由点对表示，而将E作为多重集（即允许E中有相同元素的 集合）。 例2、设V={v1,v2,v3,v4}，E={(v1,v2)，(v1,v2)，(v2,v3)}，则H=(V,E)是 一个图。 e
d (V ) 2m
i 1 i
n
五、顶点的度
推论：任何图（无向图或有向图）中，度为奇数的顶点个
图论复习
图论复习题第一章图主要内容：1．图的基本概念和基本定理（重点是完全图、二部图、图的同构、握手定理等）2．轨道和圈（最长轨理论）练习题目：1．5阶无向完全图的边数为__10_____。
2．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件______。
3．图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的_充分必要条件______。
4．设无向简单图的顶点个数为n，则该图最多有_n(n-1)/2_ 条边。
5．一个有n个结点的图，最少有___1____个连通分支。
6．有三个顶点的所有互不同构的简单无向图有___4____个。
7．单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．解：设G中有x各结点，则3度的结点有x-7根据握手定理有，1x2+2x2+4x3+3x(x-7)=2x12解得x=9,故G中有9个结点。
满足条件的图如下：8．单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．试作一个满足该条件的简单无向图．9．面上有n个点S＝{x1,x2,……,x n}，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。
（38题）10．若图G是简单图，且(1)(2)2p pq-->，则G连通。
（42题）11．如果G是具有m条边的n阶简单图，证明：若G的直径为2且△= n-2，则m≥2n-4。
（50题）12．证明：在任何图中，奇度点个数为偶数。
（推论1.1）13．证明：图G是二部图当且仅当G无奇圈。
（定理1.2）14．证明：每个顶点度数都大于等于2的简单图必有圈。
（例1.9）15．证明：每个顶点度数都大于等于3的简单图必有偶圈。
（例1.11）16．画出4个顶点的不同构的图（包括连通和不连通图）。
第二章 树主要内容：1．树的定义和简单性质； 2．树的几个等价条件；3．生成树的个数（Cayley 公式）练习题目：1．设树T 中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T 中有____片树叶。
图论入门
深度优先搜索
• 深度优先搜索运用递归的方法。进入一个点以后，就把这个点 当做新的起点继续搜索下去，一直到无路可走。 void dfsvis(int u) { int i; for(i=0;i<n;i++) if(num[u][i]!=0 && vis[i] == 0) dfs(i); vis[a]=1; }
数组版邻接表
• Void addedge(int u,int v,int c){ e++; // 全局变量，代表已经插入的边数 nxt[e]=head[u]; pnt[e]=v;cost[e]=c; head[u]=e; //和链表的思路完全一样！！ } 推荐大家用这种方法！！省时！！
一些建议
• 第一，记得初始化。 • 第二，不要用graph[1000]这种方式建数组。要用宏 定义或者const，这样方便改。 • 第三，认真辨别有向图或者无向图，对于无向图需 要加两次边。 • 第四，要尽量运用全局变量。
图的存储方式
• 1. 邻接矩阵 • 实现方法： 二维数组 • 如果u，v之间有一条权值为c的边，那么对有向图， 加边的操作就是graph[u][v]=c。对无向图，必须再加 上graph[v][u]=c。 • 优点：好操作，找边方便。 • 缺点：不能有重边，存储空间有很多浪费的。
知识普及：链表
• 链表是完全不同于数组的一种线性结构，它的特点 就是存储空间是随机的，只能一个指着一个。如果 想找到a，就必须先找到指向a的那个节点！ • 初始化： struct edge{ int to,cost; edge *next; } • 结构体edge中有一个指向edge类型的指针，就是这 样。
• • • • • • • • void addedge(int u,int v,int cost){ edge p=new(edge); p->cost=cost;p->to=v; p->next=graph[u].next; graph[u].next=p; } 注意：每次建图前要初始化，把next设置成NULL。 要熟练运用指针！！！
图论
《图论》程序设计目录第一章图的基本概念 2一、图的的定义 2二、图的存储结构 3 第二章图的遍历 5一、深度优先搜索 6二、广度优先搜索8 例、子图划分12 第二章图的生成树14 一、基本概念14 排列方案15 二、图的最小生成树(prim算法) 16 例、机器蛇18 第三章、最短路问题20一、计算单源最短路问题（Dijkstra算法）20二、任意两点间的最短路（floyd算法）23三、最短路径的应用25 例、颜色集28 例计算DAG中的最长路30 例、计算带权有向图的中心31 第四章应用举例32 例、位图32 【例题】士兵排队34 简化图36如果数据元素集合D 中的各元素之间存在任意的前后件关系R ，则此数据结构G=（D ，R ）称为图。
奥林匹克信息学联赛的许多试题，需要用图来描述数据元素间的联系，需要用图的经典算法来解题用结点代表城市，每条边代表连接两个城市间的公路，边长的权表示公路长度。
这种公路网的表现形式就是属于图的数据结构。
第一章 图的基本概念一、图的的定义如果数据元素集合D 中的各元素之间存在任意的前后件关系R ，则此数据结构G=（D ，R ）称为图。
如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V ，E ），其中V 是结点的有穷（非空）集合，E 为边的集合。
如果元素a 是元素b 的前件，这种前后件关系对应的边用(a ，b)表示，即(a ，b)∈E 。
1、无向图和有向图⑴无向图：在图G=（V ，E ）中，如果对于任意的a ，b∈V，当(a ，b)∈E 时，必有（b ，a ）∈E（即关系R 对称），对称此图为无向图。
在一无向图中用不带箭头的边连接两个有关联的结点。
在具有n 个结点的无向图中，边的最大数目为n*(n+1)/2。
而边数达到最大值的图称为无向完全图。
在无向图中一个结点相连的边数称为该结点的度，无向完全图中，每一个顶点的度为n-1。
⑵有向图：如果对于任意的a ，b∈V，当(a ，b)∈E 时 ，(b ，a)∈E 未必成立，则称此图为有向图。
图论第一章 图的基本概念
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
图论及其应用
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
第一章 图的基本概念
本次课主要内容
图的概念与图论模型
(一)、图论课程简介
(二)、图的定义与图论模型 (三)、图的同构 (四)、完全图、偶图与补图 (五)、顶点的度与图的度序列
0.5
00
1 0.8
0.6 0.4 x 0.2
(四)、完全图、偶图与补图
1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 .
在同构意义下，n个顶点的完全图只有一个，记为 Kn
K2
K3
K5
容易求出： m(Kn )
1 2
n(n
1)
20
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
定理：若n阶图G是自补图( G G ),则有：
n 0,1(mod 4)
证明：n阶图G是自补图，则有：
22
H G 1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
m(G)
m(G)
m(Kn )
1 2
n(n
1)
所以：
m(G) 1 n(n 1) 4
由于n是正整数，所以：n 0,1(mod 4)
推论2 正则图的阶数和度数不同时为奇数 。
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
图论及其应用
1
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
第一章 图的基本概念
本次课主要内容
图的概念与图论模型
(一)、图论课程简介
(二)、图的定义与图论模型 (三)、图的同构 (四)、完全图、偶图与补图 (五)、顶点的度与图的度序列
0.5
00
1 0.8
0.6 0.4 x 0.2
(四)、完全图、偶图与补图
1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 .
在同构意义下，n个顶点的完全图只有一个，记为 Kn
K2
K3
K5
容易求出： m(Kn )
1 2
n(n
1)
20
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
定理：若n阶图G是自补图( G G ),则有：
n 0,1(mod 4)
证明：n阶图G是自补图，则有：
22
H G 1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
m(G)
m(G)
m(Kn )
1 2
n(n
1)
所以：
m(G) 1 n(n 1) 4
由于n是正整数，所以：n 0,1(mod 4)
推论2 正则图的阶数和度数不同时为奇数 。
电子科技大学《图论及其应用》复习总结--第一章图的基本概念
电⼦科技⼤学《图论及其应⽤》复习总结--第⼀章图的基本概念⼀、重要概念图、简单图、图的同构、度序列与图序列、偶图、补图与⾃补图、两个图的联图、两个图的积图1.1 图⼀个图G定义为⼀个有序对(V, E)，记为G = (V, E)，其中（1）V是⼀个有限⾮空集合，称为顶点集或边集，其元素称为顶点或点；（2）E是由V中的点组成的⽆序点对构成的集合，称为边集，其元素称为边，且同⼀点对在E中可出现多次。
注：图G的顶点数（或阶数）和边数可分别⽤符号n(G) 和m(G)表⽰。
连接两个相同顶点的边的条数，叫做边的重数。
重数⼤于1的边称为重边。
端点重合为⼀点的边称为环。
1.2 简单图⽆环⽆重边的图称为简单图。
（除此之外全部都是复合图）注： 1.顶点集和边集都有限的图称为有限图。
只有⼀个顶点⽽⽆边的图称为平凡图。
其他所有的图都称为⾮平凡图。
边集为空的图称为空图。
2.n阶图：顶点数为n的图，称为n阶图。
3.(n, m) 图：顶点数为n的图，边数为m的图称为(n, m) 图1.3 邻接与关联：顶点u与v相邻接：顶点u与v间有边相连接(u adj v)；其中u与v称为该边的两个端点。
注：1.规定⼀个顶点与⾃⾝是邻接的。
2.顶点u与边e相关联：顶点u是边e的端点。
3.边e1与边e2相邻接：边e1与边e2有公共端点。
1.4 图的同构设有两个图G1=(V1,E1)和G2=(V2,E2),若在其顶点集合间存在双射，使得边之间存在如下关系：u1,v1∈V1,u2,v2∈ V2 ，设u1↔u2，v1↔v2,; u1v1∈E1 当且仅当u2v2∈E2,且u1v1与u2v2的重数相同。
称G1与G2同构，记为：G1≌G2注：1、图同构的两个必要条件： (1) 顶点数相同；(2) 边数相同。
2、⾃⼰空间的理解：通过空间的旋转折叠可以进⾏形态转换1.5 完全图、偶图1、在图论中，完全图是⼀个简单图，且任意⼀个顶点都与其它每个顶点有且只有⼀条边相连接。
图论 第1章 图的基本概念
G
G[{e1 , e4 , e5 , e6 }]
G − {e5 , e7 }
G + {e8 }
图G1，G2的关系
设 G1 ⊆ G, G2 ⊆ G. 若 V (G1 ) V (G2 ) = φ x-disjoint） 若 E (G1 ) E (G2 ) = φ ,则称G1和G2是边不交的 （edge-disjoint） G1和G2的并, G1 G2 其中 V (G1 G2 ) = V (G1 ) V (G2 )
连通性
设 u, v 是图G的两个顶点，若G中存在一条 (u, v)
≡ v表示顶点 u 和v是连通的。 如果图G中每对不同的顶点 u , v都有一条 (u , v)
以 u
道路，则称顶点 u和 v是连通的(connected)。
道路，则称图G是连通的。
连通图
连通图
图G的每个连通子图称为G的连通分支，简
证明：G中含奇数个 1 (n − 1) 度点。 2 | Vo | 为 证明 V (G ) = Vo Ve 由推论1.3.2知， 偶数。因为 n ≡ 1(mod 4) ，所以n为奇数个。 因此，| Ve | 为奇数个。 n ≡ 1(mod 4) ， 1 2 ( n − 1) 为偶数。 1 1 d ( x ) = n − 1 − d ( x ) ≠ (n − 1) 设 x ∈Ve。若 d ( x) ≠ 2 (n − 1)，则 且 2 为偶数。由 G ≅ G c ，存在y，使得 d ( y) = d ( x) 为偶数。即 y ∈Ve 且 d ( y) ≠ 1 (n − 1) 。Ve 中度不为 2 1 (n − 1) 的点是成对的出现的。 2
G
G[{v1 , v2 , v3 }]
图论 第一章
n(n 1) 2
从而
m(G) n(n 1) 4
又因G 的边数 m(G)是整数，故 n(n-1)/4 为整数，即只能有 n≡0（mod 4）, 或 (n-1) ≡0 （mod 4）。
20/111
四．顶点的度（续）, 度序列
前已定义： 设 v为 G 的顶点，G 中与 v 为端点的 边的条数（环计算两次）称为点 v 的度数，简称为 点v的度，记为 dG (v)，简记为 d(v)。
例1 设 V ={v1, v2, v3, v4}，E ={v1v2 , v1v2, v2v3 }，则 G = (V, E) 是一个4阶图。
v1 若用小圆点代
表点，连线代表边
，则可将一个图用
“图形”来表示,
如例1 中的图可表
为
v2
v4 v3
4/111
注: 也可记边 uv 为e ，即 e = uv。
例2 设V = {v1,v2,v3,v4}，E = {e1,e2,e3,e4,e5}，其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4
E1 uv u v,u,v V
18/111
例如, 下图中的(a)，(b)两图是互补的。
（a）
（b）
定理1 若n 阶图G是自补的（即 G G ），则 n = 0, 1（mod 4）
19/111
证明 因为G是自补的，则G和其补图有同样多的边数，且 边数
m(G) +m (G )
= m(Kn) =
图划分: 正整数k的一个划分(d1, d2,…, dn)能成为某简 单图的度序列的k的划分.
显然，若正整数 k 有图划分，则k 必须是偶数
26/111
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
证明 设G＝<V，E>为任意一图，令
V1＝{v|v∈V∧d(v)为奇数} V2＝{v|v∈V∧d(v)为偶数} 则V1∪V2＝V，V1∩V2＝ ，由握手定理可知
2m d (v) d (v) d (v)
vV
vV1
vV2
由于2m和 d (v) ，所以 d (v) 为偶数，
举例
NG(v1) ＝ {v2，v5} NG(v1) ＝ {v1，v2，v5} IG(v1) ＝ {e1，e2，e3}
Г+D(d ) ＝ {c} Г-D(d ) ＝ {a，c} ND(d ) ＝ {a，c} ND(d ) ＝ {a，c，d}
简单图与多重图
定义1.3 在无向图中，关联一对顶点的无向边如果多于1条，则 称这些边为平行边，平行边的条数称为重数。 在有向图中，关联一对顶点的有向边如果多于1条，并且这些 边的始点和终点相同(也就是它们的方向相同)，则称这些边 为平行边。 含平行边的图称为多重图。 既不含平行边也不含环的图称为简单图。
无向图和有向图
定义1 一个无向图是一个有序的二元组<V，E>,记作G，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E称为边集，它是无序积V&V的多重子集，其元素称为无向 边，简称边。
定义2 一个有向图是一个有序的二元组<V，E>，记作D，其中 （1）V≠称为顶点集，其元素称为顶点或结点。 （2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向 边，简称边。
vV2
vV1
但因V1中顶点度数为奇数， 所以|V1|必为偶数。
问题研究
问题：在一个部门的25个人中间，由于意见不同，是否可能每 个人恰好与其他5个人意见一致？
解答：不可能。考虑一个图，其中顶点代表人，如果两个人意见 相同，可用边连接，所以每个顶点都是奇数度。存在奇数个 度数为奇数的图，这是不可能的。
为n阶零图，记作Nn，特别地，称N1为平凡图。 在图的定义中规定顶点集V为非空集，但在图的运算中可能产
生顶点集为空集的运算结果，为此规定顶点集为空集的图为 空图，并将空图记为。
标定图与非标定图、基图
将图的集合定义转化成图形表示之后，常用ek表示无向边 (vi,vj)（或有向边<vi,vj>），并称顶点或边用字母标定 的图为标定图，否则称为非标定图。
度数列举例
按顶点的标定顺序，度数列为 4,4,2,1,3。
按字母顺序，度数列，出度列，入 度列分别为
5,3,3,3 4,0,2,1 1,3,1,2
可图化的充要条件
定理1.3 设非负整数列d＝(d1，d2，…，dn)，则d是可图化的当
且仅当
n
di 0(mod 2)
i 1
证明 必要性。由握手定理显然得证。 充分性。由已知条件可知，d中有偶数个奇数度点。 奇数度点两两之间连一边，剩余度用环来实现。
度数列
设G＝<V,E>为一个n阶无向图，V＝{v1,v2,…,vn}，称d(v1)， d(v2)，…，d(vn)为G的度数列。
对于顶点标定的无向图，它的度数列是唯一的。 反之，对于给定的非负整数列d＝{d1,d2,…,dn}，若存在V＝
{v1,v2,…,vn}为顶点集的n阶无向图G，使得d(vi)＝di，则称d 是可图化的。 特别地，若所得图是简单图，则称d是可简单图化的。 类似地，设D＝<V,E>为一个n阶有向图，V＝{v1,v2,…,vn}，称 d(v1)，d(v2)，…，d(vn)为D的度数列，另外称d+(v1)， d+(v2)，…，d+(vn)与d-(v1)，d-(v2)，…，d-(vn)分别为D的出 度列和入度列。
图的一些概念和规定
G表示无向图，但有时用G泛指图(无向的或有向的)。 D只能表示有向图。 V(G)，E(G)分别表示G的顶点集和边集。 若|V(G)|＝n，则称G为n阶图。 若|V(G)|与|E(G)|均为有限数，则称G为有限图。 若边集E(G)＝，则称G为零图，此时，又若G为n阶图，则称G
元素可以重复出现的集合称为多重集合或者多重集，某元 素重复出现的次数称为该元素的重复度。 例如 在多重集合{a,a,b,b,b,c,d}中， a,b,c,d的重复度分别为2,3,1,1。
笛卡尔积
设A，B为任意的两个集合，称{<a,b>|a∈A∧b∈B}为A与B 的笛卡尔积，记作AXB。 笛卡尔积中的是有序对<a,b>。只有a,b相等的时候才有 (a,b)＝(b,a). 也只有A=B时才有AXB＝BXA。
例3： 空间中不可能有这样的多面体存在， 它的面数Байду номын сангаас奇 数，而且每个面是奇数条围成的。
解答：如果有这样的多面体存在，以此多面体的面集合为 顶点集构造一个图G,当且仅当两个面有公共边界线时在相 应的两顶间连一条边， 于是|V(G)|是奇数，而且对每个顶 点v,d(v)是奇数,则所有的顶点的度数之和为奇数， 与握 手定理矛盾。
设有向图D＝<V，E>，v∈V， 称{u|u∈V∧<v,u>∈E∧u≠v}为v的后继元集，记做Г+D(v)。 称{u|u∈V∧<u,v>∈E∧u≠v}为v的先驱元集，记做Г-D(v)。 称Г+D(v) 为v的出邻域, Г-D(v)为v 的入邻域. Г+D(v)∪ГD(v)为v的邻域，记做ND(v)。 称ND(v)∪{v}为v的闭邻域，记做ND(v)。
例如：在图1.1中， (a)中e5与e6是平行边， (b)中e2与e3是平行边，但e6与e7不是平行边。 (a)和(b)两个图都不是简单图。
顶点的度数
定义1.4 设G＝<V,E>为一无向图，v∈V，称v作为边的端点 次数之和为v的度数，简称为度，记做 dG(v)。 在不发生混淆时，简记为d(v)。
握手定理
定理1.1 设G＝<V,E>为任意无向图，V＝{v1,v2,…,vn}，
|E|＝m，则
n
d (vi ) 2m
i 1
说明 证明
任何无向图中，各顶点度数之和等于边数的两倍。 G中每条边(包括环)均有两个端点， 所以在计算G中各顶点度数之和时， 每条边均提供2度，当然，m条边，共提供2m度。
说明 可以用图形表示图，即用小圆圈（或实心点）表示顶 点，用顶点之间的连线表示无向边，用有方向的连线 表示有向边。
例1.1
例1.1 (1) 给定无向图G＝<V,E>，其中 V＝{v1,v2,v3,v4,v5}， E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}. (2) 给定有向图D=<V,E>，其中 V＝{a,b,c,d}， E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}。 画出G与D的图形。
图的度数举例
d(v1)＝4(注意，环提供2度)， △＝4，δ＝1， v4是悬挂顶点，e7是悬挂边。
d+(a)＝4，d-(a)＝1 (环e1提供出度1，提供入度1)， d(a)＝4+1＝5。△＝5，δ＝3， △+＝4 (在a点达到) δ+＝0(在b点达到) △-＝3(在b点达到) δ-＝1(在a和c点达到)
将有向图各有向边均改成无向边后的无向图称为原来图 的基图。
易知标定图与非标定图是可以相互转化的; 任何无向图G 的各边均加上箭头就可以得到以G为基图的有向图。
关联与关联次数、环、孤立点
设G＝<V,E>为无向图，ek＝(vi,vj)∈E， 称vi,vj为ek的端点，ek与vi或ek与vj是彼此相关联的。 若vi≠vj，则称ek与vi或ek与vj的关联次数为1。 若vi＝vj，则称ek与vi的关联次数为2，并称ek为环。 任意的vl∈V，若vl≠vi且vl≠vj，则称ek与vl的关联次数为0。
注: 某个点上的环要计算2次度数. 设D＝<V，E>为有向图，v∈V， 称v作为边的始点次数之和为v的出度，记做d+D(v)，简记作 d+(v)。 称v作为边的终点次数之和为v的入度，记做d -D(v)，简记作 d-(v)。 称d+(v)+d-(v)为v的度数，记做d(v)。
注:某个点上的有向环要对这个点计算一次入度计算一次出度.
对G’利用前面的证明结果：
两边消去2t,得到结论。
握手定理
定理1.2 设D＝<V,E>为任意有向图，V＝{v1,v2,…,vn}，
|E|＝m，则
n
n
n
d (vi ) 2m, 且 d (vi ) d (vi ) m
i 1
i 1
i 1
握手定理的推论
推论 任何图(无向的或有向的)中，奇度顶点的个数是偶数。
5
3
3
1
可图化举例
由定理1.3立即可知， (3,3,2,1)，(3,2,2,1,1)等是不可图化的， (3,3,2,2)，(3,2,2,2,1)等是可图化的。
定理：若
是简单图的次序列，且
则 是偶数，且对
1960年Erdos和Gallai已经证明这也是充分条件。
证明：大致思路： 对任意的k, 把图分成两部分：一部分 是1到k个点组成的， 设为V1， 另外的n-K点组成另外一部 分,设为V2。
设D＝<V,E>为有向图，ek＝<vi,vj>∈E， 称vi,vj为ek的端点。 若vi＝vj，则称ek为D中的环。
无论在无向图中还是在有向图中，无边关联的顶点均称为孤 立点。
相邻与邻接
设无向图G＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝(vi，vj)，则称vi与vj是相邻的。 若ek与el至少有一个公共端点，则称ek与el是相邻的。