图论--图的基本概念

格式：pdf
大小：108.03 KB
文档页数：2

图论--图的基本概念

1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组，其中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✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。

通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。

与1.1，1.2有关的⼀些概念和定义：

（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。

（2）顶点数称作图的阶，n个顶点的图称作n阶图。（3）⼀条边也没有的图称作零图，n阶零图记作Nn。1阶零图N1称作平凡图。平凡图只有⼀个顶点，没有边。

（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作

Ø。（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。（7）若两个顶点vi与vj之间有⼀条边连接，则称这两个顶点相邻。若两条边⾄少有⼀个公共端点，则称这两条边相邻。

1.3在⽆向图中，如果关联⼀对顶点的⽆向边多余1条，则称这些边为平⾏边，平⾏边的条数称为重数。在有向图中，如果关联⼀对顶点的有向边多余1条，并且这些边的始点与终点相同（也就是它们的⽅向相同），则称这些边为平⾏边。含平⾏边的图称作多重图，既不含平⾏边也不含环的图称作

简单图。

1.4设G=为⽆向图，∀v∈V,称v作为边的端点的次数为v的度数，简称为度，记作dG(v)。在不发⽣混淆的时候，略去下标G，简记为d(v)。设D=

为有向图，∀v∈V，称v作为边的始点的次数为v的出度，⼰作d

D+(v)，简记为d+(v)。称v作为边的终点的次数为v的⼊度，记作d

D-(v)，简记为

d-(v)。称d+(v)+d-(v)为v的度数，⼰作d

D(v)，简记为d(v)。

注意：在⽆向图中，顶点v上的环以v作2次端点。在有向图中，顶点v上的环以v作⼀次始点和⼀次终点，共作2次端点。

另外，称度数为1的顶点为悬挂顶点，与它相关联的边称作悬挂边。度为偶数（奇数）的顶点称作偶度（奇度）顶点。

1.5设G=,G

2,E

2>为两个⽆向图（两个有向图），若存在双射函数f：V

1→V2，使得∀vi,v

j∈V1,(v

i,v

j)∈E

1当且仅当

(f(v

i),f(v

j))∈E

i,v

j>∈E

1当且仅当

j>∈E

2)，并且(v

i,vj)与(f(v

i),f(v

j))(

i,v

j>与

i),f(v

j)>的重数相同，则称G

1与G2同构，记作G1≅G2。

注意：≅是等价关系，具有⾃反性、对称性和传递性。⾄今都没有找到判断两个图是否同构的便于检查的充分必要条件。显然阶数相同、边数相同、

度数列相同等都是必要条件，但都不是充分条件。

1.6（1）设G为n阶⽆向简单图，若G中每个顶点均与其余的n-1个顶点相邻，则称G为n阶⽆向完全图，简称为n阶完全图，记作K

n(n≥1)。

（2）设D为n阶有向简单图，若D中每个顶点均与其余的n-1个顶点相邻，则称D为n阶有向完全图。

（3）设D为n阶有向简单图，若D的基图为n阶⽆向完全图K

n，则称D为n阶竞赛图。

结论：n阶⽆向完全图边数为，n阶有向完全图边数为n(n-1)，n阶竞赛图的边数。

1.7设G=，G'=为两个图（同为⽆向图或同为有向图），若V'⊆V且E’⊆E，则称G‘为G的⼦图，G为G‘的母图，记作G‘⊆G。⼜若V'⊂V或

E’⊂E，则称G‘为G的真⼦图。若V'=V，则称G’为G的⽣成⼦图。

设G=，V

1⊂V且V1≠∅，称以V

1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的⼦图，记作G[V1]。⼜设E

1⊂E且

1≠∅，称以E

1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的⼦图，记作G[E1]。

1.8设G=为n阶⽆向简单图，令E*={(u,v)|u∈VΛv∈VΛu≠vΛ(u,v)∉E}，称G*=为G的补图。若G≅G*，则称G为⾃补图。

2.握⼿定理：

