10244图论

本文地址:http://www.885.ib765.com/ZanderZhao/p/11032037.html
文章摘要:天堂鸟娱乐返点优惠,我也不耽误大家一股强大"BBIN官方平台网站登入"使出甚至是没有一点。

  图论是近年来发展迅速而又应用广泛的一门新兴学科。它最早起源于一些数学游戏的难题研究。如1736年欧拉(L . Euler)所解决的哥尼斯堡七桥问题;以及在民间广为流传的一些游戏问题:例如迷宫问题、棋盘上马的行走路线问题等等。

  这些古老的问题当时吸引了许多学者的注意,从而在这些问题研究的基础上,又提出了著名的四色猜想和环游世界各国的问题。

  图论不断发展,它在解决运筹学,网络理论,信息论,控制论,博奕论以及计算机科学等各个领域的问题时,显示出越来越大的效果。

  对于这样一门应用广泛的学科,其包含的内容是丰富的,本篇我们只准备介绍基本的概念和定理,为今后有关学科及课程的学习和研究提供方便。

 

 

1.图

 1.1定义

定义:一个图 G 是一个三元组< V(G) , E(G) , ΦG >
       其中 V(G) 是非空的结点(顶点)集合,

  E(G) 是的集合,

  ΦG 是从边集 E 到结点偶对集合上的函数。

 

讨论定义:
(1) V(G) ={ v1 , v2 , … , vn }是非空的结点集合,vi 称为结点,简称V是点集

(2) E(G)={e1 , … , em}为边的集合,ei 称为边,简称 E 为边集

(3) ΦG 是从边集 E 到结点偶对集合上的函数。即对于每条边 ei ,都存在V中的结点偶对与之相对应。

  例如       ΦG (ei) = (vi , vj)

(4) 定义中的结点偶对可以是有序偶对 <vi , vj> ,也可以是无序偶对 (vi , vj) 。

  ①若边 e 对应有序偶对 <vi , vj> ,则称边 e 是有向边(弧)

       结点 vi 称为有向边的起点,结点 vj 称为有向边的终点,统称为 e 的端点

     也称 e 是关联于结点vi 和 vj 的,结点vi 和 vj 是邻接的(相邻的)

  ②若边 e 对应无序偶对 (vi , vj),则称边 e 是无向边(棱)

(5) 每条边都是有向边的图,称为有向图
   每条边都是无向边的图,称为无向图
(6) 若令 e= <vi , vj> 或 e= (vi , vj),即以结点偶对来表示图的边,这样可把图简化成:
      G=<V,E >.

 

 

专有名词:

(1) ( n , m) 图:具有 n 个结点,m 条边的图。

(2)有向完全图:在 n 个结点的有向图
  G = <V , E> 中,如果 E=V×V,则称G为有向完全图。

 例如

 

注:对于有向简单完全图:其有向边条数 m= 2 Cn2 = n(n-1)  (除去自回路)

(3)无向完全图:每两个结点之间均有连线的无向图。
    具有 n 个结点的无向完全图的边数为:m= Cn2 = n(n-1)/2

例如

(4)混合图:既有有向边,又有无向边的图。
(5)互相邻接的边:连接于同一结点的二条(或若干条)边。

 例如

 

 

(6) 自回路:图中起始且终止于同一结点的边。
(自回路的箭头方向是没有意义的 )

(7)多重边(平行边):二个结点之间方向相同的二条(多条)边。

 例如

 

(8)含有多重边的图称为多重图,非多重图称为线图

  例如

 

 

 

(9) 简单图:无自回路的线图称为简单图。
               即简单图是没有自回路和多重边的图。

(10) 赋权图G是一个三元组〈V , E , g〉或四元组〈V , E , f , g 〉,
其中 V 为结点集合,E 为边的集合,f 是定义在集合 V上的函数,g 是定义在集合 E 上的函数。

实际上,赋权图可以用一句话概括:每一条边或结点均注上数字的图(数字可以为整数、正实数)

 

