离散数学图的基本概论

离散图论知识点总结一、基本概念图（Graph）是离散数学中的一个重要概念，它由顶点集合V和边集合E组成。

一般用G （V，E）来表示，其中V={v1,v2,…,vn}是有限非空集合，E是V中元素的无序对的集合。

图分为有向图和无向图。

无向图中的边是无序的，有向图中的边是有序的。

图中存在一些特殊的图，比如完全图、树、路径、回路等。

二、图的表示方法1. 邻接矩阵邻接矩阵是一种常见的图的表示方法，它使用一个二维数组来表示图的关系。

对于一个n 个顶点的图，邻接矩阵是一个n*n的矩阵A，其中A[i][j]表示顶点i到顶点j之间是否存在边。

对于无向图，A[i][j]=1表示顶点i与顶点j之间存在边，A[i][j]=0表示不存在。

对于有向图，A[i][j]=1表示i指向j的边存在，A[i][j]=0表示不存在。

2. 邻接表邻接表是另一种常见的图的表示方法。

它将图的信息储存在一个数组中，数组的每个元素与图的一个顶点相对应。

对于每个顶点vi，数组中储存与该顶点邻接的顶点的信息。

邻接表可以用链表或者数组来表示，链表表示的邻接表比较灵活，但是在查找某个边的相邻顶点时需要遍历整个链表。

三、图的性质1. 度图中每个顶点的度是与其相邻的边的数目。

对于无向图，顶点的度等于与其相邻的边的数目；对于有向图，则分为入度和出度。

2. 连通性对于无向图G，若图中任意两个顶点都有路径相连，则称图G是连通的。

对于有向图G，若从任意一个顶点vi到任意一个顶点vj都存在路径，则称G是强连通的。

3. 路径和回路路径是指图中一系列的边，连接图中的两个顶点；回路是指起点与终点相同的路径。

路径的长度是指路径中边的数目。

4. 树和森林一个无向图，如果是连通图且不存在回路，则称为树。

一个无向图，若它不是连通图，则称为森林。

四、图的常见算法1. 深度优先搜索（DFS）深度优先搜索是一种用于图的遍历的算法，它从图的某个顶点vi出发，访问它的所有邻接顶点，再对其中未访问的顶点继续深度优先搜索。

