图的基本概念与性质
- 格式:doc
- 大小:66.50 KB
- 文档页数:5
图形的概念知识点总结一、基本概念1. 点:图形的基本构成单位,没有长度、宽度和高度,用大写字母来表示,如A、B、C等。
2. 直线:在平面上无限延伸的线段,用小写字母或者两点的大写字母来表示,如l、AB等。
3. 封闭曲线:由连续点构成的曲线,首尾相连形成一个封闭的图形,如圆等。
4. 边:构成图形的线段,通常用大写字母表示,如AB、BC等。
5. 角:两条线段的交汇,有大小、方向和位置,通常用大写字母表示,如∠A、∠BAC等。
6. 维数:图形的维数是指图形的度量,表征了图形所在空间的维度,包括一维、二维和三维。
7. 多边形:由三条或以上的边构成的封闭图形,多边形的边数由多边形的边数来确定,如三角形、四边形等。
二、基本图形1. 点:没有大小和形状,是最基本的图形,用来构成直线、曲线及其他图形。
2. 直线:由无数个点组成,没有宽度和厚度,可以用两点来确定一条直线。
3. 封闭曲线:由连续的点组成,首尾相连形成一个封闭的图形,通常用来表示圆、椭圆等。
4. 角:由两条线段的交汇构成,可以分为锐角、直角、钝角等。
5. 多边形:由三条或以上的边构成的图形,包括三角形、四边形、五边形等。
6. 圆:由一点到平面上所有点的距离都相等的封闭曲线构成,是一种特殊的多边形。
7. 立体图形:具有三个维度、长度、宽度和高度的图形,包括正方体、长方体、圆柱体等。
三、图形的性质1. 对称性:图形的对称性包括中心对称和轴对称两种。
中心对称是指以图形的中心为对称中心,对折后两部分完全重合;轴对称是指以某条直线为轴,对折后两部分完全重合。
2. 等边性:指图形的所有边都相等,如正三角形、正方形等。
3. 相似性:指两个图形的形状相似,但大小不同。
相似的图形的相似比相等。
4. 包围性:指图形的边界围成的区域称为图形的内部,而不在图形内部的部分称为图形的外部。
5. 周长和面积:图形的周长是指图形的边界的长度总和,面积是指图形所包围的区域的大小。
6. 图形的位置关系:包括相离、相交、内含等不同的位置关系。
图论的基本概念和应用图论是数学中的一个分支,研究的是图的性质和图之间的关系。
图由节点和边组成,节点表示对象,边表示对象之间的关系。
图论的基本概念包括图的类型、图的表示方法、图的遍历算法等。
图论在计算机科学、网络分析、社交网络等领域有着广泛的应用。
一、图的类型图可以分为有向图和无向图两种类型。
有向图中的边有方向,表示从一个节点到另一个节点的关系;无向图中的边没有方向,表示两个节点之间的关系是相互的。
有向图和无向图都可以有权重,表示边的权值。
二、图的表示方法图可以用邻接矩阵和邻接表两种方式来表示。
邻接矩阵是一个二维数组,数组的行和列分别表示图中的节点,数组中的元素表示节点之间的边;邻接表是一个链表数组,数组的每个元素表示一个节点,链表中的每个节点表示与该节点相连的边。
三、图的遍历算法图的遍历算法包括深度优先搜索(DFS)和广度优先搜索(BFS)。
深度优先搜索从一个节点开始,沿着一条路径一直遍历到最后一个节点,然后回溯到上一个节点,再继续遍历其他路径;广度优先搜索从一个节点开始,先遍历与该节点相邻的所有节点,然后再遍历与这些节点相邻的节点,依次类推。
四、图论的应用1. 计算机科学:图论在计算机科学中有着广泛的应用。
例如,图可以用来表示计算机网络中的节点和连接关系,通过图的遍历算法可以实现网络路由和路径规划;图可以用来表示程序中的依赖关系,通过图的遍历算法可以实现代码的分析和优化。
2. 网络分析:图论在网络分析中有着重要的应用。
例如,社交网络可以用图来表示,节点表示用户,边表示用户之间的关系,通过图的遍历算法可以实现社交网络的分析和预测;互联网中的网页可以用图来表示,节点表示网页,边表示网页之间的链接关系,通过图的遍历算法可以实现搜索引擎的排名和推荐算法。
3. 运筹学:图论在运筹学中有着重要的应用。
例如,图可以用来表示物流网络中的节点和路径,通过图的遍历算法可以实现最短路径和最小生成树的计算;图可以用来表示任务调度中的依赖关系,通过图的遍历算法可以实现任务的优化和调度。
图形的所有知识点图形是数学中的一个重要概念,它在几何学、代数学以及其他数学学科中扮演着重要的角色。
在本文中,我们将探讨图形的各种类型和相关概念,以帮助您更好地理解和应用图形知识。
一、基本概念与术语图形是由点和线组成的几何形状。
它由以下基本概念和术语组成:1. 点:图形中最基本的元素,通常用大写字母表示,例如 A、B、C。
2. 线:由两个点之间的直接路径组成,可以是直线、曲线或弧线。
3. 线段:连接两个点的部分,用小写字母表示,例如 AB。
4. 射线:从一个点开始,通过另一个点的路径,表示为以起始点为中心的一个方向。
5. 平行线:在同一平面上不相交且始终保持相同距离的线。
6. 垂直线:形成直角交叉的两条线。
7. 角:由两条射线共享一个公共起点组成。
8. 多边形:由线段组成的封闭图形,例如三角形、四边形和多边形。
二、图形的类型图形可以根据其形状和性质进行分类。
下面是一些常见的图形类型:1. 三角形:由三条线段组成的多边形。
2. 四边形:由四条线段组成的多边形。
3. 圆:由一个固定中心点和与该中心点距离相等的所有点组成的图形。
4. 正多边形:所有边相等且所有角均相等的多边形。
5. 平行四边形:拥有两组平行线的四边形。
6. 梯形:拥有两条平行线段的四边形。
三、图形的性质与公式图形的性质和公式帮助我们计算其各种属性,例如面积、周长和体积。
在下面,我们将介绍一些常见的图形性质和相关公式:1. 三角形:三角形的面积可以通过以下公式计算:面积 = 底边长 ×高 / 2。
周长等于三条边长的和。
2. 四边形:四边形的面积可以通过以下公式计算:面积 = 对角线之积 / 2。
周长等于四条边长的和。
3. 圆:圆的面积可以通过以下公式计算:面积= π × 半径的平方。
圆的周长可以通过以下公式计算:周长= 2 × π × 半径。
4. 矩形:矩形的面积可以通过以下公式计算:面积 = 长 ×宽。
图论中的图的着色与染色问题图论是数学的一个分支,研究的是图的性质和图的应用。
在图论中,图的着色与染色问题是一个经典且重要的研究课题。
图的着色问题是指如何用有限的颜色对图的顶点或边进行染色,使得相邻的顶点或边具有不同的颜色。
本文将介绍图的着色与染色问题的基本概念和应用。
一、图的基本概念1. 无向图和有向图无向图由一些顶点和连接这些顶点的边组成,边没有方向性。
而有向图中,边是有方向性的,连接两个顶点的边有始点和终点之分。
2. 邻接矩阵和邻接表邻接矩阵是一种表示图的方法,用一个矩阵表示图中各个顶点之间的连接关系。
邻接表是另一种表示图的方法,用链表的形式表示图中各个顶点之间的连接关系。
二、图的着色问题图的着色问题是指如何用有限的颜色对图的顶点或边进行染色,使得相邻的顶点或边具有不同的颜色。
图的着色问题有以下两种情况:1. 顶点着色对于无向图或有向图的顶点,通过对每个顶点进行染色,使得图中任何相邻的顶点具有不同的颜色。
这里的相邻顶点指的是通过一条边相连的顶点。
2. 边着色对于无向图或有向图的边,通过对每条边进行染色,使得图中任何相邻的边具有不同的颜色。
这里的相邻边指的是有共同始点或终点的边。
三、图的染色算法对于图的着色问题,有不同的染色算法可以解决。
在这里我们介绍两种常用的染色算法:贪心算法和回溯算法。
1. 贪心算法贪心算法是一种基于局部最优策略的算法。
对于图的顶点着色问题,贪心算法的策略是从一个未染色的顶点开始,将其染上一个可用的颜色,并将该颜色标记为已占用,然后继续处理下一个未染色的顶点。
如果当前顶点没有可用的颜色可染,则需要增加一个新的颜色。
2. 回溯算法回溯算法是一种穷举所有可能性的算法。
对于图的着色问题,回溯算法的策略是从一个未染色的顶点开始,尝试不同的颜色进行染色,如果发现染色后与相邻顶点冲突,就回溯到上一个顶点重新尝试其他颜色,直到所有顶点都被染色。
四、图的着色问题的应用图的着色问题在实际中有广泛的应用。
小学平面图形知识点回顾平面图形是小学数学中的重要内容之一,它是学习几何的基础。
在这篇文章中,我们将回顾小学阶段的平面图形知识点,包括图形的基本概念、性质和分类,帮助同学们达到全面回顾、巩固知识的目的。
一、图形的基本概念1. 点:几何图形的基本单位,用大写字母A、B、C等表示。
2. 线段:两个点之间的部分,用两端点的大写字母表示,例如AB。
3. 直线:无限延伸的线段,用一对大写字母表示,例如AB。
4. 射线:有一个端点,另一端向无穷远延伸的线段,用一个点和一对大写字母表示,例如→AB。
5. 角:由两个射线和一个公共端点构成,用顶点字母表示,例如∠ABC。
6. 三角形:由三条线段组成的图形,用大写字母表示顶点,例如△ABC。
7. 四边形:由四条线段组成的图形,用大写字母表示顶点,例如ABCD。
二、图形的性质1. 三角形的性质:(1) 三角形三边之和等于180度;(2) 内角和相等,外角和为360度;(3) 直角三角形的两个锐角之和为90度;(4) 等边三角形的三个内角均为60度。
2. 四边形的性质:(1) 任意四边形的两个对角线一定相交于一点;(2) 平行四边形的对边相等且平行;(3) 矩形的对角线相等且相互垂直;(4) 正方形是特殊的矩形,具有矩形的性质同时也有边长相等的特点。
三、图形的分类1. 三角形的分类:(1) 按边长分为等边三角形、等腰三角形和一般三角形;(2) 按角度分为直角三角形、锐角三角形、钝角三角形。
2. 四边形的分类:(1) 按边长和角度分为平行四边形、矩形、正方形和一般四边形;(2) 按对角线分为交错四边形和相交四边形。
四、图形的面积计算1. 三角形的面积计算公式为:面积 = 底边长度 ×高 ÷ 2。
2. 矩形的面积计算公式为:面积 = 长 ×宽。
3. 正方形的面积计算公式为:面积 = 边长 ×边长。
4. 平行四边形的面积计算公式为:面积 = 底边长度 ×高。
图形的所有知识点图形是我们日常生活中经常会遇到的一个概念,从简单的几何图形到复杂的三维模型,每一种图形都有自己的特点和应用场景。
本文将介绍图形的所有知识点,包括图形的定义、分类、性质、参数方程、平移、旋转、缩放等内容。
一、图形的定义和分类图形是指在平面或者空间内的有形物体,具有形状和大小的概念。
根据图形的维度可以分为二维图形和三维图形两类。
二维图形包括点、线、面等基本图形,三维图形则包括基本立体如球体、立方体、圆锥体、棱锥体、圆柱体、棱柱体等以及复杂的多面体。
在二维图形中,点是最基本的图形,没有大小,仅仅表示一个位置坐标,用于作为其他图形的基础。
线是由点连接而成,可以表示一条直线或者曲线,根据其长度和形状可分为直线、折线、曲线等。
面是由线或曲线围成的区域,可以分为平面图形和曲面图形两类。
其中平面图形包括三角形、矩形、正方形、梯形、菱形、圆等基本图形,曲面图形则包括弧、扇形、椭圆等。
在三维图形中,球体是最基本的图形,具有无限接近于圆形的表面。
立方体是具有6个相等的正方形面的立体,是最简单的几何体。
棱锥体则是由一个多边形底面和一个顶点连接而成的立体,其中根据底面不同又可以分为三角形棱锥、正四边形棱锥、正五边形等。
圆柱体是由圆形的底面和端面连接而成的立体,同样可以分为任意圆柱、圆柱台等。
多面体则是由平面图形所组成的三维立体,其中最为著名的是五种正多面体,分别是四面体、六面体、八面体、十二面体和二十面体。
二、图形的性质和参数方程每一种图形都有自己的特点和性质,根据图形的性质我们可以对其进行分类和判断。
这里介绍几种最为基本的图形性质。
1. 几何属性几何属性是指各种基本图形具有的标准的属性,包括长度、面积、体积等。
其中长度通常使用直线或曲线的长度表示,面积通常使用平面内形状所覆盖的区域表示,体积则是三维图形内所占据的空间。
2. 对称性对称性是指图形的一部分在沿对称轴将其翻折后可以与另一部分重合。
其中对称轴可以是直线、点、面等。
图论中的基本概念与算法图论是数学的一个分支,研究的是图的性质和图之间的关系。
图是由一些点和连接这些点的边组成的数学结构。
在图论中,我们探索了一些基本的概念和算法,本文将就这些内容进行探讨。
一、图的基本概念1. 顶点(Vertex):图中的一个点被称为顶点,也可以被称为节点或者结点。
2. 边(Edge):图中的边是连接两个顶点的线段,用于表示两个顶点之间的关系。
3. 有向图(Directed Graph):有向图是一种图,其中的边是有方向的,即从一个顶点指向另一个顶点。
4. 无向图(Undirected Graph):无向图是一种图,其中的边没有方向,即两个顶点之间的关系是互相的。
5. 加权图(Weighted Graph):加权图是一种图,每条边都有一个权重或者距离,用于表示顶点之间的距离或者代价。
6. 路径(Path):路径是图中连接两个顶点的边的序列。
7. 环(Cycle):环是一种路径,其起点和终点相同。
二、图的基本算法1. 广度优先搜索(Breadth-First Search,BFS):BFS是一种用于图中遍历或者搜索的算法。
它从一个起始顶点开始,依次访问与之相邻的顶点,然后再访问与这些顶点相邻的顶点,依次类推。
2. 深度优先搜索(Depth-First Search,DFS):DFS是一种递归的遍历算法。
它从一个起始顶点开始,沿着一条路径尽可能深地访问顶点,直到不能继续为止,然后回退并选择另一条路径。
3. 最小生成树(Minimum Spanning Tree,MST):最小生成树是一个无环连通子图,它包含图中的所有顶点,并且总权重最小。
常用的算法有Prim算法和Kruskal算法。
4. 最短路径问题(Shortest Path Problem):最短路径问题是找出图中两个顶点之间的最短路径。
常用的算法有Dijkstra算法和Floyd-Warshall算法。
5. 拓扑排序(Topological Sorting):拓扑排序是一种对有向无环图进行排序的算法。
第3章图的基本概念与性质一、概念图——图可以用集合的形式表示,即图可以表示为一个三元组,包含结点集、边集,以及边与结点对集间的映射.如果用结点对来表示边,则图可以表示成一个由结点集与边集组成的二元组.定义3.1.1图G是一个三元组<V(G),E(G),ϕG>,其中V(G)是一个非空的结点集(或称顶点集),E(G)是边集,ϕG是从边集E(G)到结点偶对(无序偶或有序偶)集上的函数.图定义中的结点偶对可以是有序的,也可以是无序的.有向边、端点——若图中的边e所对应的结点偶对是有序的,记为<a,b>,则称e是有向边(简称弧).a,b分别称为弧的始点与终点,并均称为e的端点.称e是关联于结点a 和b的,结点a和结点b是相、邻的,或称结点a和结点b是邻接的.无向边、端点——若图中的边e所对应的结点偶对是无序的,记为(a,b),则称e是无向边(简称棱).a,b称为e的端点.称e是关联于结点a和b的,结点a和结点b是相、邻的,或称结点a和结点b是邻接的.有向图——每一条边均为有向边的图称为有向图.无向图——每一条边均为无向边的图称为无向图.底图——如果把有向图中每条有向边都看作无向边,就得一个无向图,此无向图称为原有向图的底图.底图只表示出结点间的连接关系而没有表示出连接边的方向.弧立结点——图中不与任何相邻的结点称为弧立结点.零图——全由孤立结点构成的图称为零图.自回路(环)——关联于同一结点的一条边称为自回路或环.重边(平行边)——在有向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为重边或平行边.多重图——含有重边的图称为多重图.线图——非多重图称为线图.定义3.1.2(简单图)无自回路的线图称为简单图.定义3.1.3(结点的度数、最大度、最小度)图G=<V,E>中,与V中结点v(v∈V)相关联的边数,称为该结点的度数,记作为deg(v).记∆(G)= max{deg(v)| v∈V(G)},δ(G)= min{deg(v)| v∈V(G)},分别称为G=<V,E>的最大度和最小度.定义3.1.4(出度、入度、度数)在有向图中,对于任何结点v,以v为始点的边的条数称为结点v的引出次数(或出度);以v为终点的边的条数称为结点v的引入次数(或入度);结点v的引出次数和引入次数之和称为v的次数(或度数).定义3.1.5(二部图)设G=〈V,E>是n阶无向图,若能将V分成两个互不相交的子集V1与V2使得G中任一边的两端点都不在同一个V i(i=1,2)中,则称G为二部图.记G=<V1,V2,E>.定义3.1.6(完全图)简单图G=<V,E>中,若每一对结点间都有边相连,则称该图为完全图.有n个结点的无向完全图记为K n.定义3.1.7(k-正则图)若无向简单图中,每个结点的度均为某个固定整数k,则称该图为k-正则图.定义3.1.8(赋权图)赋权图G是一个三重组<V,E,g>或四重组<V,E,f,g>,其中V是结点集合,E是边的集合,f是定义在V上的函数,g是定义在E上的函数.定义3.1.9(补图)设图G=<V,E>有n个顶点,图H=<V,E’>也有同样的顶点,而E’是由n个结点的完全图的边删去E所得,则图H称为图G的补图,记为H=G,显然,G=H.定义3.1.10(子图、真子图、生成子图)设G=<V,E>和G’=<V’,E’>是两个图.(1)若V’⊆V且E’⊆E,则称G’是G的子图;(2)若V’⊂V或E’⊂E,则称G’是G的真子图;(3)若V’=V和E’⊆E,则称G’是G的生成子图;(4)若子图G’中没有孤立结点,G’由E’唯一确定,则称G’为由边集E’导出的子图;(5)若子图G’中,对V’中的任意两个结点u,v,当u,v∈V’时有[u,v]∈E’,则G’由V’唯一确定,则称G’为由结点集V’导出的子图.定义3.1.11(补图) 设G’=<V’,E’>是G=<V,E>的子图,若给定另外一个图G’’=<V’’,E’’>,使得E’’=E-E’,且V’’中仅包含E’’的边所关联的结点,则称G’’是子图G’的相对于G 的补图.定义3.1.12(同构) 设G=〈V,E>和G’=<V’,E’>是两个图,若存在从V到V’的双射函数f,使对任意[a,b]∈E,当且仅当[f(a),f (b)]∈E’,并且[a,b]和[f(a),f (b)]有相同的重数,则称G和G’是同构的.定义3.1.13(路径) 在图G=<V,E>中,设v0,v1,…,v n∈V,e1,e2,….,e n∈E,其中e i是关联于结点v i-1,v i的边,交替序列v0 e1 v1 e2…e n v n称为联结v0到v n的路径(或称路).v0与v n分别称为路的起点与终点,边的数目n称为路的长度.孤立点——长度为0的路定义为孤立点.简单路径——若序列中所有的边e1,e2,…., e n均互不相同,则称此路径为简单路径.基本路径——若序列中所有的点v0,v1,…,v n均互不相同,则称此路径是基本路径.回路——若v0=v n,即路径中的终点与始点相重合,则称此路径为回路.简单回路——没有相同边的回路称为简单回路.基本回路(圈)——各结点均互不相同的回路称为基本回路(或圈).奇圈(偶圈)——长度为奇(偶)数的圈称为奇(偶)圈.定义3.2.1(可达、连通)在图G=<V,E>中,设有结点v j与v k,若从v j到v k存在任何一条路径,则称结点v k从结点v j可达,也称结点v j与v k是连通的.定义3.2.2(连通图、非连通图、分离图)若G是平凡图或G中任意两个结点都是连通的,则称G是连通图,否则称G为非连通图或分离图.定义3.2.3(连通分支)设G=<V,E>是图,连通关系的商集为{V1,V2,…,V m},则其导出的子图G(V i)(i=1,2,…m)称为图G的连通分支(图),将图G的连通分支数记作W(G).定义3.2.4(短程线)设u与v是图G的两个结点,若u与v连通,则称u与v之间的长度最短的路为u与v之间的短程线,短程线的长度可作为结点u与v间的距离,记作d(u,v),其满足下列性质:d(u,v) ≥ 0,u=v时,d(u,v) =0 (非负性)d(u,v) = d(v,u) (对称性)d(u,v) + d(v,w) ≥d(u,w) (三角不等式)若u与v不连通,则通常记d(u,v) = ∞.定义3.2.5(单向连通、强连通、弱连通)在简单有向图中,如果在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向(侧)连通的;如果在任何结点偶对中,两结点对互相可达,则称图G是强连通的;如果图的底图(在图G中略去边的方向,得到无向图)是连通的,则称图G是弱连通的.定义3.2.6(极大强连通子图、极大单向连通子图、极大弱连通子图、强分图、单向分图、弱分图) 在简单有向图G =<V ,E >中,G’是G 的子图,如G’是强连通的(单向连通的,弱连通的),且没有包含G’的更大的子图G’’是强连通的(单向连通的,弱连通的),则称G’是极大强连通子图(极大单向连通子图,极大弱连通子图)又叫强分图(单向分图,弱分图).定义3.2.7(点割集、割点) 设无向图G =<V ,E >为连通图,若有点集V 1⊂V ,使图G 删除了V 1的所有结点后,所得的子图是不连通图,而删除了V 1的任何真子集后,所得的子图是连通图,则称V 1是G 的一个点割集.若某个结点构成一个点割集,则称该结点为割点.定义3.2.8(点连通度) 若G 为无向连通图且不含Kn 为生成子图,则称k (G )=min{|V 1| ∣V 1是G 的一个点割集}为G 的点连通度(简称连通度).规定:完全图Kn 的点连通度为n ,n ≥1.非连通图的点连通度为0.若k (G ) ≥k ,则称G 为k -连通图.定义3.2.9(边割集、割边、桥) 设无向图G =<V ,E >为连通图,若有边集E 1⊂E ,使图G 删除了E 1的所有边后,所得的子图是不连通图,而删除了E 1的任何真子集后,所得的子图是连通图,则称E 1是G 的一个边割集.若某个边构成一个边割集,则称该结点为割边(或桥). 定义3.2.10(连通度) 若G 为无向连通图,则称λ(G )=min{|E 1| ∣E 1是G 的一个边割集}为G 的边连通度.规定:非连通图的边连通度为0.若λ(G ) ≥k ,则称G 为k 边-连通图.定义3.3.1(邻接矩阵) 设G =<V ,E >是一个简单图,其中V ={v 1,v 2,…, v n },则n 阶方阵A (G )=(a ij )称为G 的邻接矩阵.其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 定义3.3.2(可达性矩阵) 设G =<V ,E >是一个简单图,|V |=n ,假定G 的结点已编序,即V ={v 1,v 2,…, v n },定义一个n ⨯n 方阵P =(p ij ).其中⎪⎩⎪⎨⎧=不存在一条路与从至少存在一条路到从j i j i ij v v v v p 01 则称矩阵P 为图G 的可达性矩阵.最短路径的数学模型——给定一个网络N (有向或无向赋权图),u 0与v 0是N 中指点的两个顶点,在N 中找一条从u 0到v 0且权最小的路.规定N 中的一条路P 的权w (P )称为p 的长度.若N 中存在从u 到v 的路,则将N 中从u 到v 且权最小的路称为u 到v 的最短路,其长度称为u 到v 的距离,记为d N (u ,v ).二、定理定理3.1.1(握手定理) 设G 是一个图,其结点集合为V ,边集合为E ,则∑∈=V v E v ||2)deg(定理3.1.2 图中次数为奇数的结点有偶数个.定理3.1.3 在任何有向图中,所有的入度之和等于所有结点的出度之和.定理3.1.4 有n 个结点的无向完全图K n 的边数为n (n -1)/2.定理3.1.5 在具有n 个结点的简单图G =<V , E >中,若从结点v j 到结点v k 有一条路,则从结点v j 到结点v k 有一条长度不大于n -1的路.定理3.1.5推论在一个具有n个结点的图G=<V, E>中,如果从结点v j到结点v k有一条路,则从结点v j到结点v k必有一条长度小于n的通路.定理3.1.6在具有n个结点的图G=<V,E>中,如果经v有一条回路,则经v有一条长度不超过n的回路.定理3.1.6推论在具有n个结点的图G=<V,E>中,如果经v有一条简单回路,则经v 有一条长度不超过n的基本回路.定理3.2.1一个有向图是强连通的,当且仅当G中有一个回路,其至少包含每个结点一次.定理3.2.2在有向图G=〈V,E〉中,G的每一结点都在也只在一个强(弱)分图中.定理3.2.3在有向图G=〈V,E〉中,G的每一结点都处在一个或一个以上的单向分图中.定理3.2.4(Whitney)对于任何一个图G,有k(G) ≤λ (G) ≤δ(G)其中k(G)、λ (G)、δ(G)分别为G的点连通度、边连通度和最小度.定理3.2.5一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u与w,使得结点u与w的每一条路都通过v.三、方法1.两图同构的必要条件:(1)结点数相等;(2)边数相等;(3)度数相同的结点数相等.2.邻接矩阵运算特征(1)图G=<V,E>的邻接矩阵不唯一,而与V中的元素标定次序有关.对V中各元素不同的标定次序可得到同一图G的不同邻接矩阵.但这些邻接矩阵经过适当地交换行和列的次序,就从一个邻接矩阵变到另一个邻接矩阵.根据不同邻接矩阵所作的有向图都是同构的.因此,可选V元素的任一种标定次序所得出的邻接矩阵.(2)当有向线图代表关系时,邻接矩阵就可看作是一种关系矩阵.有向图是自反的,矩阵的对角线元素全为1.有向图是非自反的,矩阵的对角线元素全为0.有向图是对称的,对所有i和j,矩阵是对称的.有向图是反对称的,对所有i和j,矩阵是以主对角线对称的元素不可能同时为1.(3)零图的邻接矩阵的元素全为零,并称其为零矩阵.(4)图的每一顶点都有自回路而再无其它边时,图的邻接矩阵是单位矩阵.(5)设有向线图G=<V,E>的邻接矩阵是A,则A的逆图的邻接矩阵是A的转置矩阵.3.可达性矩阵的计算方法一般地,可以由图G的邻接矩阵A得到可达性矩阵P.即令B n=A+A2+…+A n,在从B n中将不为0的元素改为1,而为零的元素不变,这样改换的矩阵即为可达性矩阵P.也可以将矩阵A,A2,…,A n分别改为布尔矩阵A,A(2),…,A(n),简化计算,故P= A∨A(2)∨…∨A(n),其中A(i)表示在布尔运算下A的i次方.4.求最短路径的Dijkstra算法步骤(1)置l(u0)=0,对v∈V-{ u0},l(v)= +∞,S0 ={ u0},i=0.(2)对每个v∈ N G-Si(u i),用min{ l(v),l(u i)+ w(u i,v)}代替l(v).若l(v)取到l(u i)+w(u i,v),则在v旁边记下(u i).计算min(v∈G- S i ){ l(v)},并将达到最小值的这个顶点记为u i+1.置S i+1= S i⋃{ u i+1}.(3)若i=|G|-1,则算法停止,否则用置i 为i+1,并转入第(2)步.算法结束时,从u0到v的距离由最终的标号给出l(v),并且可根据各个顶点旁边的(u i)追回出从u0到v的最短路径.若为求某个特定的顶点v时,则可以在u j= v时使算法停止即求得结果.。