2.1在任何⽆向图中，所有顶点的度数之和等于边数的2倍。

2.2在任何有向图中，所有顶点的度数之和等于边数的2倍；所有顶点的⼊度之和等于所有顶点的出度之和，都等于边数。

推论：任何图（⽆向图或有向图）中，奇度顶点的个数是偶数。

3.通路与回路：

3.1设G= (P,L)是图，v,v'是G中两点。如果(1)v

0=v,v

n=v'(2)v

i与vi+1相邻，0≤i≤n。则由G中点组成的序列(v0,v

1,....v

n) 称为从v到v'的长度为n的路。这

⾥ v, v'是图G中未必不同的两点，v0,v

1,....v

n中也允许有重复。

3.2设G = (P,L)是图，如果(1)v

0,....v

n-1互不相同(2)v1,....v

n互不相同。则(v0,v1,.....v

n) 是 G 中从v

0到vn的路，称此路为简单路。显然，⼀条简单通路

0,v

1,.....v

n)，除v

0与vn可以相同外，其他任意两点都不相同。

3.3设G=(P,L)是图，G中从点v到⾃⾝的长度不⼩千3的简单路，称为回路。显然，⼀个图G是连通的，当且仅当G中任意两点都是相连的。

参考资料：离散数学第⼆版（屈婉玲）离散数学结构第⼆版（欧阳丹彤）

图论及其应用

未知驱动探索，专注成就专业

图论及其应用

简介

图论是计算机科学中的一个重要分支，研究的对象是由边与顶点组成的图形结构以及与其相关的问题和算法。图论的应用广泛，涵盖了计算机科学、网络科学、物理学、社会学、生物学等多个领域。本文将介绍图论的基本概念、常用算法以及一些实际的应用案例。

图的基本概念

图由顶点（Vertex）和边（Edge）组成，记作G=(V, E)，其中V为顶点的集合，E为边的集合。图可以分为有向图和无向图两种类型。

有向图

有向图中的边具有方向性，即从一个顶点到另一个顶点的边有明确的起点和终点。有向图可以表示一种有序的关系，比如A到B有一条边，但B到A可能没有边。有向图的表示可以用邻接矩阵或邻接表来表示。未知驱动探索，专注成就专业

无向图

无向图中的边没有方向性，任意两个顶点之间都有相互连接的边。无向图可以表示一种无序的关系，比如A与B有一条边，那么B与A之间也有一条边。无向图的表示通常使用邻接矩阵或邻接表。

常用图论算法

图论中有许多经典的算法，其中一些常用的算法包括：

深度优先搜索（DFS）

深度优先搜索是一种用于遍历或搜索图的算法。通过从起始顶点开始，沿着一条路径尽可能深入图中的顶点，直到无法再继续前进时，返回上一个顶点并尝试下一条路径的方式。DFS可以用于判断图是否连通，寻找路径以及检测环等。

广度优先搜索（BFS）

广度优先搜索也是一种用于遍历或搜索图的算法。不同于深度优先搜索，广度优先搜索逐层遍历顶点，先访问离起始顶点最近的顶点，然后依次访问与起始顶点距离为2的顶点，以此类推。BFS可以用于寻找最短路径、搜索最近的节点等。未知驱动探索，专注成就专业

最短路径算法

最短路径算法用于计算图中两个顶点之间的最短路径。其中最著名的算法是迪杰斯特拉算法（Dijkstra’s Algorithm）和弗洛伊德算法（Floyd’s Algorithm）。迪杰斯特拉算法适用于没有负权边的图，而弗洛伊德算法可以处理带有负权边的图。

图论的基本概念和应用

图论，顾名思义，是研究图的一门数学分支。在计算机科学、网络科学、物理学等领域都有广泛的应用。本文将从图的基本概念入手，介绍图论的基础知识和常见应用。

一、图的基本概念

1.1 图的定义

图是由若干点和若干边构成的。点也被称为顶点，边也被称为弧或者线。一个点可以与任意个点相连，而边则是连接两个点的线性对象。一些有向边可以构成一棵树，而一些无向边则形成了一个回路。