(11)孤立结点:不与任何结点相连接的结点。
(12)零图:仅包含孤立结点的图,记为 ( n , 0 ).
(13)平凡图:只有一个结点的图(1 , 0).

 

1.2节点的次数

1.2.1定义

有向图 G 中,对于任何结点 v,
①以 v 为始点的边的条数,称为结点 v 的引出次数出度),记作 deg+(v) ;
②以 v 点为终点的边的条数称为 v 的引入次数入度),记作 deg-(v) ;
③结点 v 的引入次数和引出次数之和称为结点 v 的次数度数),记作 deg(v),即
deg(v) = deg+(v) + deg-(v) .

 

对于无向图

结点 v 的度数等于与该结点 v 相关联的边的条数,也记为 deg(v) 。

 

正则图:所有结点的度数均相同的简单无向图。

例如

 

 1.2.2定理

定理1

设 G 是一个 (n , m) 图,它的结点集合为 V ={ v1 , v2 , … , vn } ,则

即所有结点度数的总和等于边数的两倍。

 

推论:

在任何图中,
(1) 所有结点的度数之和必为偶数;
(2) 度数为奇数的结点必有偶数个。

 

定理2

在任何有向图中,所有结点的入度之和等于所有结点的出度之和。

 

1.3路与回路

1.3.1路径

定义:

在一个图中,从结点 v0 到结点 vn 的一条路径 P 是:图的一个点边交替序列
( v0 e1 v1 e2 v2 … en vn )。
即从结点 v0 出发经过某些结点,而最终到达终点 vn 的点边交替序列称为图的路径

讨论定义:
⑴ 从一个结点到某一结点的路径(若有的话),不一定是唯一的;

例如:设有向图G,求起始于1,终止于3的路径。

 

专有名词:

(1)穿程全部结点的路径:经过图中所有结点的路径。
(2)简单路径:在某一路径中,如果同一条边仅出现一次的路径。
(3)基本路径:在某一路径中,如果同一顶点仅出现一次的路径。

(4)回路:如果某路径的起点 v0 和终点vn 相重合,则称此路径为回路。
(5)简单回路:通过每条边不超过一次的回路。
(6)基本回路:通过每个结点不超过一次的回路。
(7)非回路图:没有任何回路的简单有向图。

讨论:

①回路不包含自回路。
②不是基本路径的任何路径都会包含回路,而去掉这些回路就可以得到基本路径。

 

1.3.2路径的表示方法

(a)边的序列表示法:设G = <V , E> 为一有向图,vi ∈ V ,则路径可以表示成:
      (< v1 , v2 > , < v2 , v3 > , … , < vk-1 , vk >)
(b)结点表示法: 在非多重图中,也可用顶点序列 (v1 , v2 , … , vk ) 表示路径。

1.3.3路径长度

 若两个结点之间有一条路经P,则路径 P 的长度|P|=P中边的条数。

 

1.4图的性质

1.4.1可达性

定义: 

设图G为简单有向图,且 vi , vj ?V,若从 vi 到 vj 存在任何一条路径的话,则称 vi 到 vj 是可达的

 注:

可达性一定满足:自反性;可传递性

 

定义:

 从 vi 到 vj 的最短路径的长度称为距离,并记作: d<vi , vj> 

讨论定义:
(1) d<vi , vi> = 0
(2) d<vi , vj> ≥ 0
(3) d<vi , vj> + d<vj , vk> ≥ d<vi , vk>
(4)规定:若 vi 到 vj 是不可达的,则d<vi , vj> = ∞.
(5) 在有向图中,若 vi 到 vj 是可达的,且 vj 到 vi 也是可达的,
     但 d<vi,vj> 不一定等于 d<vj, vi>。

例如

d< c, a > = 1,
d< a, c > = 2

 

1.4.2联通性

定义:

 对于无向图 G,如果任何两个结点是相互可达的,则称图G是连通的

 对于有向图来讲,如果两结点均是互相可达的,则称此图是强连通的

 若图中任何结点偶对中至少有一点到另一结点是可达的,则称此图是单侧连通

 对于简单有向图的伴随无向图(底图),若是连通的,则称此图为弱连通

