当前位置：文档之家 › 平面图、对偶图和色数的应用探究-大学论文

平面图、对偶图和色数的应用探究-大学论文

  • 格式：doc
  • 大小：1.99 MB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

几何图形数学论文2400字_几何图形数学毕业论文范文模板

几何图形数学论文2400字_几何图形数学毕业论文范文模板

几何图形数学论文2400字_几何图形数学毕业论文范文模板几何图形数学论文2400字(一)：探索初中数学几何图形教学的有效途径论文摘要：数学是学习生涯中一门非常重要的学科，它陪伴广大学子一直从幼儿园到就业，我们生活中的点点滴滴都有数学相伴。

所以学好数学是每一个学生都应该为之努力的事，教好数学也是每一位数学教师的重任。

几何图形在数学中占有不可替代的重要地位，对于一些逻辑思维相对较差的学生来说，不免是一个坎，本文主要围绕初中数学中的几何数学进行论述，简要分析一些几何图形教学的有效途径。

關键词：初中数学；几何图形；教学；有效途径教育事业一直是我国非常重视的一大领域，我国的课程标准也一直不断的在更新完善中，国家以及教育工作者们也一直都在为教育事业的不断发展而不断努力着。

数学作为一门逻辑性非常强的学科，曾一度难倒了各个学习阶段的广大学子，因其具有浓厚的逻辑思维性和观察分析性，所以要求学生要具有良好的逻辑思维能力和观察力。

几何图形的学习主要包括概念、作图和推理三部分，其本身比较枯燥乏味，对于思维敏捷的学生来说学习这部分内容是非常轻松的，但对于一部分学生来说根本就是一个难以跨越的鸿沟。

其实，在教学过程中除了需要学生努力学习，教师的教学方法也是至关重要的一部分。

一、现如今几何教学方法存在的问题我们大家都应该清楚我国很多教师在教学模式中采用的仍是灌输式的教学，教师仅仅通过口述教材中的定义、概念等，让学生单方面的“囫囵吞枣”式的记住所学的知识。

概念、定义等都知识片面的概述，仅仅记住其表面的意思是远远不够的，因为只是记住这些知识学生在遇到问题时并不能自主的将其延伸到问题中，也没有将这些概念应用到问题中的意识。

教师并不仅仅是知识的“搬运工”，也应该是学生学习的引导者、领航者。

几何问题内容抽象，对于空间想象能力稍差的学生来说，其想象力和逻辑思维很容易受到限制，在遇到证明题时根本无从下手。

如果教师在教学过程中没能有效的引导和锻炼其逻辑思维能力，将出现学生不能正确的将知识运用其中和逻辑思维不能灵活转换等问题，部分学生甚至出现缺乏自信，自暴自弃等恶心循环的状态。

离散数学PPT课件10着色与对偶图(ppt文档)

离散数学PPT课件10着色与对偶图(ppt文档)






不同颜色.
四. 图G的正常着色(简称着色):
1. 对G的每个结点指定一种颜色,使得相邻接的两个结点
着不同颜色. 如果G着色用了n种颜色,称G是 n-色的.
2.对G着色时,需要的最少颜色数,称为G的着色数,记作
x(G) .
3.对G着色方法:(下面介绍韦尔奇.鲍威尔法)
3.对G着色方法:(介绍韦尔奇.鲍威尔法 Welch.Powell) ⑴将G中的结点按照度数递减次序排序,(此排序可能不唯 一,因为可能有些结点的度数相同) ⑵用第一种颜色对第一个结点着色,并按照排序,对与前面 着色点不邻接的每一个点着上相同颜色. ⑶用另一种颜色对尚未着色的点, 重复执行⑵和⑶,直到
⑶当且仅当ek只是一个面Fi的边界时, vi*上有一个环ek* 与ek相交.
v3*
则称图G*是G的对偶图.
v5
F1 v1*
F3
可见G*中的结点数等于
F2 v2*
G中的面数.
二. 自对偶图:如果图G对偶图G*与G同构,则称G是自对偶
图. (如下图) 三.对偶图与平面图着色的关系:

对平面图面相邻面用不同颜 色的着色问题,可以归结到对 其对偶图的相邻接的结点着
有共同的学生在读, 就在两门课程之间连一直线.得到图:
结点度数递减排序:
A
B,C,D,G,A,E,F 对图正常着色后, 标有同一种颜色的 G
课,可以同时考试.安排考试日程: 周一: A 周二: B,F 周三:C,E 周四: D,G
F E
作业 P189 – 8.16 8.17
B C
D
所有结点都着上颜色为止.
B C
例如:结点排序:A,B,E,F,H,D,G,C A

图论5-8章-习题课

图论5-8章-习题课
6. 设 G 是连通的平面图，证明：G 为二部图当且仅当 G 的对偶图为欧 拉图。
证明：设 G 的对偶为 G*，则 G* 是连通的。必要性： G 为二部图，则 G 中无奇数长度回路，故 G* 中无奇数度顶点，因此 G* 是一个欧拉 图。充分性：G* 是一个欧拉图，则 G* 中无奇数度顶点，故 G 中 无奇数长度回路，因此 G 为一个二部图。
第二十八页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
14. 匈牙利算法求二部图的可增广道：如图，设初始匹配 {(x2, y2), (x3, y3), (x5, y5)}，求其最大匹配。
x1
x2
x3
x4
x5
y1
y2
y3
y4
y5
28
第二十九页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
12
第十三页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
7. 证明：k 色图 G 中至少有 k(k1)/2 条边。
13
第十四页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
7. 证明：k 色图G中至少有 k(k1)/2 条边。 证明：按 G 的一个 k 正常着色方案划分 G 的顶点为 k 个集合 V1,
第四页，编辑于星期六：八点 分。
《图论》4-8 章 习题课
2. 证明：Perterson 图不是平面图。
证二：反证。设其为平面图。由图示，每个面至少有5条边，即 l=5，代 入：
m (n 2)l l2
得： 3m 5(n2) 将 n =10, m =15 代入得 45 40，矛盾。
4
第五页，编辑于星期六：八点 分。
v1
v2

图论第6章-平面图

图论第6章-平面图
n–m+r=( n′+1)–(m′ +1)+r′= n′-m′ +r′ =2。
若G不是树，则G中含有回路。设边e在G的 某个回路上。令G′=G-e(从G中删除边e，而得 到G′)，则G′仍然是连通图。设n′，m′和r′分别是 的结点数、边数和面数。则n′=n，m′=m-1=k， r′=r–1 。 于 是 n=n′ ， m=m′+1 ， r=r′+1 。 因 为 G′ 是连通图且m′=k，所以G′满足归纳假设的条件。 由归纳假设知：n′–m′＋r′=2，所以 n–m+r= n′–(m′+1)+(r′+1)= n′-m′+r′=2。
v1
v4
R0 R2 R1 v2
v3 v5
v6
又例：下图为非连通的平面图，有两个连
通分支， deg(R1)=3， deg(R2)=4， R0的 边界由两个初级回路v1 v2 v3v1 和v4 v5 v6 v7 v4围成， deg(R0)=7 。
v1
v4
v7
v2
R1 v3R0 v5
R2
v6
定理：设G=V,E是有限平面图，有r个面，
如下图G1,G2,G3是同胚的。
G1
G2
G3
定理 (库拉斯基定理) 一个图G是非平面的，当 且仅当它包含一个同胚于K3.3或K5的子图。
例 说明彼得森图不是平面图。
解:删去下图(a)皮得森图的结点b,得其子图
(b)H。a 而H胚于Kf 3,3,所以皮c 得森不是平f面图。d
j
f ejg baFra bibliotekd g
6
36
4
54 12
7
8

图论图着色

