图论⼀：基本概念
⼀、图的基本概念
（⼀）图的点和边1、图的定义：⼀个图G=（V,E）由顶点集V和边集E组成。
2、边：⼀个点对（v,w），分为有向边，和⽆向边；
3、图的分类：有向图（点对是有序的），⽆向图（点对是⽆向的）
4、点与边的关系：顶点v与w邻接，当且仅当（v,w）属于E
5、权：每条边除了有顶点（v,w）有时还有⾃⼰的值或权。
（⼆）图的路径1、路径定义：图的路径是⼀个顶点序列w1,w2,w3,……,wn，使得（wi，wi+1）属于E，（1<=i 2、路径的长： （1）⽆权路的路径的长度是该路径上的长度 （2）有权路径的路径的长度是该路径上所有边的权值之和3、环：⼀个从顶点到它⾃⾝的边（v,v），环的长度是1 4、简单路径：⼀条路径上所有顶点都是互异的，（但第⼀个和最后⼀个可能相同）。 （三）圈1、有向图的圈满⾜w1=wn且长度⾄少为1的⼀条路径，且每条边都是互异的 （eg：⽆向图的（u，v，u）不是圈，因为（u，v）和（v,u）是同⼀条边）2、⼀个⽆圈图称为DAG （四）连通图1、（⽆向图）连通：如果⼀个⽆向图图的每⼀个顶点到其他顶点都有⼀条路径，就称这个图是连通图 2、有向图： （1）强连通图：⼀个有向图的每⼀个顶点到其他顶点都有⼀条路径，这个图就是强连通的 （2）弱连通图：⼀个有向图不是强连通涂，但是去掉⽅向的这个⽆向图是连通图。
图论复习题
第一章 图
主要内容：
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,……,xn}，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。（38题）
10．若图G是简单图， 且(1)(2)2ppq，则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）
图论及应用参考答案
图论及应用参考答案
图论是数学中的一个重要分支，研究的是图的性质和图之间的关系。图由节点（顶点）和边组成，节点代表对象，边代表对象之间的关系。图论不仅在数学中有广泛的应用，也在计算机科学、物理学、生物学等领域中发挥着重要的作用。本文将介绍图论的基本概念和一些应用。
一、图论的基本概念
1. 图的类型
图分为有向图和无向图。有向图中的边有方向，表示节点之间的单向关系；无向图中的边没有方向，表示节点之间的双向关系。
2. 图的表示方法
图可以用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，其中的元素表示节点之间是否有边相连；邻接表是一个链表数组，数组中的每个元素对应一个节点，链表中存储了该节点相邻的节点。
3. 图的性质
图的性质包括节点的度、连通性和路径等。节点的度是指与该节点相连的边的数量；连通性指的是图中任意两个节点之间是否存在路径；路径是指由边连接的节点序列。
二、图论在计算机科学中的应用
1. 最短路径算法
最短路径算法是图论中的经典问题之一，它用于计算图中两个节点之间的最短路径。著名的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。这些算法在网络路由、地图导航等领域中有广泛的应用。
2. 最小生成树算法
最小生成树算法用于找到一个连通图的最小生成树，即包含所有节点且边的权重之和最小的子图。普里姆算法和克鲁斯卡尔算法是常用的最小生成树算法。这些算法在电力网络规划、通信网络设计等领域中有重要的应用。
3. 图的着色问题
图的着色问题是指给定一个图，将每个节点着上不同的颜色，使得相邻节点之间的颜色不同。这个问题在地图着色、任务调度等方面有实际应用。
三、图论在物理学中的应用
1. 粒子物理学
在粒子物理学中，图论被用来描述和分析粒子之间的相互作用。图论模型可以帮助研究粒子的衰变、散射等过程，为理解物质的基本结构提供了重要的工具。
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、在图论中，完全图是⼀个简单图，且任意⼀个顶点都与其它每个顶点有且只有⼀条边相连接。