注:伴随无向图即为去掉箭头方向的图。

 定理:

一个有向图是强连通的充要条件是它包含一个回路,且该回路至少包含每个结点一次

 

定义:

设G = <V , E>为一简单有向图,且G’是G的子图。

对于某一性质而言,若没有其他包含G’的子图具有这种性质,

则称子图G’是相对于该性质的极大子图

具有强连通性质的极大子图G’称为强分图
具有单侧连通性质的极大子图G’称为单侧分图
具有弱连通性质的极大子图G’称为弱分图

定理:

在任一简单有向图G=<V,E>中,有向图的每一个结点恰好处于一个强分图之中。

 

1.5图的矩阵表示

矩阵是研究图的有关性质的最有效的工具,可运用图的矩阵运算求出图的路径、回路和其它一些性质

1.5.1图的邻接矩阵表示

定义:

设G = <V , E>是简单有向图,其中V={v1, v2, … , vn}。定义一个 n?n 的矩阵 A,并把其中各元素 aij 表示成:

则称矩阵 A 为图 G 的邻接矩阵

例如:设图 G = <V , E>
如图所示

则图 G 的邻接矩阵为

 

讨论定义:

⑴ 图G的邻接矩阵中的元素为0和1,
∴又称为布尔矩阵;

⑵ 图G的邻接矩阵中的元素的次序是无关紧要的,

只要做 行和行、列和列的交换,则可得到相同的矩阵。

∴若有二个简单有向图,则可得到二个对应的邻接矩阵,

若对某一矩阵做行和行、列和列之间的交换后得到和另一矩阵相同的矩阵,则此二图同构。

⑶ 当有向图中的有向边表示关系时,邻接矩阵就是关系矩阵;
⑷ 零图的邻接矩阵称为零矩阵,即矩阵中的所有元素均为0;

⑸ 在图的邻接矩阵中,
①行中1的个数就是行中相应结点的引出次数(出度).
②列中1的个数就是列中相应结点的引入次数(入度).

 

1.5.2 矩阵的计算

设有向图 G = <V , E>的邻接矩阵为 A,

则G的逆图 > 的邻接矩阵就是 AT

 

 

1.5.2.1AAT 的元素的意义

设有向图 G = <V , E> 的邻接矩阵为 A,并令 B = AAT,则

 

分析:元素 aik = 1 意味着存在边<vi , vk> .
  元素 ajk = 1 意味着存在边<vj , vk> .

结论:如果从结点 vi 和 vj 两者引出的边,能共同终止于某些结点 vk ,则这些终止结点 vk 的数目就是 bij 的值,

  特别地,当 i = j 时,元素 bii 的值就是结点 vi 的引出次数

 

主对角线上的数,表示结点 i 的引出次数。

1.5.2.2ATA 的元素的意义

设有向图 G = <V , E> 的邻接矩阵为 A,并令 B = ATA,则

 

分析:元素 aki = 1 意味着存在边<vk , vi> .
  元素 akj = 1 意味着存在边<vk , vj> .

结论:如果从某些结点 vk引出的边,能同时终止于结点 vi 和 vj ,则这些起始结点 vk 的数目就是 bij 的值,

  特别地,当 i = j 时,元素 bii 的值就是结点 vi 的引入次数

 

主对角线上的数,表示结点 i 的引入次数

 1.5.2.3A(n) 的元素的意义

 设有向图 G = <V , E> 的邻接矩阵为  A = ( aij ),则 A(2) 的元素

分析:元素 aik = 1 意味着存在边<vi , vk> .
  元素 akj = 1 意味着存在边<vk , vj> .

所以,元素 aij(2) 的值表示从结点 vi 到 vj 存在长度为 2 的不同路径的条数。

结论: A(n) 的元素 aij(n) 的值表示从结点 vi 到 vj 存在长度为 n 的不同路径的条数。
特别,对角线上的元素 aii(n) 表示经过结点 vi的长度为 n 的不同回路的条数。

 例如