图论部分第七章、图的基本概念7.1无向图及有向图无向图与有向图多重集合：元素可以重复出现的集合无序积:A,、B={（x,y） | x A y B}定义无向图G=<V,E>,其中（1）顶点集V二一，元素称为顶点（2）边集E为V 7的多重子集，其元素称为无向边，简称边•例如,G=<V,E>如图所示,其中V={V1, V2,…,V5}, E={（V1,V1）,（V1,V2）,（V2,V3）,（V2,V3）,（V2,V5）,（V1,V5）,（V4,V5）},定义有向图D=<V,E>,其中（1）V同无向图的顶点集，元素也称为顶点（2）边集E为V V的多重子集，其元素称为有向边，简称边•用无向边代替D的所有有向边所得到的无向图称作D的基图，右图是有向图, 试写出它的V和E注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的通常用G表示无向图,D表示有向图,也常用G泛指无向图和有向图，用e k表示无向边或有向边.V(G), E(G), V(D), E(D): G 和D 的顶点集,边集.n阶图：n个顶点的图有限图:V, E都是有穷集合的图零图:E=..平凡图：1阶零图空图：V=.顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G=<V,E>的一条边,称v i,v j 为e k 的端点,e k与v i (v j)关联.若v i = v j,则称e k与v i (v j)的关联次数为1;若v i = v j, 则称e k为环，此时称e k与v i的关联次数为2;若v i不是e k端点，则称e k与v i的关联次数为0.无边关联的顶点称作孤立点.定义设无向图G=<V,E> , v i,v j V, e k,e i E,若(v i,v j) E,则称v i,v j相邻;若e k,e i 至少有一个公共端点,则称e k,e i相邻.对有向图有类似定义.设e k= v i,v j是有向图的一条边，又称v i是e k的始点，v j是e k的终点，v i邻接到v j, v j邻接于v i.v 的入度d _(v)： v 作为边的终点次数之和邻域和关联集邻域和关联集设无向图G 灼IX®，的邻域畀©)=例气〒£伍”如司①八炕］、的R ］邻域 V(v)=A r (v)U{v}［的关轶集J®)=3E £(G)2与咲联}设有向图D 於玖Q'的百堆乎集册护側進E (D)AV 惚Y E(G/\T '的先極元集 Zy (i-r («kcl ；(P )A<a s r>C E(Q AW } *的邻域 A^(v )=r ；(v )UJK (v )、的团邻域 哥何fV 』(i ・)u 阴顶点的度数 设G=<V,E>为无向图,v V,v 的度数(度)d(v): v 作为边的端点次数之和悬挂顶点：度数为1的顶点悬挂边：与悬挂顶点关联的边G 的最大度：(G)=max{d(v)| v V}G 的最小度 (G)=min{d(v)| v V}例如 d(v 5)=3, d(v 2)=4, d(v i )=4, ：(G)=4,、(G)=1,v 4是悬挂顶点,e 7是悬挂边,e i 是环设D=<V,E>为有向图，v V,v 的出度d +(v): v 作为边的始点次数之和v 的度数(度)d(v): V 作为边的端点次数之和d(v)= d +(v)+ d -(v)D的最大出度+(D),最小出度、+(D)最大入度厶TD),最小入度_(D)最大度. (D),最小度、(D)例如d+(a)=4, d-(a)=1, d(a)=5,d+(b)=O, d-(b)=3, d(b)=3,+(D)=4, +(D)=0, ："(D)=3,"(D)=1, (D)=5, (D)=3.握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数•证G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度.有向图的每条边提供一个入度和一个出度，故所有顶点入度之和等于出度之和等于边数推论在任何无向图利有向图中，奇度顶点的个数必为肉数一证设空彷任意團，令曲伪翻！叫叫V|t6l^(v)为朗；则FlU V^V,卩小岭虫,由握手立理可知hH ■工兀)-XrfM + E rf W" M 心由于如罗W)均为他4,所以卩2)也为偶埶但因为吁中顶融齢防奇数，所以强诡为儼L图的度数列设无向图G的顶点集V={v i, V2, ••»*}G 的度数列：d(v i), d(V2),…d (v n)如右图度数列：4,4,2,1,3设有向图D的顶点集V={V1, V2,…v n}D 的度数列：d(v i), d(V2), •••d (v n)D 的出度列:d+(v i), d+(v2), --d+(v n)D 的入度列:d_(v i), d _(v2),…d Iv n)如右图度数列：5,3,3,3出度列:4,0,2,1入度列:1,3,1,2例1 (3,3,3,4), (2,3,4,6,8)能成为图的度数列吗?解不可能•它们都有奇数个奇数•例2已知图G有10条边，4个3度顶点,其余顶点的度数均小于等于2,问G 至少有多少个顶点？解设G有n个顶点•由握手定理，4 3+2 (n-4)_2 10解得n _8例3证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.证用反证法.假设存在这样的多面体，作无向图G=<V,E>, 其中V={v | v为多面体的面},E={(u,v) | u,v V u 与v 有公共的棱u=v}.根据假设，|V|为奇数且- v V, d(v)为奇数.这与握手定理的推论矛盾.多重图与简单图定义(1)在无向图中,如果有2条或2条以上的边关联同一对顶点，则称这些边为平行边，平行边的条数称为重数.⑵在有向图中，如果有2条或2条以上的边具有相同的始点和终点，则称这些边为有向平行边，简称平行边，平行边的条数称为重数.(3) 含平行边的图称为多重图.(4) 既无平行边也无环的图称为简单图.注意:简单图是极其重要的概念匕和勺是平行边蓮数为2临和旳不是平行边不是简单图图的同构定义 设G i =<V i ,E i >, G 2=<V 2,E 2>为两个无向图(有向图)，若存在双射函数f: V i >V 2,使得对于任意的V i ,V j V i ,(V i ,V j )・ E l ( <V i ,V j > E i )当且仅当(f(V i ),f(V j )) E 2( Vf(V i ),f(V j )> E 2), 并且,(Vi ,V j )( <V i ,V j >)与(f(V i ),f(V j ))( <f(V i ),f(V j )>) 的重数相同，则称G i 与G 2是同构的，记作G i 三G 2.几点说明：图之间的同构关系具有自反性、对称性和传递性 .能找到多条同构的必要条件，但它们都不是充分条件：① 边数相同，顶点数相同② 度数列相同(不计度数的顺序)③ 对应顶点的关联集及邻域的元素个数相同，等等若破坏必要条件，则两图不同构至今没有找到判断两个图同构的多项式时间算法令和◎是平行边 重数为2 不是例1试画岀4阶3条边的所柯E同构的无向简单图 E K R例2判断下述每一对圉是否同构:度教列不同不同构不同构入(岀】度列不⑶度数列相同但不同构为什么？完全图：n阶无向完全图K n：每个顶点都与其余顶点相邻的n阶无向简单图.简单性质：边数m=n(n-1)/2,「=；=n-1n阶有向完全图：每对顶点之间均有两条方向相反的有向边的n阶有向简单图•简单性质：边数m=n(n-1),八=：=2(n-1),A+=6+=A_=6 _=n_1(1)为§阶完全图乓⑵为3阶有向完全图(3)称为彼得森图(1) ⑵子图：定义设G=<V,E>, G =<V ,E >是两个图(1)若V匸V且E亠E,则称G为G的子图，G为G 的母图，记作G G⑵若G G且V =V，则称G为G的生成子图⑶若V V或E E，称G为G的真子图⑷设V V且V ,以V •为顶点集，以两端点都在V中的所有边为边集的G的子图称作V 的导出子图，记作G[V ]⑸设E E且E ,以E为边集,以E中边关联的所有顶点为顶点集的G的子图称作E的导出子图，记作G[E ]补图：定义设G=<V,E>为n阶无向简单图，以V为顶点集,所有使G成为完全图K n 的添加边组成的集合为边集的图，称为G的补图，记作匚. 若Gm ■，则称G是自补图.例对上一页K4的所有非同构子图，指出互为补图的每一对子图，并指出哪些是自补图.7.2通路、回路、图的连通性简单通（回）路,初级通（回）路，复杂通（回）路定义给定图G=<V,E> （无向或有向的），G中顶点与边的交替序列-=v o e i v i e2 …e i v i，（1）若_i（1半I）, V i—1, V i是e i的端点（对于有向图,要求V i-1是始点,V i是终点），则称】为通路，V0是通路的起点，V I是通路的终点,I为通路的长度.又若V0=v l，则称丨为回路•⑵若通路（回路）中所有顶点（对于回路,除V O=V l）各异，贝U称为初级通路（初级回路）.初级通路又称作路径，初级回路又称作圈.（3）若通路（回路）中所有边各异,则称为简单通路（简单回路）,否则称为复杂通路（复杂回路）.说明：表示方法①用顶点和边的交替序列（定义）,如-=v o e i v i e2…e i v i②用边的序列,如-=e i e2…e i③简单图中，用顶点的序列，如】=V0V1…v i④非简单图中，可用混合表示法，如-=v o v i e2v2e5v3v4v5环是长度为1的圈，两条平行边构成长度为2的圈.在无向简单图中，所有圈的长度一3;在有向简单图中，所有圈的长度一2.在两种意义下计算的圈个数①定义意义下在无向图中，一个长度为1（1一3）的圈看作21个不同的圈.如v o v i v2v o ,v i v2v o v i , v2v0v l v2, v0v2v l v0 , v l v0v2v1 , v2v l v0v2 看作6 个不同的圈.在有向图中，一个长度为l（l—3）的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的，因而是1个圈.定理在n阶图G中，若从顶点v i到v j （v i=v j）存在通路，则从v i到v j存在长度小于等于n-1的通路.推论在n阶图G中，若从顶点v到v j (v i=v j)存在通路，则从v i到v j存在长度小于等于n—1的初级通路.定理在一个n阶图G中，若存在w到自身的回路，则一定存在v i到自身长度小于等于n的回路.推论在一个n阶图G中，若存在v i到自身的简单回路，则一定存在长度小于等于n的初级回路.无向图的连通性设无向图G=<V,E>,u与V连通：若u与V之间有通路.规定u与自身总连通.连通关系R={<u,v>| u,v V且u、v}是V上的等价关系连通图:任意两点都连通的图.平凡图是连通图.连通分支:V关于连通关系R的等价类的导出子图设V/R={V I,V2,…丫心G[V i], G[V2], ••G[V k]是G的连通分支,其个数记作P(G)=k.G是连通图二p(G)=1短程线与距离u与V之间的短程线：u与V之间长度最短的通路(u与V连通)u与V之间的距离d(u,v): u与V之间短程线的长度若u与v不连通,规定d(u,v)= g性质:d(u,v)_O,且d(u,v)=O ：= u=vd(u ,v)=d(v,u)d(u ,v)+d (v,w) _d(u ,w)点割集与割点记G-v:从G中删除v及关联的边G-V :从G中删除V中所有的顶点及关联的边G-e :从G中删除eG-E：从G中删除E 中所有边定义设无向图G=vV,E>, V V,若p(G-V )>p(G)且-V V , p(G-V )=p(G),则称V •为G的点割集.若｛v｝为点割集，则称v为割点.刑仙旳h轴杲点割集必星割虐.｛%叫;是点剖隼吗？边割集与割边(桥)定义设无向图G=<V,E>, E E,若p(G-E )>p(G)且-E - E , p(G-E )=p(G),则称E为G的边割集.若｛e｝为边割集，则称e 为割边或桥.在上一页的图中，｛e i,e2｝，｛e i,e3,e5,e6｝，｛e8｝等是边割集，e8是桥，｛e7,e9,e5,e6｝是边割集吗?几点说明:K n无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p（G-E ）=2若G连通，V为点割集，贝U p（G-V ）_2有向图的连通性设有向图D=<V,E>u可达V： u到V有通路.规定u到自身总是可达的.可达具有自反性和传递性D弱连通（连通）:基图为无向连通图D单向连通：-u,v・V，u可达v或v可达uD强连通：-u,v • V，u与v相互可达强连通=单向连通=弱连通定理（强连通判别法）D强连通当且仅当D中存在经过每个顶点至少一次的回路定理（单向连通判别法）D单向连通当且仅当D中存在经过每个顶点至少一次的通路例下图⑴强连通，（2惮连通，（3｝弱连诵(1) (2) ⑶有向图的短程线与距离u到v的短程线：u到v长度最短的通路（u可达v） u与v之间的距离d<u,v>: u到v 的短程线的长度若u不可达v,规定d<u,v>=x.性质：d<u,v>_0,且d<u ,v>=0 = u=v d<u,v>+d<v,w> -d<u ,w>注意：没有对称性7.3图的矩阵表示无向图的关联矩阵定义设无向图G=<V,E>, V={v i, V2,…“*}, E={e i, e2,…,e m},令m ij为v i与e j 的关联次数，称(m ij)n m为G的关联矩阵，记为M(G).性质(1)每一列恰好有两个1或一个2(2) tf-U"⑴«)(+)平行边的列相同有向图的关联矩阵定义设无环有向图D=<V,E>, V={v1, v2, ••»・},E={e1, e2, …e m},令1 片为勺的始点tn严0 »y与弓不关联片为弓的终点则称臨儿伪。

