图论课件(一)、子图的相关概念

格式：ppt
大小：1.00 MB
文档页数：29

下载文档原格式

图论课件(一)、子图的相关概念

1、路与连通性的相关概念
(1)、图中的途径 G的一条途径（或通道或通路）是指一个有限非空序列w= v0
e1 v1 e2 v2…ek vk，它的项交替地为顶点和边，使得 1 i k ，
ei的端点是vi-1和vi. 途径中边数称为途径的长度；v0,vk分别称为途径的起点与终点，
其余顶点称为途径的内部点。
G的子图，记为 H G
当 H G, H G 时，称H是G的真子图，记为
H G
3
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
2、点与边的导出子图
(1) 图G的顶点导出子图
定义2 如果 V V (G) ，则以 V 为顶点集，
以两个端点均在 V 中的边集组成的图，称为图G的点导出子图。记为：G[V ]
19
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
(6)、图的直径
连通图G的直径定义为：
d (G) max d (u, v) u, v V (G)
如果G不连通，图G的直径定义为 d (G) 例6 证明：在n阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。证明: (1) 若G中没有1度顶点，由握手定理：
Saad Y, Schultz M H. Topological properties of hypercubes [J]. IEEE
Trans. Comput . 1988, 37(7) : 867--872

图论课件-PPT课件

学习方法
目的明确
态度端正理论和实践相结合
充分利用资源
逐步实现从知识到能力到素质的深化和
升华
课程考核
平时成绩（30%-40%）
闭卷考试（60%-70%）
图论模型
为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢化合物用点抽象分子式中的碳原子和氢原子，用边抽象原子间的化学键。
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每个零售店间的关联。则图模型图形为： w1 w2 w3
r1
r2
r3
r4
r5
29
(3) 最短航线问题用点表示城市，两点连线当且仅当两城市有航线。为了求出两城市间最短航线，需要在线的旁边注明距离值。例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线则航线图的图形为： a 320 500 d 370 b 140 430 e c

图论学科简介（2）
19世纪末期，图论应用于电网络方程组
和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论用来求解生产管理、军事、交通运输、计算机和网络通信等领域中的离散性问题物理学、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学、管理科学等领域应用
七桥问题
近代图论的历史可追溯到18世纪的七桥问题:
穿过Kö nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。

图和子图

( = G[E \ {b, d, g}] ) ( G[E \ {b, c, d, g}] ) ( G[E \ {a, e, f, g}] )
注意 G[E \ E’] 与G - E’ 虽有相同的边集，但两者不一定相等：后者一定是生
成子图，而前者则不然。
❖ 上述四种运算是最基本的取子图运算，今后经常会遇到，一定要认真掌握好。关于子图的另一些定义还有： G + E’ 往G上加新边集E’ 所得的（G的）母图。为简单计，今后将 G {e} 简记为 G e ； G - {v} 简记为 G - v 。
❖ 完全二部图 Km,n 二部图G = (X, Y; E)，其中X
和Y之间的每对顶点都相邻，且 X = m, Y = n 。
二部图
K 3,3
K 1,5
K 2,2,2
❖ 类似地可定义，完全三部图（例如， Km,n,p），完
全 n-部图等。
❖ 例。用标号法判定二部图。用红蓝两种颜色进行
顶点标号如下：任取一顶点v 标以红色。再将v的所有相邻顶点都标以兰色。这时称v为已扫描顶点。若尚存在一已标号未扫描顶点u，将它的所有相邻顶点，（若不出现矛盾）都标以（其相异色）红色，并称u为已扫描顶点。如此继续下去，直到或者所有顶点都已标号，从而该图为一二部图；或者在标号过程中出现矛盾，该图为非二部图。
k-正则图（k-regular g.) d(v)k, v V.
0 -正则图 1-正则图 2-正则图
3 -正则图
习题
❖ 1.3.1 证明： 2/ 。
❖ 1.3.2 若 k-正则偶图(k > 0)的2-划分为 (X, Y),则 X = Y。
❖ 1.3.3 在人数 >1的人群中，总有二人在该人群中有相同的朋友数

图论基础知识PPT课件