A2 表示 i 和 j 之间具有长度为2的路径数

A3 表示 i 和 j 之间具有长度为3的路径数

A表示 i 和 j 之间具有长度为4的路径数

 

1.5.2.4可达性矩阵

 

注:bij 表示从结点 vi 到 vj 有长度分别为 1,2,3,4 的不同路径总数。
此时, bij ≠ 0,表示从 vi 到 vj 是可达的。
bij = 0,表示从 vi 到 vj 是不可达的。因此, bij 表明了结点间的可达性。

 定义:

设 G = <V , E> 是简单有向图,其中 |V|=n( n ? I+),定义一个 n?n 矩阵 P,它的元素为:

则P称为图G的可达性矩阵

 

注:由矩阵 Bn 可计算出可达性矩阵 P,其方法是:若 Bn中(i , j)元是非“0”元素,则令对应的 pij = 1,否则令 pij = 0 。

 例如:若

 

 

1.5.2.5可完全关联矩阵

 定义:

设无向图G = <V , E> ,
V = {v1 , v2 , … , vn}, E = {e1 , e2 , … , em},
令 B = ( bij )n×m,其中

 

则称B为无向图G的完全关联矩阵

讨论定义:

⑴ 完全关联矩阵为布尔矩阵;
⑵ 对应B中行均为0的结点为孤立结点,只有一个“1”的行的结点一定为悬挂的边,且一定不在任一回路中;
⑶ 全部为1的行的结点必定联结图中所有的结点。

例如

 

 

1.6特殊图

1.6.1欧拉图

定义:

欧拉路径:穿程于图 G 的每条边一次且仅一次的路径。
欧拉回路:穿程于图 G 的每条边一次且仅一次的回路。
欧拉图:具有欧拉回路的图。

 

定理:

 无向连通图 G 具有一条欧拉路径,当且仅当 G 具有零个或两个奇数度数的结点。

推论:

无向连通图 G 具有一条欧拉回路(欧拉图),当且仅当图G 所有结点度数全为偶数。

例如:用定理解决哥尼斯堡桥的问题

 

 

定理:

有向连通图 G 具有欧拉回路,当且仅当 G中每一个结点的引入次数等于引出次数,即Deg+(v)= Deg-(v) .

 

 定理:

有向连通图 G 具有欧拉路径,当且仅当除了二个结点(其中一个的引入次数比引出次数大1,

另一个的引入次数比引出次数小1)以外的所有结点的引入次数等于引出次数,即Deg+(v)= Deg-(v) .

 

 1.6.2 哈密尔顿图

定义

哈密尔顿路径:穿程于无向图 G 的每一个结点一次且仅一次的路径。
哈密尔顿回路:穿程于无向图 G 的每一个结点一次且仅一次的回路。
哈密尔顿图:具有哈密尔顿回路的图。

到目前为止,还没有找到哈密尔顿路径存在的充分必要条件。下面介绍两个定理。

 

定理:

设 G = < V , E > 是具有n 个结点的简单无向图,若在 G 中每一对结点次数之和大于或等于(n-1),

则在 G 中一定存在一条哈密尔顿路径。

 注:此定理是充分条件,而不是充分必要条件

例如:n=7,G = <V , E > 见图:每对结点次数为4<7-1=6,但确有一条汉密尔顿路径。

 

定理:

若图 G = < V , E > 是哈密尔顿图,则对于结点集 V 的每个非空真子集 S 均有
W( G ―S ) ≤ |S| 成立,
其中 W(G-S) 表示从G中删除S后,所得图的连通分图个数; |S| 表示 S 中的结点数。

 

2.树与生成树

2.1无向树(树)

2.1.1定义

连通的且无简单回路的无向图称为无向树,简称

 

专用名词
树叶(终点):树中度数为1的结点。
分枝点(内点):树中度数大于1的结点。
森林:每个连通分图均为树的无向图。

2.1.2树的性质

设T是一棵树,vi,vj 为T中两个不同的结点,则:
1) vi 和 vj 仅有一条路径相连通。
2) 在T中加一条边{ vi , vj },则由此而形成 的图,仅有一个回路。

 