第十四章图的基本概念§1 图定义设A,B是两个集合，称{{a,b}|a∈A,b∈}B 为A与B的无序积，记为A&B；{a,b}称为无序对。

后面，把{a,b}记为(a,b)，且允许a=b；对无序对(a,b)，有(a,b)=(b,a)。

定义设G =〈V,E〉是一个序偶，其中(1) V是非空集合(2) E⊆V&V，（E中元素可重复出现）则称G是一个无向图。

此时，称V为G的顶点集，记为V(G)，V中的元素称为G的顶点；称E为G的边集，记为E(G)，E中的元素称为G的无向边。

定义设D=〈V,E〉是一个序偶，其中(1) V是非空集合(2) E⊆V×V（E中元素可重复出现）则称G是有向图。

此时，称V为D的顶点集，记为V(D)，V中的元素称为D的顶点；称E为D的边集，记为E(D)，E中的元素称为D的有向边。

图的图示注①有时G既表示无向图又表示有向图，可统称为图。

②若V(G),E(G)均为有穷集，则称G为有限图。

对有限图G，称|V(G)| 为G的阶数。

③对e∈E(G)，称e出现的次数为e的重数，这些相同的边称为平行边（或重边）。

④当V(G)=∅时，称G为空图，记为∅。

⑤ 当E (G )= ∅时，称G 为零图，n 阶零图记为N n ；特别地，称N 1为平凡图。