.
6
图论算法与实现
一、图论基础知识
2、图的基本概念：
连通图：如果一个无向图中，任意两个顶点之间
都是连通的，则称该无向图为连通图。否则称为非连通图；左图为一个连通图。
强连通图：在一个有向图中，对于任意两个顶点U和V，都存在着一条从U到V的
有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图；右图不是一个强连通图。
深度优先遍历与宽度优先遍历的比较：
深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。
下面是广度优先遍历的过程：
.
14
图论算法与实现
一、图论基础知识
简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。
.
4
图论算法与实现
一、图论基础知识
2、图的基本概念：
路径和简单路径的举例：
左图1—2—3是一条简单路径，长度为2，而1—3—4—1—3就不是简单路径；
一、图论基础知识
2、图的基本概念：路径：对于图G=（V，E），对于顶点a、b，如果存在一些顶点序列
x1=a,x2,……,xk=b(k>1)，且（xi,xi+1）∈E，i=1,2…k-1，则称顶点序列x1,x2,……,xk为顶点a到顶点b的一条路径，而路径上边的数目（即k-1）称为该路径的长度。并称顶点集合{x1,x2,……,xk}为一个连通集。
边集数组
邻接表
优点

1 图的基本概念

这些学科都以图作为工具来解决实际问题和理论问题。
5
图论在计算机科学中的应用：地图信息系统、电路设计、超文本、计算机
网络、程序结构、数据结构、Petri网、形式语言与自动机…..
6
图的基本概念 1. 图
7
定义（无序对）对于二元集合{a,b}，由于元素之间没有次序，称{a,b}为无序对，记为（a,b）。
（2）给定有向图D=<V，E>，其中V={a,b,c,d}， E={<a,a>,<a,b>,<a,b>,<a,d>,<d,c>,<c,d>,<c，b>}
画出G与D的图形。
14
定义1.3 在无向图中， G的两个顶点之间可能存在若干条不同的边，称这些边为平行边或重边（multiple edges）。
这样问题就等价于在图中从某一结点出发找一条通路，通过它的每条边一次且仅一次，并回到原结点。
1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。欧拉认证了该问题无解。
3
从十八世纪中叶到二十世纪中叶，漫长的200年中，图论几乎停留在数学游戏阶段，在此阶段，图论问题大量出现，如著名的四色问题、Hamilton问题以及图的可平面问题等。
15
图的有关规定和概念通常G泛指图，包括无向图和有向图。 V、E 分别表示 G 的顶点集和边集，所以用 | V|、
|E|分别表示G的顶点数和边数。如果|V|和|E|是有限的，则称G为有限图；否则
为无限图。本课程只涉及有限图。
16
图的有关规定和概念图的顶点数|V|称为图的阶（order）。若|V|=n，则称G为n阶图。若E=，则称G为零图（null graph）。含有n个顶

图论的介绍ppt课件

chedules
工程项目的任务安排，如何满足限制条件，并在最短时间内完成？
Program structure
大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效率。
Graph Applications
Graph Problems and Algorithms
图论的介绍ppt课件
欧拉路径解決哥尼斯保七桥问題
原來是一笔画问题啊！
数学家欧拉(Euler, 1707-1783) 于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式
实际生活中的图论 Graph Model
电路模拟
例：Pspice、Cadence、ADS…..
哈密頓（Hamilton）周遊世界问題
正十二面体有二十个顶点表示世界上20个城市各经每个城市一次最后返回原地
投影至平面
哈密頓路径至今尚无有效方法來解決！
最短路径问題
(Shortest Path Problem)
最快的routing
最快航線
B 2
1
E
3
A
C 1
3 2F
1
3
D
3 3
G
最短路径算法Dijkstra算法
二分图（偶图） Bipartite graphs
A graph that can be decomposed into two partite sets but not fewer is bipartite
It is a complete bipartite if its vertices can be divided into two non-empty groups, A and B. Each vertex in A is connected to B, and viceversa

图论--第3讲子图

离散数学子图第3讲定义3.1设G=<V,E>, G1=<V1,E1>为两个图(同时为无向图或有向图)，(1) 若V1⊆V且E1⊆E，则称G1为G的子图，G为G1的母图，记作G1⊆G。

(2) 若V1⊂V或E1⊂E，则称G1为G的真子图，即G1⊆G且G1≠G。

定义3.2设G=<V,E>为一图，V1⊆V且V1≠∅，称以V1为顶点集，以G中两个端点都在V1中的所有边组成的集合为边集的图为G的V1导出子图，记作G[V1]。

特殊地，我们有G[V]=G。