在一棵(n , e)树中有e=n-1。(n表示结点数,天堂鸟娱乐返点优惠:e表示边数)

设F是由 t 棵树组成的(n , e)森林,则有e=n-t。

 

在结点大于2的(n , e)树中,所有结点的度数之和为2(n-1)

 

在任一(n ≥ 2)的树T中,至少有二片树叶。

 

2.2生成树

2.2.1定义

一个无向图G的生成子图是树TG,则称TG是G的生成树(支撑树)。

讨论定义:

1) G的生成树不是唯一的。

2)如何在连通图G中寻找一棵生成树:

①若G没有循环,则G本身就是一棵树;

②若G仅有一条循环,从此循环中删去一条边,仍保持图的连通性,得到一棵生成树。

③若G有多条循环,则逐个对每条循环重复②中操作,直到打断G中所有循环,得到一棵生成树为止。

 

定理:

任何连通无向图至少有一棵生成树

给定一个连通图,寻找其生成树的数目是图论中树的计数问题

含 n (n>1)个结点的标记完全图Kn 有 nn-2 棵标记生成树

 

定义:

生成树T中的边称为树枝,不在生成树T中但属于图G的边,称为树T的弦,弦的集合称为树T的补。

在一个连通赋权图中,树枝的权之和为最小的生成树称为最小生成树。

 

Kruskal算法:

设G有n个结点,m条边,先将G中所有边按权的大小次序进行排列,不妨设:

W(e1) < W(e2) < … < W(em),

①k←1,A←Ø。

②若AU{ek}导出的子图中不包含简单循环,则A ← A U{ek}

③若A中已有n-1条边,则算法终止,否则K← K+1,转至②。

这一算法假设G中权均不相同,对于边权任意情况也完全适用。这时求得的最小生成树不唯一

 

2.3有向树与根树

定义:

若有向图在不考虑边的方向时是一棵树,称之为有向树。

定义:

一棵有向树,如果恰有一个结点的入度为0,其余所有结点的入度都为1,则称为根树。入度为0的结点称为根,出度为0的结点称为叶,出度不为0的结点称为分枝点或内点。任何结点的级(高度)是从根出发到该结点的路径长度(边的条数)。

定义:

指明了根树中结点或边的次序的树为有序树。在有序树中,如每个结点有明确级,同一级的结点排在同一行,并明确它们位置,则这样的树称位置树

定义:

在根树中,若每一个结点的出度小于或等于m,则称这棵树为m叉树。若每个结点的出度恰好等于m或零,则称这棵树为完全m叉树,若其所有树叶层次相同,称为正则m叉树。

特别,当m=2时,称为二叉树。

很多实际问题可用二叉树或m叉树表示。任何一棵有序树都可以把它改写为一棵对应的二叉树。

定义:

在有向树T中,由结点V和它的所有子孙所构成的结点子集V’以及从V出发的所有有向路中的边所构成的边集E’组成T的子图

方法:

设有序树T中结点Vi 的r棵子树有根Vi1, Vi2 , …, Vir,其顺序自左向右,则在二叉树T’中Vi1是Vi 的左儿子,Vi2是Vi1的右儿子,Vi3是Vi2的右儿子….,Vir是Vir-1的右儿子。

 

posted @ 2019-06-16 18:49 Zander_Zhao 阅读(...) 评论(...) 编辑 收藏
优博娱乐(上搜博网) 双色球电子游戏直营网 现在发牌打龙虎技巧网上娱乐场 申博太阳城手机软件 澳门英皇官网开户
凯时娱乐网站直营网 XTD旗舰馆娱乐平台注册 澳门金沙导航页 東北二人刨手機版下載 m5彩票代理
bet36体育投注手机app 第一彩票 网络骰宝玩法 腾讯分分彩热号 网络赌博反水官网
老虎机游戏手机app版下载 优博时时彩投注平台登入 澳门金沙导航登入 博彩公司大全手机app ag5858的网址导航