图论图着色
源自v2v1v0
v4
v5
(b)去掉v0后结点v1与v3处在 同一个连通分支中,v1 与v3有一通路，其中点的颜色红黄交替出现，它与 v0构成一回路C(同一个连通分支)，也就是约当曲线， 这时结点v2处在曲线的内部而结点v5则处在线的外 部，v2与v5的任何连线必与曲线C相交，与平面图的 条件矛盾。因此约当曲线C必然将黑白集中的结点分 成两个连通分支，使v2与v5分别处于两个连通分支中 （也就是v2与v5不连通）， v 于是问题回到(a)，可将v2 v v (或v5)所在的分支中的黑 v 白色对换，于是与v0邻接 v v 的5个结点也只着了4种颜 色， v0就可着第5种颜色。
独立集特点 (1)图G的每一个结点构成一个独立集。 (2)极大独立集不是唯一的，它的基数不一定 是最大的，但它的元素数目已达到极限， 即不可能再加入其他结点而不破坏它的独 立性。 (3)最大独立集必然也是极大独立集而且元素 数目是最多的。 (4)任一完全图Kn的独立数I(Kn)＝1 (5)偶图G只有两个极大独立集，即是它的两 个互补结点子集V1和V2
v1 e1 c1 e3 c3 v3 v0 e2 c2 v2
定理6.4 若G是偶图，则 ψ e (G ) = Δ (最大结点次数) 证：设G的两个互补结点子集为Vl和V2，若|V1|<|V2|，则 在V1中增加一些结点成为V1’使|V1’|=|V2|， 对xi∈V1’及yj∈V2，若G中无边(xi，yj)，则增加一条 边(xi,yj)，通过以上的增添，图G=(V，E)成为图GΔ＝ (V’，E1’)， GΔ 是 Δ次正则偶图，（ 由定理5.4的推论可知）它 有一完美匹配M1，令E2’＝E1’一M1，得到图 G Δ-1＝ (V’，E2’)，则 G Δ-1是(Δ一1)次正则偶图，它也有一 完美匹配M2， 如此继续下去可以得到M1，M2,..., MΔ 个完美匹 配，每一个完美匹配可着一种颜色，使得到G的边 着 色，即 ψ e (G ) = Δ

几何图论论文

几何图论论文

几何图论论文一、引言几何图论作为图论的分支之一，研究的是在几何空间中的图形及其间的关系。

它涉及到的问题有很多，例如平面图的着色、最小生成树的构建、欧拉回路的存在性等。

本文将介绍几何图论的基本概念与方法，并探讨其中的一些经典问题。

二、基本概念1. 平面图在定义平面图之前，我们先介绍一些基本概念。

概念1：一个平面图由若干顶点和连接这些顶点的边所组成，其中每条边都是两个端点的非交叉直线段。

平面图可以用图的形式表示，其中顶点代表图中的顶点，边代表连接这些顶点的边。

概念2：一个平面图称为简单的，如果它的边不会相交，即任意两条边之间最多只有一个顶点。

概念3：如果一个平面图可以被画在平面上，使得任意两条边之间最多只有一个交点，那么这个平面图是一个平面图。

2. 最小生成树最小生成树是指在一个连通图中生成一棵包含所有顶点的树，并使得该树的边权重之和最小。

最小生成树常用于解决网络设计、电力传输等问题。

算法：普里姆算法步骤： - 选择任意一个顶点作为起点 - 从剩余的顶点中选择与当前树相邻的边权重最小的顶点，并将其加入到树中 - 重复上一步，直到树中包含所有顶点3. 欧拉回路欧拉回路是指一个图中经过每条边一次且只经过一次的回路。

欧拉回路的存在性问题是欧拉图论中的经典问题之一。

定理1：对于连通的欧拉图，存在欧拉回路的充分必要条件是所有顶点的度数都是偶数。

三、经典问题1. 平面图的着色平面图的着色问题是指给定一个平面图，将图中的每个顶点染上一种颜色，要求相邻的顶点不能染成相同的颜色。

算法：染色算法步骤： - 选择任意一个顶点，并给其染上颜色1 - 从剩余的顶点中选择一个未染色的顶点，并给其染上一种相邻顶点未使用的颜色 - 重复上一步，直到所有顶点都被染色2. 最近点对最近点对问题是指在平面上给定n个点的坐标，要求找出其中距离最近的两个点。

算法：分治法步骤： - 将所有点按照X坐标排序 - 将排序后的点集分成两半，分别求左半部分和右半部分内的最近点对 - 比较左右两部分内的最近点对，选择最近的一对作为最终结果四、结论几何图论是图论的重要分支，它研究的是在几何空间中的图形及其间的关系。