定义3.3设G=<V,E>为一图，E1⊆E且E1≠∅，称以E1为边集，以E1中边关联的顶点为顶点集的图为G的E1导出子图，记作G[E1]。

特殊地，若G无孤立点，则有G[E]=G。

定义3.4设G=<V,E>为图,(1)设e∈E,用G-e表示从G中去掉边e，称为删除边e。

又设E1 E,用G-E1表示从G中删除E1中所有的边，称为删除E1。

定义3.4设G=<V,E>为图,(2) 设v∈V,用G-v表示从G中去掉v及所其关联的一切边，称为删除顶点v。

又设V1 V,用G-V1表示从G中删除V1中所有的顶点，称为删除V1。

G-V1=G[v\v1]定义3.4设G=<V,E>为图,(3) 设u,v∈V(u,v可能相邻也可能不相邻),用G∪(u,v)(或G+(u,v))表示在u,v之间加一条边(u,v)，称为加新边。

定义3.5设G为n阶无向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶无向完全图，简称n阶完全图，记作K n(n≥1) 。

思考K n的边数为？答案：C n2=n(n-1)/2定义3.6设D为n阶有向简单图，若D中每个顶点都邻接到其余的n-1个顶点，又邻接于其余的n-1个顶点，则称D为n阶有向完全图。

定义3.7设D为n阶有向图，若D的基图为n阶无向完全图K n，则称D为n阶竞赛图。

运筹学--图论 ppt课件

4
5
4 9 8
v1
v3
2
v6
[8,v2]
v8
5 33
1
[2,v1]
v4
v7
[10,v4]
33
Dijkstra算法示例1
3）迭代计算(c)—更新与永久标号节点v2相连的节 (d2+w25=3+7=)10< ∞ (=d5) 点的临时标号。
[3,v1]
v2
[0,-]
7
v5
[10,v2]
2 [+∞,v1] 6
v4
v7
[+∞,v1]
22
Dijkstra算法示例1
2）迭代计算(a)—从临时标号中找到距离上界dk最小的节点v4，d4=min{dk}，将其变换为永久编号。
[3,v1] [+∞,v1]
v2
[0,-]
7
v5
2 [+∞,v1] 6 1 2 [+∞,v1]
3
5 2 [5,v1]
4
5
4 9 8
v1
v3

最小树问题不一定有唯一解。
10
10
最小支撑树问题的解法

破圈法算法

初始化将图G的边按权值从大到小的次序排列，从原图开始迭代；迭代

第1步(删边) 从排列中顺序选择一条与图中剩余边构成圈的边，则将此边从图中删除，进入第2步(结束判断)；第2步(结束判断) 若图中剩下n-1条边，则已经得到最小支撑树；否则，进入下一轮迭代，返回第1步(加边)；

柯尼斯堡七桥问题

柯尼斯堡市区横跨普雷格尔河两岸，在河中心有两个小岛。小岛的两岸共有七座桥将岛与岛、岛与河岸连接起来。一个人怎样才能一次走遍七座桥，每座桥只走过一次，并最后回到出发点？

(图论)图的基本概念(课堂PPT)

15
图的度数的相关概念
在无向图G中，最大度 △(G)＝max{d(v)|v∈V(G)} 最小度 δ(G)＝min{d(v)|v∈V(G)}
称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。度为偶数(奇数)的顶点称为偶度(奇度)顶点。
在有向图D中，最大出度 △+(D)＝max{d+(v)|v∈V(D)} 最小出度 δ+(D)＝min{d+(v)|v∈V(D)} 最大入度 △-(D)＝max{d-(v)|v∈V(D)} 最小入度 δ-(D)＝min{d-(v)|v∈V(D)}
元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如在多重集合{a,a,b,b,b,c,d}中， a,b,c,d的重复度分别为2,3,1,1。
4
笛卡尔积
设A，B为任意的两个集合，称{<a,b>|a∈A∧b∈B}为A与B 的笛卡尔积，记作AXB。笛卡尔积中的是有序对<a,b>。只有a,b相等的时候才有 (a,b)＝(b,a). 也只有A=B时才有AXB＝BXA。
16
图的度数举例
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点达到)
例如：在图1.1中， (a)中e5与e6是平行边， (b)中e2与e3是平行边，但e6与e7不是平行边。 (a)和(b)两个图都不是简单图。

图论课件、子图的相关概念