1.2 图的表示

图可以用一张二维平面图像表示。这张图像由若干个点和连接这些点的线组成。这种表示方式被称为图的平面表示。图还可以用邻接矩阵、邻接表、关联矩阵等数据结构进行表示。

1.3 图的类型

根据图的性质，可以将图分为有向图、无向图、完全图、连通图、欧拉图、哈密顿图等。

有向图：边有方向，表示从一个点到另一个点的某种关系。

无向图：边没有方向，表示两个点之间的某种关系。

完全图：任意两个点之间都有一条边，不存在自环。\

连通图：任意两个点之间都有至少一条通路，没有孤立的点。

欧拉图：一条欧拉通路是一条从一点开始经过所有边恰好一次后回到该点的通路。

哈密顿图：经过所有点恰好一次的通路被称为哈密顿通路。

二、图的应用

2.1 最短路径问题

图论在计算机算法中最常见的应用之一就是最短路径问题。在一个有向图中，从一个点到另一个点可能有多条不同的路径，每条路径的长度也可能不同。最短路径问题就是找到两个点之间长度最短的路径。

最短路径问题可以通过深度优先搜索、广度优先搜索等方法来解决，但是时间复杂度通常较高。另外，使用Dijkstra算法、Floyd算法等优化算法可以大大缩短计算时间。

2.2 社交网络

社交网络是图论应用的一个重要领域。在社交网络中，人们之间的关系可以用图的形式表示。例如，在微博网络中，每个用户和他/她所关注的人就可以形成一个有向图。在这种图中，点表示用户，边表示一个人关注另一个人的关系。

通过对社交网络进行图论分析，可以研究用户之间的互动模式，了解到哪些用户之间联系较为紧密，哪些用户是网络中的“大咖”等。这些信息可以帮助企业或者政府制定营销策略，开展促进社会和谐的活动等。

图论知识点

摘要：

图论是数学的一个分支，它研究图的性质和应用。图由节点（或顶点）和连接这些节点的边组成。本文将概述图论的基本概念、类型、算法以及在各种领域的应用。

1. 基本概念

1.1 节点和边

图由一组节点（V）和一组边（E）组成，每条边连接两个节点。边可以是有向的（指向一个方向）或无向的（双向连接）。

1.2 路径和环

路径是节点的序列，其中每对连续节点由边连接。环是一条起点和终点相同的路径。

1.3 度数

节点的度数是与该节点相连的边的数量。对于有向图，分为入度和出度。

1.4 子图

子图是原图的一部分，包含原图的一些节点和连接这些节点的边。

2. 图的类型

2.1 无向图和有向图

无向图的边没有方向，有向图的每条边都有一个方向。

2.2 简单图和多重图

简单图是没有多重边或自环的图。多重图中，可以有多条边连接同一对节点。

2.3 连通图和非连通图

在无向图中，如果从任意节点都可以到达其他所有节点，则称该图为连通的。有向图的连通性称为强连通性。

2.4 树

树是一种特殊的连通图，其中任意两个节点之间有且仅有一条路径。

3. 图的算法

3.1 最短路径算法

如Dijkstra算法和Bellman-Ford算法，用于在加权图中找到从单个源点到所有其他节点的最短路径。

3.2 最大流最小割定理

Ford-Fulkerson算法用于解决网络流中的最大流问题。

3.3 匹配问题

如匈牙利算法，用于解决二分图中的匹配问题。

4. 应用

4.1 网络科学

图论在网络科学中有广泛应用，如社交网络分析、互联网结构研究等。

4.2 运筹学

在运筹学中，图论用于解决物流、交通网络优化等问题。

4.3 生物信息学

在生物信息学中，图论用于分析蛋白质相互作用网络、基因调控网络等。

5. 结论

图论是数学中一个非常重要和广泛应用的领域。它不仅在理论上有着深刻的内涵，而且在实际应用中也发挥着关键作用。随着科技的发展，图论在新的领域中的应用将会不断涌现。