图论课件特殊平面图与平面图的对偶


嵌入法
首先将原始图嵌入到平面 上，然后根据嵌入的图构 造对偶图。
Hale Waihona Puke 递归构造法通过对原始图的递归分割， 构造出对偶图。
04
特殊平面图与平面图的对 偶关系
欧拉图与对偶图的关系
欧拉图
一个连通图，其每一条边都恰好在一个欧拉路径 上。
对偶图
将原图的每条边替换为其对偶边，即反转边的方 向。
关系
如果一个图是欧拉图，那么其在对偶图中也是欧 拉图。
在其他领域的应用
生物信息学
在生物信息学中，特殊平面图和平面图的对偶可以用于描述基因组序列和蛋白质 相互作用网络。
电子工程
在电子工程中，特殊平面图和平面图的对偶可以用于描述电路设计和信号处理。
THANKS
感谢观看
经过原图每条边至少一次的回路。
表现
在对偶图中，欧拉路径和哈密顿路径的方向也会发生反转。
05
特殊平面图和平面图对偶 的应用
在计算机科学中的应用
1 2
路由算法
在计算机网络中，对偶图可以用于描述数据包的 传输路径，通过对偶图的计算可以找到最优路径。
计算机图形学
在计算机图形学中，特殊平面图和平面图的对偶 可以用于描述图形的渲染和光照计算。
02
特殊平面图
欧拉图
定义
一个连通图，它的边可以按照某 种顺序排列，使得每条边恰好被 走过一次，则称这个图为欧拉图 。
判定条件
一个连通图是欧拉图当且仅当存 在一个顶点，从它出发的边数等 于它与其它顶点的度数之和。
哈密顿图
定义
一个连通图，它的顶点可以由一个顶点开始遍历一次（包括 起点），且只遍历一次所有顶点，则称这个图为哈密顿图。
哈密顿图与对偶图的关系

任何平面图都是4-面可着色的

任何平面图都是4-面可着色的（蒋友皎广西玉林市537000）0引言任何一个连通平面图都是五色图。

但是后来在平面图上经过多次试验，没有找到一种平面图一定要用5种颜色的。

在一百多年前，有人猜测只要用4种颜色就够了，这就是世界上著名的4色猜测问题。

这个猜测一经提出，迷住了许多数学家，但是谁都无法用数学的方法证明它。

直到1976年，Appel和Haken两人宣布了四色理论的证明方法。

他们用大型电子计算机分析了2000多种图包括几百万种情况，花了大量的机器时间，终于证明了这个问题，从而解决了一百多年来引人关注的难题[1]。

Since the proving of the theorem, efficient algorithms have been found for 4-coloring maps requiring only O(n2) time, where n is the number of vertices. In 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas created a quadratic time algorithm, improving on a quartic algorithm based on Appel and Haken’s proof[2] [3] [11]. This new proof is similar to Appel and Haken's but more efficient because it reduced the complexity of the problem and required checking only 633 reducible configurations. Both the unavoidability and reducibility parts of this new proof must be executed by computer and are impractical to check by hand[4] [11]. In 2001 the same authors announced an alternative proof, by proving the snark theorem[5] [11].In 2005 Benjamin Werner and Georges Gonthier formalized a proof of the theorem inside the Coq proof assistant. This removed the need to trust the various computer programs used to verify particular cases; it is only necessary to trust the Coq kernel[6] [11].显然这不是纯理论上的严格证明，在计算机的辅助工作下四色定理的证明完成了，但是是否存在不需要借助计算机的纯数学方法的证明呢？本文将运用纯数学方法的证明任何平面图都是4-面可着色的。

离散数学第四篇7图 5-6平面图及图的着色