判定方法：VF算法详解
初始化：为两个图的顶点分配初始颜色，并根据颜色对顶点进行排序。搜索：从两个图中选择未匹配的顶点作为当前顶点对，并尝试建立映射关系。如果当前顶点对可以建立映射关系，则递归地搜索下一个顶点对；否则回溯到上一个顶点对，并尝试其他可能的映射关系。剪枝：在搜索过程中，如果发现当前映射关系无法满足同构条件，则提前终止该分支的搜索。判定：当所有顶点对都建立了映射关系时，判断映射是否满足同构条件。如果满足，则两个图是同构的；否则它们不是同构的。
子图领域未来发展趋势预测
THANKS FOR
WATCHING
感谢您的观看
对于子图中的任意顶点v，其在子图中的度不大于在原图中的度。
子图的连通分量数可能大于、等于或小于原图的连通分量数。
子图的补图不一定是原图的补图的子图。
02
子图类型及其特点
生成子图是指由原图中所有顶点及部分边构成的子图，且子图中任意两个顶点间若存在边，则这条边一定是原图中的边。
生成子图保留了原图的所有顶点，但边数可能少于原图。由于包含原图所有顶点，因此生成子图能够较好地反映原图的拓扑结构。
适用于任意图，通过每次选择最小边的方式逐步构建生成树，求解最小生成树。
05
子图在计算机科学中应用
树是一种特殊的图，用于表示具有层次结构的数据。在计算机科学中，树被广泛应用于各种数据结构和算法，如二叉树、红黑树、B树等。
树（Tree）
图是一种更一般化的数据结构，用于表示对象之间的复杂关系。在计算机科学中，图被用于表示网络、电路、程序流程等多种结构。
判定方法：VF算法详解
在化学领域中，图论被广泛应用于分子结构的表示和比较。通过将分子结构转换为图模型，并利用子图同构判定方法，可以比较两个分子的结构相似性，从而预测它们的化学性质和反应活性。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3、图的生成子图
定义3 如果图G的一个子图包含G的所有顶点，称
该子图为G的一个生成子图
例2 如图所示，求G的所有生成子图 1
2
3
图G
解：按边数分别求出
7
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
定理：简单图G=(n,m)的所有生成子图个数为2m
(二)、图运算
19
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
(6)、图的直径
连通图G的直径定义为：
d (G) max d (u, v) u, v V (G)
如果G不连通，图G的直径定义为 d (G) 例6 证明：在n阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。证明: (1) 若G中没有1度顶点，由握手定理：
2m d (v) 2n m n m n 1 vV (G)
20
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
若G中有1度顶点u，对G的顶点数作数学归纳。
当n=2时，结论显然；设结论对n=k时成立。
当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≤k-1.于是G的边数≤k.
0.5
00
1 0.8
0.6 0.4 x 0.2
6、图的合成图
设 G1 (V1, E1), G2 (V2 , E2 ), 是两个图。对点集 V V1 V2 的任意两个点u=(u1,u2)与v=(v1,v2),当(u1adjv1)
或(u1=v1和u2adjv2)时，把u与v相连。如此得到的新图称为G1与
另证：由于G连通，所以，存在如下形式的途径：
v1 v2
vn1 vn
显然该途径至少含有n-1条边。(v1,v2, … , v n是G的n个不同顶点) (2) 考虑G中途径：W : v1 v2 vn1 vn
若W是路，则长为n-1;但由于G的边数大于n-1,因此，存在vi与vj,它们相异，但邻接。于是：
例1 如图所示，求 G[V ] 。其中 V 1, 3, 5
2 4
1 5
3 图G
4
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 5 3
G[V ]
(2) 图G的边导出子图
定义3 如果 E E(G) ，则以 E 为边集，
以 E 中边的所有端点为顶点集组成的图，称为图G的边导出子图。记为：G[E]
特别地，如果只删去一个点v，则记为G-v.
8
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
(2)、图的删边运算
设 E E(G) ，在G中删去 E 中的所有边的操作，称为删边运算。记为 G E
特别地，如果只删去一条边e，则记为G-e.
注：删点、删边后得到的图是原图的子图。
(4)、图中两顶点的距离
图中顶点u与v的距离：u与v间最短路的长度称为u与v间距离。记为
d (u, v). 如果u与v间不存在路，定义d (u, v)=∞.
(5)、图中两顶点的连通性
图G中点u与v说是连通的，如果u与v间存在通路。否则称u与v不连通。点的连通关系是等价关系。
如果图G中任意两点是连通的，称G是连通图，否则，称G是非连通图。非连通图中每一个极大连通部分，称为G的连通分支。G的连通分支的个数，称为G的分支数，记为 (G)
2、图的并运算
设G1,G2是G的两个子图，G1与G2并是指由 V (G1) V (G2 ) 为顶点集，以 E(G1) E(G2 ) 为边集组成的子图。记为：
G1 G2
特别是，如果G1,G2不相交(没有公共顶点)，称它们的并为直接并，可以记为： G1 G2
9
1
0.5 n 0
0.5
1 2 1.5 t1
G的子图，记为 H G
当 H G, H G 时，称H是G的真子图，记为
H G
3
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
2、点与边的导出子图
(1) 图G的顶点导出子图
定义2 如果 V V (G) ，则以 V 为顶点集，
以两个端点均在 V 中的边集组成的图，称为图G的点导出子图。记为：G[V ]
1
4
2
3
G1
G2
解：由联图的定义得：
1
5 4
2
3
5
G1 G2
13
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
6、图的积图
设 G1 (V1, E1), G2 (V2 , E2 ), 是两个图。对点集 V V1 V2 的任意两个点u=(u1,u2)与v=(v1,v2),当(u1=v1和u2adjv2)
“超立方体”可以采用积图来递归构造。定义如下：
(1) 1方体 Q1 K2
(2) n方体定义为：Qn K2 Qn1
Q1
Q2
Q3
“超立方体”常采用下面简单的递归构造方法：
16
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
n方体Q n的顶点可用一个长度为n的二进制码来表示。Q n的顶点数目正好等于2n个。
例8 设G是具有m条边的n阶单图，证明：若G的直径为2且Δ=n-2, 则m≥2n-4.
证明：设d (v)=Δ=n-2,且设v的邻接点为v1,v2,…,vn-2. u是剩下的一个顶点。由于d (G)=2且u不能和v邻接，所以u必须和v1,v2…,
vn-2中每个顶点邻接。否则有d (G)>2.于是得：m≥2n-4.
4、图的对称差运算(或环和运算)
设G1,G2是两个图，G1与G2的对称差定义为：
G1G2 (G1 G2 ) (G1 G2 )
10
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
例3 已知G1与G2，求 G1 G2 G1 G2 G1 G2
G1G2
2
d
4
d 2
Saad Y, Schultz M H. Topological properties of hypercubes [J]. IEEE
Trans. Comput . 1988, 37(7) : 867--872
7、图的联合
把G1的一个顶点和G2的一个顶点粘合在一起后得到的新图称为 G1与G2的联合。记为：G G1 G2
在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。
1、图的删点、删边运算
(1)、图的删点运算
设 V V (G) ，在G中删去 V 中的顶点和G中与之关联的所有边的操作，称为删点运算。记为 G V
a
c
e
c
b
1
f
3
G1
解：由相应运算定义得下面结果：
2
d
a c
bHale Waihona Puke 4gh5
ei
4 g
eh 5 i j
3 G2
d 2
4
c
e
1
f
3
j
G1 G2
3
G1 G2
G2 G1
11
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
2
2
a
b
1
f
3
G1 G2
4 g
h5 i
j 3
G2 G1
vi vi1
v j vi
为G中一闭途径，于是也就存在闭迹。
21
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
(3) 若不然，G中顶点度数至少为2，于是由握手定理：
2m d (v) 2n m n m n 1 vV (G)
这与G中恰有n-1条边矛盾！
0.5
00
1 0.8
0.6 0.4 x 0.2
2、图的交运算
设G1,G2是G的两个子图，G1与G2交是指由 V (G1) V (G2 ) 为顶点集，以 E(G1) E(G2 ) 为边集组成的子图。记为：
G1 G2
3、图的差运算
设G1,G2是两个图，G1与G2的差是指从G1中删去G2中的边得到的新图。记为G1-G2.
17
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
(三)、路与连通性
对图的路与连通性进行研究，在计算机网络研究中有十分重要的意义。因为网络的抽象就是一个图。研究网络信息传递，信息寻径是主要问题之一，这恰对应于图中路的研究；在网络研究中，可靠性也是主要问题之一，它与图的连通性问题相对应。

图论课件(一)、子图的相关概念

合集下载