⑥ 用u ,v ,v 1,v 2,"表示顶点，用e ,e 1,e 2,"表示边，称这样的图为标定图。

否则，称为非标定图。

⑦ 把无向图G =〈V ,E 〉的每条无向边确定一个方向后得到一个有向图D ，称D 为G 的定向图。

反之，去掉有向图D =〈V ,E 〉的每条有向边的方向后得到一个无向图G ，称G 为D 的基图。

⑧ 设G 是一个图，e ∈E (G )。

若e =(v i ,v j ) 或e =〈v i ,v j 〉，则称v i ,v j 为e 的端点，称v i ，v j 与e 是关联的。

当v i ≠v j 时，称e 与v i 或e 与v j 的关联次数为1；当v i =v j 时，称e 为环，e 与v i 的关联次数为2；对 (), ,l l i l j v V G v v v v ∈≠≠，称e 与v l 的关联次数为0。

图论是离散数学的一个分支，研究图的性质和图上的问题。

图是由结点和边组成的一种抽象数据结构，可以用来描述现实世界中的各种关系和连接。

本文将介绍一些图的基本概念和算法。

在图中，结点表示实体，边表示结点之间的关系。

一张图可以用G=(V, E)表示，其中V为结点的集合，E为边的集合。

边可以有方向（有向图）或没有方向（无向图），也可以有权重（带权图）或没有权重（不带权图）。