7-6-2 图中顶点的着色
7-6-3 地图的着色与平面图的点着色 7-6-4 边着色 本章小结 习 题
4
7-5-1 平面图的基本概念
一、关于平面图的一些基本概念 1、 平面图的定义 定义7-5-1 G可嵌入曲面S——如果图G能以这样的方式画在曲面S上 ，即除顶点处外无边相交。 G是可平面图或平面图——若G可嵌入平面。
证明
设G的连通分支分别为G1、G2、…、Gk，并设Gi的顶点数、 边数、面数分别为ni、mi、ri、i=1，2，…，k。
由欧拉公式可知: ni-mi+ri = 2，i=1，2，…，k 易知， m mi，n ni
i 1 i 1 k k
(7-5-1)
由于每个Gi 有一个外部面，而G只有一个外部面，所以G的面数 k r ri k 1
(3)设m＝k(k≥1)时成立，当m＝k+1时，对G进行如下讨论。 若G是树，则G是非平凡的，因而G中至少有两片树叶。 设v为树叶，令G'=G-v，则G'仍然是连通图，且G'的边数 m'=m-1=k，n'=n-1，r'=r。 由假设可知 n'-m'+r'=2，式中n'，m'，r'分别为G'的顶点数， 边数和面数。 于是n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2 若G不是树，则G中含圈。
R1
R0 R2
R3
平面图有4个面，deg(R1)=1,9deg(R2)=3, deg(R3)=2, deg(R0)=8。
定理7-6-1 平面图G中所有面的次数之和等于边数m的两倍，即

图论中的图的平面性质及其应用

图论中的图的平面性质及其应用图论是一门研究图与其性质的学科，它在计算机科学、数学、物理学等领域均有广泛应用。

而其中一项重要的研究就是图的平面性质。

所谓图的平面性质，指的是一个图是否能够被画在平面上而不发生任何两条边相交的情况。

如果一个图的平面性质成立，那么我们就称其为平面图。

平面图是一种特殊的图，它没有任何交叉的边，这使得它在实际应用中具备了很多方便的特性。

那么如何判断一个图是否为平面图呢？其中一个著名的方法就是埃及学家的“三颗岛屿”问题（Königsberg问题）。

在这个问题中，我们需要判断一个城市中的四个陆地区域和两条河流是否能够被一条路径顺次地穿过。

经过一定的推理和证明，发现这个问题的关键在于它所对应的图是否为平面图。

目前，已经有很多算法和理论可以用来判断一个图是否为平面图。

其中最常用的是Kuratowski定理，它指出一个图是平面图，当且仅当它不含有K5和K3,3两种子图。

通过这个定理，我们可以较为简单地判断一个图是否为平面图。

除了判断一个图是否为平面图，平面图在实际应用中还有很多特殊的应用。

其中最广泛的莫过于地图着色问题。

在地图着色问题中，我们需要为每一个国家或地区分配一种独立的颜色，使得相邻的国家或地区颜色不同。

如果我们将每一个国家或地区看作图的节点，国界看作图的边，那么这个问题就可以被简化为对一个平面图进行着色。

为了解决地图着色问题，我们需要考虑到平面图的特殊性质。

其中最重要的就是欧拉公式。

欧拉公式给出了平面图中节点数、边数和面数之间的关系式：V-E+F=2。

其中V表示节点数，E表示边数，F表示面数。

这个公式可以帮助我们解决一些与平面图相关的问题。

在地图着色问题中，我们可以使用带权区间图的贪心算法进行求解。

首先，我们可以将每一个国家或地区看作是一个节点，然后按照欧拉公式计算出平面图的面数F。

然后，我们可以将所有边按照长度排序，然后从前往后依次添加边，如果两个节点之间的边跨越了一个已经着色的区域，那么我们就需要给这个新的区域分配一个新的颜色。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

i 目 录 1引言 ............................................................................................................................................ 1 2相关概念和定理 ................................................................................................................. 1

2.1 图的相关概念 ........................................................................................................................ 1 2.2 平面图的相关概念和定理 .................................................................................................... 2 2.3 对偶图的相关概念 ................................................................................................................ 5 2.4 色数的相关概念和定理 ........................................................................................................ 6 2.4.1 图中顶点的着色 ................................................................................................................. 6 2.4.2 边着色 ................................................................................................................................. 6 2.4.3 面着色 ................................................................................................................................. 7 3平面图、对偶图和色数的应用 ................................................................................. 7 3.1 平面图理论的应用 ................................................................................................................ 7 3.2 对偶图理论的应用 ................................................................................................................ 9 3.3 色数理论的应用 .................................................................................................................. 10 3.3.1 运用图论知识解决高中数学染色问题 ........................................................................... 10 3.3.2 染色理论在教务工作中的两个应用 ............................................................................... 12 4结束语..................................................................................................................................... 15