图的基本概念中，最常见的是路径和回路。

路径是图中的一条边的序列，每个边连接两个结点。

回路是一条路径，起点和终点相同。

如果一条路径中没有重复的结点，那么它就是一条简单路径。

连接结点之间的路径可以通过深度优先搜索（DFS）和广度优先搜索（BFS）来寻找。

DFS以栈为数据结构，先找到一个结点，然后再找它的邻居结点，如此往复，直到找到目标结点或者所有结点都被访问过。

BFS以队列为数据结构，先找到一个结点，然后找它的所有邻居结点，如此往复，直到找到目标结点或者所有结点都被访问过。

除了DFS和BFS，图中还有其他一些重要的算法和问题。

最短路径算法是用来找到两个结点之间最短路径的算法，其中最著名的是狄克斯特拉算法和弗洛伊德算法。

狄克斯特拉算法适用于没有负权边的图，通过不断更新起点到每个结点的最短距离来寻找最短路径。

弗洛伊德算法适用于任意有向图，通过不断更新任意两个结点之间的最短距离来寻找最短路径。

最小生成树算法是用来找到一个无环且连通的子图，该子图包含所有结点并且边的权重之和最小的算法。

其中最著名的是普里姆算法和克鲁斯卡尔算法。

普里姆算法从一个起始结点出发，每次选择与该结点最近的未访问结点，直到所有结点都被访问过。

克鲁斯卡尔算法一开始将每个结点都看作一个独立的树，然后每次选择权重最小的边，如果该边连接的两个结点不在同一棵树中，就将它们合并为一棵树。

图的基本概念和算法在离散数学中起到了至关重要的作用。

图论不仅仅可以用于计算机科学领域，还可以应用到物流规划、社交网络分析、电路设计等各个领域。