参考文献 ................................................................................................................................... 16 致谢 .............................................................................................................................................. 17 ii

平面图、对偶图和色数的应用探究 xxx本xxx班 xxx

指导老师 xxx

摘 要：平面图、对偶图和色数理论不仅是图论中的重要内容,而且在实际生活中应用广泛。本文首先阐述了平面图、对偶图和色数的相关概念和定理，然后分别探究了其实际应用。其中，景区空调管道的设计和3间房子3种设施问题是典型的平面图模型，电力电子器件的对偶变换是对偶图理论的应用，高中数学染色问题的图论解法和教务工作中期末考试安排和排课表问题是平面图的色数理论的应用。 关键词：平面图，对偶图，色数，应用探究。

The application of planar graph, dual graphs and chromatic number Xxxxxxxxxxxxxxx Class xxxx, Mathematics Department Tutor: xxxxxxxx

Abstract: plan, dual graphs and chromatic number theory is not only the important content in graph theory, and extensive application in real life. This paper firstly explains the related concept plan, dual graphs and chromatic number and theorem, and then explores its practical application. Among them,the scenic design of air conditioning pipeline and 3 houses 3 facilities is a plane graph model, dual transformation of power electronic devices is the application ofthe dual graph coloring problem, high school mathematics graph theory method and the final exam schedule administration work and the timetable problem is the application of chromatic number of planar graphs of theory. Key words: plan, dual graph, chromatic number, application research. １

1引言 图论起源于著名的哥尼斯堡七桥问题，欧拉在1736年解决了这个问题，并于1753年发现了欧拉公式而成为拓扑图论的奠基人。接着中断了170多年。1930年，当波兰数学家C.Kuratowski和美国数学家O.Frink & P.A.Smith发现了平面图判定准则后，这方面的研究才开始复苏。20世纪70年代，我国著名数学家吴文俊教授和刘彦佩教授创立了平面性判定的“吴-刘”方法得到了国际数学界的认可。如今，平面问题的研究成果已经在交通网络和印刷线路的设计等方面得到应用。世界上著名的“四色猜想”曾困扰了数学家们将近100年，期间人们进行了各种尝试，平面图的对偶图也曾用于解决著名的四色猜想问题，但都以失败告终，最后数学家凯尼斯.阿佩尔和沃夫冈.哈肯借助计算机得以解决。平面图的染色问题是与四色问题紧密相联的。于是产生了着色问题即给定一个图，如果要求把所有顶点涂上颜色，使得相邻顶点具有不同的颜色，问最少需要几种不同的颜色？这个问题叫做图的点着色问题。如果对给定图的全部边都涂上颜色，使相邻的边有不同的颜色，问至少需要几种颜色？这个问题叫做边的着色问题，边的着色问题可以转化为点着色问题。由于生产管理、军事、交通运输等方面提出大量实际问题的需要，图的染色理论及其应用研究得到飞速发展。 2相关概念和定理 2.1图的相关概念 定义1 一个图是一个三元组GGEGV),(),(, 其中nvvvGV,,,21为有

限非空结点集合, iv称为结点, meeGE,,1为有限的边集合, ie称为边, G

是从边集合E到结点对集合上的函数. 图可简记为:EVG,. 定义2 如果E中边ie对应V中的结点对是无序的vu,, 称ie是无向边, 记vuei,, 称u,v是ie的两个端点. 如果ie与结点有序对vu,相对应, 称ie是有

向边, 记vuei,, 称u为ie的始点, v为ie的终点. 定义3 每条边均为无向边的图称为无向图. 每条边均为有向边的图称为有向图. 有些边是无向边, 有些边是有向边的图称为混合图. 定义4 设EVG,, EVG,为两个图(同时为无向图或有向图), 若