两种实用地图着色算法的比较与实现
摘要：地图着色算法的研究是为了是把相邻的区域用尽可能少的颜色区分开。四色猜想是从理论上指出地图着色所需最小着色数，但考虑到实际应用中速度因素，只需采用尽可能优化的地图着色方案，本文中对两种实用算法进行了比较和实现。
关键字：四色猜想；地图着色；DFS
引言
“四色猜想”虽然至今尚未得到一个严格的数学证明，但人们似乎已经默认这一著名猜想是对的，即任意一个平图都可以用至多四种不同的颜色对其平面区域进行正常着色。地图着色的应用研究是为了是把相邻的区域用尽可能少的颜色区分开，而不是针对“四色猜想”的问题本身[1]。地图着色实际应用中速度指标和颜色数目指标同样重要，目标是在可容忍时间消耗的基础上采用尽可能少的颜色进行着色[2]。
着色算法
对于平面图的着色问题的研究一直成为研究热点，特别是随着计算机的出现和广泛应用，图的着色理论也有了迅速的发展，其应用日益广泛[3][4]。现在已经成为研究系统工程、管理工程、计算机可续、通讯、网络理论、运筹学等所必须的一种手段[5][6]。，本文从实际应用角度列举的两种算法都是实现基于四色猜想的着色优化，但并不一定是最佳的着色算法。
算法1：根据图G的邻接矩阵，依次按节点序号遍历所有节点，进行着色。先用一种颜色对节点着色，判断矩阵中与该节点相邻的节点的颜色是否相同，如果不同，则继续对其他节点遍历。如果相同，则改用其他颜色尝试，直至与相邻点颜色不同。
算法中核心的颜色赋值和碰撞检测处理步骤如下：
For (依次遍历图的所有节点i)
{For (依次判断的最大颜色数目,颜色j)
{给节点i赋值颜色j；
For (序号k小于该节点序号i的节点)
课程设计 地图着色 课程设计名称：课程设计 专业班级： 学生姓名： 学号： 指导教师： 课程设计时间：
计算机专业课程设计任务书 学生姓名专业班级学号题目地图着色 课题性质课题来源 指导教师同组姓名 主要内容学习掌握并熟练运用C语言进行程序设计； 针对具体应用问题，选择、设计和实现合适的抽象数据类型；进行简单的需求分析，给出设计方案。 任务要求综合运用和融化所学理论知识，提高分析和解决实际问题的能力，达到培养良好程序设计能力和习惯的目的，为开发满足问题要求的小型应用软件奠定基础，达到软件工程的综合性基础训练的目的。 完成需求分析报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。 参考文献《数据结构（C语言版）》严蔚敏清华大学出版社《C语言程序设计》（第三版）谭浩强清华大学出版社
指导教师签字： 审查意见 教研室主任签字： 2014年6月15 日
目录 1 需求分析 (4) 2 概要设计 (4) 3详细设计 (5) 4 运行环境 (6) 5开发环境 (6) 6 程序设计.............................................................................................6~9 7 调试分析........................................................................................9~10 8 测试结果 (10) 9参考文献 (11) 10心得体会 (11) 11成绩评价表 (12)
高斯-克吕格（Gauss-Kruger）投影，是一种“等角横切圆柱投影”。德国数学家、物理学家、天文学家高斯（Carl Friedrich Ｇauss，1777一 1855）于十九世纪二十年代拟定，后经德国大地测量学家克吕格（Johannes Kruger，1857～1928）于 1912年对投影公式加以补充，故名。设想用一个圆柱横切于球面上投影带的中央经线，按照投影带中央经线投影为直线且长度不变和赤道投影为直线的条件，将中央经线两侧一定经差范围内的球面正形投影于圆柱面。然后将圆柱面沿过南北极的母线剪开展平，即获高斯一克吕格投影平面。 一、只谈比较常用的几种：“墨卡托投影”、“高斯-克吕格投影”、“UTM 投影”、“兰勃特等角投影” 1．墨卡托(Mercator)投影 1.1 墨卡托投影简介 墨卡托(Mercator)投影，是一种" 等角正切圆柱投影”，荷兰地图学家墨卡托（Gerhardus Mercator 1512－1594）在1569年拟定，假设地球被围在一中空的圆柱里，其标准纬线与圆柱相切接触，然后再假想地球中心有一盏灯，把球面上的图形投影到圆柱体上，再把圆柱体展开，这就是一幅选定标准纬线上的“墨卡托投影”绘制出的地图。 墨卡托投影没有角度变形，由每一点向各方向的长度比相等，它的经纬线都是平行直线，且相交成直角，经线间隔相等，纬线间隔从标准纬线向两极逐渐增大。墨卡托投影的地图上长度和面积变形明显，但标准纬线无变形，从标准纬线向两极变形逐渐增大，但因为它具有各个方向均等扩大的特性，保持了方向和相互位置关系的正确。 在地图上保持方向和角度的正确是墨卡托投影的优点，墨卡托投影地图常用作航海图和航空图，如果循着墨卡托投影图上两点间的直线航行，方向不变可以一直到达目的地，因此它对船舰在航行中定位、确定航向都具有有利条件，给航海者带来很大方便。 “海底地形图编绘规范”（GB/T 17834-1999，海军航保部起草）中规定1：25万及更小比例尺的海图采用墨卡托投影，其中基本比例尺海底地形图（1：5万，1：25万，1：100万）采用统一基准纬线30°，非基本比例尺图以制图区域中纬为基准纬线。基准纬线取至整度或整分。 1.2 墨卡托投影坐标系 取零子午线或自定义原点经线(L0)与赤道交点的投影为原点，零子午线或自定义原点经线的投影为纵坐标X轴，赤道的投影为横坐标Y轴，构成墨卡托平面直角坐标系。 2．高斯-克吕格(Gauss-Kruger)投影和UTM（Universal
算法设计课程设计 题目图着色问题 姓名学号 专业年级 指导教师职称 2014年 12月 4日
图的m着色问题 1 摘要 (3) 2 图的着色问题 (4) 2.1 图的着色问题的来源 (4) 2.2 图的着色问题的描述 (4) 3算法的基本思想 (4) 3.1 求极小覆盖法----布尔代数法 (4) 3.2 穷举法－Welch Powell着色法 (4) 3.3 回溯法 (4) 3.4 贪心法 (4) 3.5 蚁群算法 (5) 4算法步骤 (5) 4.1 求极小覆盖法----布尔代数法 (4) 4.2 穷举法－Welch Powell着色法 (4) 4.3 回溯法 (4) 4.4 贪心法 (4) 4.5 蚁群法 (4) 5 理论分析（复杂度比较）、实验性能比较 (7) 5.1 复杂度分析 (4) 5.2 实验性能比较 (4) 6 心得体会 (8) 7参考文献 (8) 8 附录 (8)
摘要 图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。 关键词：图着色 c++代码 2、图的着色问题 2.1图的着色问题的来源 1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。 用四种颜色着色的世界地图： 采用四种颜色着色的美国地图： 2.2图的着色问题的描述 （一）图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 （二）通常所说的着色问题是指下述两类问题：
一、需求分析 1、问题描述 现在有一张地图，为了便于区别各个地图上的板块，地图上相 邻的颜色块应该是不同的颜色。现在的任务是给定一张地图，要对其进行着色，相邻的板块之间的颜色不能相同，输出最后 的着色的方案。 2、基本分析 功能一：为了程序的灵活性，可以让程序自由建立图 功能二：为建好的图进行着色。 3、输入输出 输入一张图的信息，正确输入边数和顶点数，输入边的关系（两 个顶点之间的），颜色只要四种，分别用数字1到4表示。 输出时根据每个顶点不同的标号输出着色的结果。 二、概要设计 1、设计思路 给定四种颜色，从选定的第一个顶点开始着色，先是第一种颜 色，如果这个颜色与这个顶点的其他邻接顶点颜色不重复，则 这个顶点可以使用此颜色，程序开始对下一个顶点着色；如果 着色重复，则使用下一种颜色重复上述过程。着色过程就是一 个递归的过程，直到所有的顶点都有着色后结束着色过程
结束
2、数据结构设计： 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构是邻接矩阵，考虑用邻接表是因为一般的地图的某一 个顶点并不会与很多的顶点邻接，如果用邻接矩阵就能符合实 际的需求，虽然占用稍大的空间，但是增强了程序的实际使用 性。 抽象数据类型定义如下： 数据对象是点和边（vex&adj） 数据关系是颜色分布以及边的相邻的两个顶点 基本操作： CreatGrouph(&G); 创建一张需要操作的无向图G Destroy(Graph &G); 初始条件：无向图G存在 操作结果：销毁图G LocateVex(&G,i) 初始条件：无向图G存在 操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息 Trycolor(current &G,store[]) 初始条件：无向图G存在，在图中有第current个顶点
3．地图投影的基本问题 3．1地图投影的概念 在数学中，投影（Project）的含义是指建立两个点集间一一对应的映射关系。同样，在地图学中，地图投影就是指建立地球表面上的点与投影平面上点之间的一一对应关系。地图投影的基本问题就是利用一定的数学法则把地球表面上的经纬线网表示到平面上。凡是地理信息系统就必然要考虑到地图投影，地图投影的使用保证了空间信息在地域上的联系和完整性，在各类地理信息系统的建立过程中，选择适当的地图投影系统是首先要考虑的问题。由于地球椭球体表面是曲面，而地图通常是要绘制在平面图纸上，因此制图时首先要把曲面展为平面，然而球面是个不可展的曲面，即把它直接展为平面时，不可能不发生破裂或褶皱。若用这种具有破裂或褶皱的平面绘制地图，显然是不实际的，所以必须采用特殊的方法将曲面展开，使其成为没有破裂或褶皱的平面。 3．2地图投影的变形 3．2．1变形的种类 地图投影的方法很多，用不同的投影方法得到的经纬线网形式不同。用地图投影的方法将球面展为平面，虽然可以保持图形的完整和连续，但它们与球面上的经纬线网形状并不完全相似。这表明投影之后，地图上的经纬线网发生了变形，因而根据地理坐标展绘在地图上的各种地面事物，也必然随之发生变形。这种变形使地面事物的几何特性（长度、方向、面积）受到破坏。把地图上的经纬线网与地球仪上的经纬线网进行比较，可以发现变形表现在长度、面积和角度三个方面，分别用长度比、面积比的变化显示投影中长度变形和面积变形。如果长度变形或面积变形为零，则没有长度变形或没有面积变形。角度变形即某一角度投影后角值与它在地球表面上固有角值之差。 1）长度变形 即地图上的经纬线长度与地球仪上的经纬线长度特点并不完全相同，地图上的经纬线长度并非都是按照同一比例缩小的，这表明地图上具有长度变形。 在地球仪上经纬线的长度具有下列特点：第一，纬线长度不等，其中赤道最长，纬度越高，纬线越短，极地的纬线长度为零；第二，在同一条纬线上，经差相同的纬线弧长相等；第三，所有的经线长度都相等。长度变形的情况因投影而异。在同一投影上，长度变形不仅随地点而改变，在同一点上还因方向不同而不同。 2）面积变形 即由于地图上经纬线网格面积与地球仪经纬线网格面积的特点不同，在地图上经纬线网格面积不是按照同一比例缩小的，这表明地图上具有面积变形。 在地球仪上经纬线网格的面积具有下列特点：第一，在同一纬度带内，经差相同的网络面积相等。第二，在同一经度带内，纬线越高，网络面积越小。然而地图上却并非完全如此。如在图4-9-a上，同一纬度带内，纬差相等的网格面积相等，这些面积不是按照同一比例缩
一：等角正切方位投影(球面极地投影) 概念：以极为投影中心,纬线为同心圆，经线为辐射的 直线，纬距由中心向外扩大。 变形:投影中央部分的长度和面积变形小，向外变形逐渐增 大。 用途:主要用于编绘两极地区，国际1∶100万地形图。 二：等距正割圆锥投影 概念：圆锥体面割于球面两条纬线。 变形:纬线呈同心圆弧，经线呈辐射的直线束。 各经线和两标纬无长度变形，即其它纬线均有 长度变形，在两标纬间角度、长度和面积变形 为负，在两标纬外侧变形为正。离开标纬愈远， 变形的绝对值则愈大。 用途:用于编绘东西方向长，南北方向稍宽地区 的地图，如前苏联全图等。 三：等积正割圆锥投影 概念:满足ｍｎ＝1条件，即在两标纬间经线长度放 大,纬线等倍缩小，两标纬外情况相反。 变形:在标纬上无变形，两标纬间经线长度变形为正， 纬线长度变形为负；在两标纬外侧情况相反。角度 变形在标纬附近很小，离标纬愈远，变形则愈大。 用途:编绘东西南北近乎等大的地区，以及要求面积 正确的各种自然和社会经济地图。
四：等角正割圆锥投影 概念：满足m=n条件，两标纬间经线长度与纬线长度 同程度的缩小，两标纬外同程度的放大。 变形：在标纬上无变形，两标纬间变形为负，标纬外变 形为正，离标纬愈远，变形绝对值则愈大。 用途：用于要求方向正确的自然地图、风向图、洋流图、 航空图，以及要求形状相似的区域地图；并广泛用于制 作各种比例尺的地形图的数学基础。 如我国在1949年前测制的1∶5万地形图，法国、比利 时、西班牙等国家亦曾用它作地形图数学基础，二次大 战后美国用它编制1∶100万航空图。 五：等角正切圆柱投影——墨卡托投影 概念：圆柱体面切于赤道，按等角条件，将经 纬线投影到圆柱体面上，沿某一母线将圆柱体 面剖开，展成平面而形成的投影。是由荷兰制 图学家墨卡托（生于今比利时）于1569年创拟 的，故又称（墨卡托投影）。 变形：经线为等间距的平行直线，纬线为非等 间距垂直于经线的平行直线。离赤道愈远，纬 线的间距愈大。纬度60°以上变形急剧增大， 极点处为无穷大，面积亦随之增大，且与纬线 长度增大倍数的平方成正比，致使原来只有南 美洲面积1/9的位于高纬度的格陵兰岛，在图 上比南美洲大。 用途:等角航线表现为直线，用于编制海图、印度尼西亚和赤道非洲等赤道附近国家和地区的地图、世界时区图和卫星轨迹图等。
1万地图缩编成5万地图的方法 一：面文件由MapGIS格式转换为shp格式 1：注意：mapgis的区文件转换直接转换为.shp文件格式时，会有属性的丢失，为了防止此种情况，一般是先将mapgis格式文件转换为.eoo格式化，再将eoo格式的文件转换为shp 文件，这样属性就不会丢失了 2：操作步骤：在mapgis主菜单下打开“文件转换”---→装入所需的区文件--→输入eoo文件-→输入eoo文件-→输入shape文件
3：在arcmap中打开属性表并检查多边形几何形状和属性是否正确； 二：（这些操作都是在arcgis里完成） 1 ；区域的概括（1万的图转换成5万的图的核心就在于地类图斑在融合） 1：修复 几何形状：使用ArcToolbox/Repair Geometry工具修复：目的在于修复破碎图斑 转出的数据可能存在1-3个多边形无属性，可以在属性表中检查； 2、融合 使用ArcToolbox/dissolve融合二级分类，生成新的Shape文件（二级地类），选择所需要在字段；（别钩create multipart features,否则会连成一片） Dissolve的操作方法同repair,在生成新的SHP文件时，注意所需要的字段
3、使用ArcTollbox/Eliminate去除小于1000平方米的图斑，并编辑（制图综合）小图斑（居民点水域5000-1万平方米，耕地园地1万－1.5万平方米，其它2.5万平方米），生成符合1：5万图斑大小要求的综合图。（Eliminate需要先选择小图斑，然后在综合）。 ?同2输入eliminate ?进入属性表后，在option下，选择select by attributes ?双击面积字段并输入<1000 ?ArcTollbox/search 中删除面积小于10000平方米的图斑，同时自动生成新的shp文件?删除耕地面积15000，前面步骤同前4步，只是表达式为"地类编码" = '011' AND "面积" <15000
世界地图常用地图投影知识大全 在不同的场合和用途下使用不同的地图投影,地图投影方法及分类名目众多,象:墨卡托投影,空间斜轴墨卡托投影,桑逊投影,摩尔维特投影,古德投影,等差分纬线多圆锥投影,横轴等积方位投影,横轴等角方位投影,正轴等距方位投影,斜轴等积方位投影,正轴等角圆锥投影,彭纳投影,高斯-克吕格投影,等角圆锥投影等等。 一、世界地图常用投影 1、等差分纬线多圆锥投影（Polyconic Projection With Meridional Interval on Same Parallel Decrease Away From Central Meridian by Equal Difference） 普通多圆锥投影的经纬线网具有很强的球形感，但由于同一纬线上的经线间隔相等，在编制世界地图时，会导致图形边缘具有较大面积变形。1963年中国地图出版社在普通多圆锥投影的基础上，设计出了等差分纬线多圆锥投影。 等差分纬线多圆锥投影的赤道和中央经线是相互垂直的直线，中央经线长度比等于1；其它纬线为凸向对称于赤道的同轴圆弧，其圆心位于中央经线的延长线上，中央经线上的纬线间隔从赤道向高纬略有放大；其它经线为凹向对称于中央经线的曲线，其经线间隔随离中央经线距离的增加而按等差级数递减；极点投影成圆弧(一般被图廓截掉),其长度等于赤道的一半（图2-30）。 通过对大陆的合理配置，该投影能完整地表现太平洋及其沿岸国家，突出显示我国与邻近国家的水陆关系。从变形性质上看，等差分纬线多圆锥投影属于面积变形不大的任意投影。我国绝大部分地区的面积变形在10%以内。中央经线和±44o纬线的交点处没有角度变形，随远离该点变形愈大。全国大部分地区的最大角度变形在10o以内。等差分纬线多圆锥投影是我国编制各种世界政区图和其它类型世界地图的最主要的投影之一。
算法分析与设计课程设计说明书 地图着色 学院：计算机与控制工程学院 专业：计算机科学与技术 学生姓名：xxxxx学号：成绩 学生姓名：xxxxx 学号：成绩 指导教师：
内容提要 此题为地图着色问题，由地图着色问题很容易想到图的着色问题，因此可以把地图抽象为无向图来解决地图的着色问题。对地图的抽象相当于对图的抽象，即以邻接矩阵来实现地图的区域相邻的描绘，而对地图的区域数即以图的顶点数来描绘。设计说明书的内容包括需求分析，概要设计，详细设计，代码实现，后期测试等内容，需求分析是对此问题所需要实现的功能的介绍，概要设计是对所需要实现功能的模块划分，以及初步的实现思想，详细设计通过编写大致的代码来实现功能，代码实现则是具体的解决问题，解决此问题设计了两个算法，贪心，回溯，在程序的测试阶段，回溯算法对同一个问题的解决速率高于贪心算法，但是结果都是以最少的颜色数来染色。 课题实现的环境是在window环境下的eclipse中，通过在其中输入地图的区域数，图的连接情况，来选择相应的算法来实现染色，本次课题所采用的数据结构主要是二维数组来抽象图的邻接矩阵。
目录 1引言（或绪论） (1) 2需求分析 (2) 2.1 问题分析 (2) 2.3问题解决 (2) 2.3 运行环境及开发工具 (3) 2.4功能需求 (3) 2.4.1 地图的抽象及输入 (3) 2.4.2 地图着色的算法设计 (3) 2.4.3 界面设计 (3) 2.4.4 输出设计 (3) 2.5任务分配 (4) 3概要设计 (4) 3.1 数据定义 (4) 3.2 功能模块定义 (4) 3.2.1 地图的抽象输入模块 (4) 3.2.2 输出模块 (4) 3.2.3 地图染色模块 (4) 3.2.4 界面设计模块 (5) 3.2.5 主模块 (5) 3.3 程序流程图 (6) 4 详细设计 (7) 4.1 地图输入模块 (7) 4.1.1 数据类型 (7) 4.1.2 具体实现 (7) 4.2 界面设计模块 (7) 4.2.1 数据类型 (7) 4.2.2 具体实现 (7) 4.3 算法设计模块 (9) 4.3.1 回溯法过程 (9)
2019年高考地理复习轻松记忆地图的四种 方法 地理的学习离不开地图，为此查字典地理网整理了轻松记忆地图的四种方法，请大家学习。 1、阅图忆文，看文思图 掌握地图知识的落点应放在发现特征、理解概念、揭示规律、阐明成因上。如果片面阅图而不思文，知识显得支离破碎。反之死记课文，地理概念失去具体形象的支持，必然造成张冠李戴、桃李不分。尤其高中学生抽象思维发展很快，语言表达能力较强，教学中要训练学生写读图说明文，提取说明要点，开展课后讨论活动，把课本知识活化于地图之中。2、人为设图，图形赋意 为使图像内地理事物的相互区位关系更加明确，把地理事物依附在人为设计的几何框架之内。如长江三角洲工业区，可在图上将无锡、苏州、宜兴、湖州围绕太湖连成一侧立的梯形；说明英国五大城市位置采用金线穿珠的办法，将利物浦、曼彻斯特、谢菲尔德、伯明翰、伦敦用反S形穿起来说明英国五大城市位置。又如：澳大利亚东南部悉尼等三城市构成三星式裕溪口和芜湖构成隔河连珠。还可将图形作形象说明，例如用Y表示波罗的海的外形等。 在填图训练中，根据整体局部整体的原则，大小图结合，按先读图，后简化，最后复原的程序练习。即：先看总图，再
出示暗射图，在脑海中浮现和拼图；接着简化填绘、仿制，最后打开地图册验证复原。由于调动了各个感官协调动作，使地图知识记得住、记得牢。 3、丰富联想，词图对照 一味背图、填图是乏味的。应根据人和动物共有的反射机制，对信息源做恰当处理。采用多办法刺激，以获得运动记忆和情绪记忆的最佳效果。把抽象的地图符号化作具体物象激发联想，如柴达木盆地区域图有矿区，有铁路，编成冷湖向东把鱼(鱼卡)打，打柴(大柴旦)南去锡山(锡铁山)下，挥汗(察尔汗)砍得格尔木，火车东运到茶卡，一边看图一边诵词，很快就能记住这部分图。 4、要点精减，信号提示 对地图承载的信息要分析、加工、分化、改组；提高其精度；缩小范围，排除干扰渠道。正确的做法应该是：(1)以示意图为基础，先易后难，如铁路采取干线为本，枢纽填准，变曲为直的办法，就易掌握。(2)用单色笔和多色彩笔勾画插图，然后再和地图册对照。这样先看黑白后看彩电，可起突出重点，互相弥补作用。(3)对难记内容进行强化，揭示区域图的关键点，如在图例练习课和快速查图比赛中可不停地揭示，如水电站应画在水库的上游还是下游?基尔运河是在国界上通过吗?石太线的中点是哪个矿区?吴哥窟画面上有几个塔?等等。(4)抓住文字特征，简化信号。如在学习朝鲜东部港口
课程设计报告 课程设计题目：地图着色问题 专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx
一：需求分析： 1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使 用的颜色总数最少； 2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行； 4)最后对结果做出简单分析。 二：概要设计 一：设计思路 把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。 二：数据结构设计 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。 其中： typedef struct ArcNode { int x; （表示与当前顶点所表示省份相邻的省份的位置信息） struct ArcNode *next; （指向下一个弧结点） }ArcNode; （表示省份之间相邻关系的弧结点） typedef struct { char *name; （顶点所表示的省份的名称） int color; （省份的颜色，用数字表示不同的颜色） ArcNode *firstnext; （指向第一个弧） }shengfen[35];
课程设计报告 课程设计题目：地图着色问题专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx
一：需求分析： 1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使 用的颜色总数最少； 2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行； 4)最后对结果做出简单分析。 二：概要设计 一：设计思路 把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。 二：数据结构设计 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。 其中： typedef struct ArcNode { int x; （表示与当前顶点所表示省份相邻的省份的位置信息） struct ArcNode *next; （指向下一个弧结点） }ArcNode; （表示省份之间相邻关系的弧结点） typedef struct { char *name; （顶点所表示的省份的名称） int color; （省份的颜色，用数字表示不同的颜色） ArcNode *firstnext; （指向第一个弧） }shengfen[35]; 2 三：详细设计 该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。 1.初始化模块
一、制图人需要具备的基本知识与技能； 二、适合用于制作定向越野图的底图； 三、定向越野的场地制作一一野外勘测； 四、绘图一一OCAD软件的使用（简介）。 9. 1制图人需要具备的基本知识与技能 9. 1 . 1制作定向地图涉及的知识面 ①地质地貌学一一想要正确的表现出不同类型的地貌及其图形特点，需要知道地貌的成因； ②绘图学一一地图是由各种符号组成的，我们不能不了解他们的构成、色彩、表达方式、 绘制特点与要求； ③地图编制与印制的常识一一地图对地形（即地物与地貌）的表示方法是一个完整的技 术艺术体系，因此，制作地图的过程就必须是一个遵循制图规律的独特的工艺流程，并采用科学的理论与先进的技术手段； ④测量学一一因为没有现成的地图完全适合于定向运动； ⑤定向运动基本常识不言而喻（一下同）； ⑥国际定向运动图制图规范； ⑦各类、各级定向运动比赛的规则； ⑧定向路线设计的原理与原则； ⑨OCAD制图软件的使用； ⑩参加定向运动比赛的实际经验（这一点十分重要）。 9. 1 . 2工作性质与环境对制图人提出的要求 ? 强健的生理与心理状态 野外测图是制作定向地图最关键，也是最基础的工作。您若想从事这项工作，不仅需要具有较多的经验，较强的专业能力，其实您首先必须具备的是要有“异于常人”的性格、意志、心理和体能的状态。 在定向这个行业中，在没有谁的特殊性彼得上测绘定向地图的人啦。长期孤身一人在寂 静无声的山野丛林中上上下下，兜兜转转，脑力体力经常透支。特别是不可避免的枯燥乏味、孤独寂寞，还要忍受地理环境、季节气候甚至是野生动物带来的身心压力。 假如再有时间限制（通常都由计划比赛的时间限定），时间因素就成了压力倍增器。因
世界地图常用地图投影知识大全 2009－09－30 １3:20 在不同的场合和用途下使用不同的地图投影,地图投影方法及分类名目众多，象:墨卡托投影,空间斜轴墨卡托投影,桑逊投影,摩尔维特投影,古德投影,等差分纬线多圆锥投影,横轴等积方位投影,横轴等角方位投影,正轴等距方位投影,斜轴等积方位投影,正轴等 角圆锥投影,彭纳投影,高斯-克吕格投影,等角圆锥投影等等。 一、世界地图常用投影 1、等差分纬线多圆锥投影（Polyｃonic Projecｔion With Meridional Interval o ｎＳaｍe Parａllel Ｄeｃreaｓe AｗaｙＦｒｏm Cｅntrａl Meridｉａn ｂｙ E ｑuaｌ Dｉffeｒence） 普通多圆锥投影的经纬线网具有很强的球形感，但由于同一纬线上的经线间隔相等,在编制世界地图时,会导致图形边缘具有较大面积变形。1９６3年中国地图出版社在普通多圆锥投影的基础上，设计出了等差分纬线多圆锥投影。 等差分纬线多圆锥投影的赤道和中央经线是相互垂直的直线，中央经线长度比等于1；其它纬线为凸向对称于赤道的同轴圆弧,其圆心位于中央经线的延长线上，中央经线上的纬线间隔从赤道向高纬略有放大;其它经线为凹向对称于中央经线的曲线，其经线间隔随离中央经线距离的增加而按等差级数递减；极点投影成圆弧(一般被图廓截掉),其长度等于赤道的一半（图２-３0）。 通过对大陆的合理配置，该投影能完整地表现太平洋及其沿岸国家，突出显示我国与邻近国家的水陆关系。从变形性质上看，等差分纬线多圆锥投影属于面积变形不大的任意投影。我国绝大部分地区的面积变形在10%以内。中央经线和±4４o纬线的交点处没有角度变形，随远离该点变形愈大。全国大部分地区的最大角度变形在10o以内。等差分纬线多圆锥投影是我国编制各种世界政区图和其它类型世界地图的最主要的投影之一。
一、只谈比较常用的几种：“墨卡托投影”、“高斯-克吕格投影”、“UTM投影”、“兰勃特等角投影。 1．墨卡托(Mercator)投影 1.1 墨卡托投影简介 墨卡托(Mercator)投影，是一种"等角正切圆柱投影”，荷兰地图学家墨卡托（GerhardusMercator1512－1594）在1569年拟定，假设地球被围在一中空的圆柱里，其标准纬线与圆柱相切接触，然后再假想地球中心有一盏灯，把球面上的图形投影到圆柱体上，再把圆柱体展开，这就是一幅选定标准纬线上的“墨卡托投影”绘制出的地图。 墨卡托投影没有角度变形，由每一点向各方向的长度比相等，它的经纬线都是平行直线，且相交成直角，经线间隔相等，纬线间隔从标准纬线向两极逐渐增大。墨卡托投影的地图上长度和面积变形明显，但标准纬线无变形，从标准纬线向两极变形逐渐增大，但因为它具有各个方向均等扩大的特性，保持了方向和相互位置关系的正确。 在地图上保持方向和角度的正确是墨卡托投影的优点，墨卡托投影地图常用作航海图和航空图，如果循着墨卡托投影图上两点间的直线航行，方向不变可以一直到达目的地，因此它对船舰在航行中定位、确定航向都具有有利条件，给航海者带来很大方便。 “海底地形图编绘规范”（GB/T17834-1999，海军航保部起草）中规定1：25万及更小比例尺的海图采用墨卡托投影，其中基本比例尺海底地形图（1：5万，1：25万，1：100万）采用统一基准纬线30°，非基本比例尺图以制图区域中纬为基准纬线。基准纬线取至整度或整分。 1.2 墨卡托投影坐标系 取零子午线或自定义原点经线(L0)与赤道交点的投影为原点，零子午线或自定义原点经线的投影为纵坐标X轴，赤道的投影为横坐标Y轴，构成墨卡托平面直角坐标系。 2．高斯-克吕格(Gauss-Kruger)投影和UTM（UniversalTransverseMercator）投影 2.1 高斯-克吕格投影简介 高斯-克吕格（Gauss-Kruger）投影，是一种“等角横切圆柱投影”。德国数学家、物理学家、天文学家高斯（CarlFriedrichＧauss，1777一1855）于十九世纪二十年代拟定，后经德国大地测量学家克吕格（JohannesKruger，1857～1928）于1912年对投影公式加以补充，故名。设想用一个圆柱横切于球面上投影带的中央经线，按照投影带中央经线投影为直线且长度不变和赤道投影为直线的条件，将中央经线两侧一定经差范围内的球面正形投影于圆柱面。然后将圆柱面沿过南北极的母线剪开展平，即获高斯一克吕格投影平面。 高斯一克吕格投影后，除中央经线和赤道为直线外，其他经线均为对称于中央经线的曲线。高斯-克吕格投影没有角度变形，在长度和面积上变形也很小，中央经线无变形，自中央经线向投影带边缘，变形逐渐增加，变形最大处在投影带内赤道的两端。由于其投影精度高，变形小，而且计算简便（各投影带坐标一致，只要算出一个带的数据，其他各带都能应用），因此在大比例尺地形图中应用，可以满足军事上各种需要，并能在图上进行精确的量测计算。 按一定经差将地球椭球面划分成若干投影带，这是高斯投影中限制长度变形的最有效方法。分带时既要控制长度变形使其不大于测图误差，又要使带数不致过多以减少换带计算工作，据此原则将地球椭球面沿子午线划分成经差相等的瓜瓣形地带，以便分带投影。通常按经差6度或3度分为六度带或三度带。六度带自0度子午线起每隔经差6度自西向东分带，带号依次编为第1、2…60带。三度带是在六度带的基础上分成的，它的中央子午线与六度带的中央子午线和分带子午线重合，即自1.5度子午线起每隔经差3度自西向东分带，带号
地图投影全解析 科技名词定义 中文名称：地图投影 英文名称：map projection 定义1：按照一定的数学法则，把参考椭球面上的点、线投影到可展面上的方法。 所属学科：测绘学（一级学科）；测绘学总类（二级学科） 定义2：根据一定的数学法则，将地球表面上的经纬线网相应地转绘成平面上经纬线网的方法。 所属学科：大气科学（一级学科）；动力气象学（二级学科） 定义3：运用一定的数学法则，将地球椭球面的经纬线网相应地投影到平面上的方法。即将椭球面上各点的地球坐标变换为平面相应点的直角坐标的方法。 所属学科：地理学（一级学科）；地图学（二级学科） 本内容由全国科学技术名词审定委员会审定公布 地图投影是利用一定数学方法则把地球表面的经、纬线转换到平面上的理论和方法。由于地球是一个赤道略宽两极略扁的不规则的梨形球体，故其表面是一个不可展平的曲面，所以运用任何数学方法进行这种转换都会产生误差和变形，为按照不同的需求缩小误差，就产生了各种投影方法。 目录
展开 定义 地图投影,Map Projection.把地球表面的任意点，利用一定数学法则，转换到地图平面上的理论和方法。 地图投影 书面概念化定义：地图投影就是指建立地球表面（或其他星球表面或天球面）上的点与投影平面（即地图平面）上点之间的一一对应关系的方法。即建立之间的数学转换公式。它将作为一个不可展平的曲面即地球表面投影到一个平面的基本方法，保证了空间信息在区域上的联系与完整。这个投影过程将产生投影变形，而且不同的投影方法具有不同性质和大小的投影变形。 由于球面上任何一点的位置是用地理坐标（λ，φ）表示的，而平面上的点的位置是用直角坐标（χ，у）或极坐标（r，）表示的，所以要想将地球表面上的点转移到平面上，必须采用一定的方法来确定地理坐标与平面
两种实用地图着色算法的比较与实现 摘要：地图着色算法的研究是为了是把相邻的区域用尽可能少的颜色区分开。四色猜想是从理论上指出地图着色所需最小着色数，但考虑到实际应用中速度因素，只需采用尽可能优化的地图着色方案，本文中对两种实用算法进行了比较和实现。 关键字：四色猜想；地图着色；DFS 引言 “四色猜想”虽然至今尚未得到一个严格的数学证明，但人们似乎已经默认这一著名猜想是对的，即任意一个平图都可以用至多四种不同的颜色对其平面区域进行正常着色。地图着色的应用研究是为了是把相邻的区域用尽可能少的颜色区分开，而不是针对“四色猜想”的问题本身[1]。地图着色实际应用中速度指标和颜色数目指标同样重要，目标是在可容忍时间消耗的基础上采用尽可能少的颜色进行着色[2]。 着色算法 对于平面图的着色问题的研究一直成为研究热点，特别是随着计算机的出现和广泛应用，图的着色理论也有了迅速的发展，其应用日益广泛[3][4]。现在已经成为研究系统工程、管理工程、计算机可续、通讯、网络理论、运筹学等所必须的一种手段[5][6]。，本文从实际应用角度列举的两种算法都是实现基于四色猜想的着色优化，但并不一定是最佳的着色算法。 算法1：根据图G的邻接矩阵，依次按节点序号遍历所有节点，进行着色。先用一种颜色对节点着色，判断矩阵中与该节点相邻的节点的颜色是否相同，如果不同，则继续对其他节点遍历。如果相同，则改用其他颜色尝试，直至与相邻点颜色不同。 算法中核心的颜色赋值和碰撞检测处理步骤如下： For (依次遍历图的所有节点i) {For (依次判断的最大颜色数目,颜色j) {给节点i赋值颜色j； For (序号k小于该节点序号i的节点)
空间参照系统和地图投影 导读：正如上一章所描述的，一个要素要进行定位，必须嵌入到一个空间参照系中，因为GIS所描述是位于地球表面的信息，所以根据地球椭球体建立的地理坐标（经 纬网）可以作为所有要素的参照系统。因为地球是一个不规则的球体，为了能够将 其表面的内容显示在平面的显示器或纸面上，必须进行坐标变换。 本章讲述了地球椭球体参数、常见的投影类型。考虑到目前使用的1：100万以上地 形图都是采用高斯——克吕格投影，本章最后又对该种投影类型和相关的地形图分 幅标准做了简单介绍。 1．地球椭球体基本要素 1．1地球椭球体 1．1．1地球的形状 为了从数学上定义地球，必须建立一个地球表面的几何模型。这个模型由地球的形状决定的。它是一个较为接近地球形状的几何模型，即椭球体，是由一个椭圆绕着其短轴旋转而成。 地球自然表面是一个起伏不平、十分不规则的表面，有高山、丘陵和平原，又有江河湖海。地球表面约有71%的面积为海洋所占用，29%的面积是大陆与岛屿。陆地上最高点与海洋中最深处相差近20公里。这个高低不平的表面无法用数学公式表达，也无法进行运算。所以在量测与制图时，必须找一个规则的曲面来代替地球的自然表面。当海洋静止时，它的自由水面必定与该面上各点的重力方向（铅垂线方向）成正交，我们把这个面叫做水准面。但水准面有无数多个，其中有一个与静止的平均海水面相重合。可以设想这个静止的平均海水面穿过大陆和岛屿形成一个闭合的曲面，这就是大地水准面（图4-1）。 图4-1：大地水准面 大地水准面所包围的形体，叫大地球体。由于地球体内部质量分布的不均匀，引起重力方向的变化，导致处处和重力方向成正交的大地水准面成为一个不规则的，仍然是不能用数学表达的曲面。大地水准面形状虽然十分复杂，但从整体来看，起伏是微小的。它是一个很接近于绕自转轴（短轴）旋转的椭球体。所以在测量和制图中就用旋转椭球来代替大地球体，这个旋转球体通常称地球椭球体，简称椭球体。
数据结构实验报告 实验一：地图着色问题 班级：计算机科学与技术1班 姓名学号 完成日期：2015.11.16 一、题目描述 已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。 二、需求分析 1.已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保 证使用的颜色总数最少； 2.将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关 系； 3.演示程序以用户和计算机的对话方式进行； 4.最后对结果做出简单分析。 三、概要设计 把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。 结构设计： 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以选择邻接表来存储。
其中： typedef struct ArcNode { int x; // 表示与当前顶点所表示省份相邻的省份的位置信息 struct ArcNode *next; // 指向下一个弧结点 }ArcNode; // 表示省份之间相邻关系的弧结点 typedef struct { char *name; // 顶点所表示的省份的名称 int color; // 省份的颜色，用数字表示不同的颜色 ArcNode *firstnext; // 指向第一个弧 }Province[35]; 四、详细设计 该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。 1.初始化模块 声明表示省份的顶点信息、省份之间相邻关系的弧的信息，并为其赋值。 2.着色模块 // 分别为各个省份着色。 for(i=1;i<=34;i++) { province[i].color=0; } for(i=1;i<=34;i++) { j=1; p=province[i].firstnext; while(p!=NULL) { while(p!=NULL&&j!=province[p->x].color) { p=p->next; } if(p!=NULL) j++; } province[i].color=j; } 3.输出模块 输出各个省份的颜色信息。 for(i=1;i<=34;i++) {
图的染色问题 应锡娜06990213@https://www.doczj.com/doc/6e8798340.html, （浙江师范大学初阳学院，浙江金华321004） 摘要：本文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成果及当今的研究状况进行了阐述。 关键词：图；染色；色数 一、引言 图染色问题起源于著名的“四色猜想”[1]问题。早在一百多年前的1852年，英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。 二、研究与发展 “四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明。时隔二十七年后，1879年Kempe给出了“四色猜想”的第一个证明，又过了十一年，1980年Hewood发现Kempe的证明是错误的。但他指出，Kempe的证明方法虽然不能证明“四色猜想”，却可以证明用五种颜色就够了。此后，“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。直到1976年6月美国数学家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是正确的。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。[2] 值得指出的是，Appel与Haken的证明，计算机运行了1200个小时。诚然用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期待着用常规的数学方法证明“四色定理”。目前仍有许多数学家在潜心研究，寻求常规的证明方法。 地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各种形状，任意两个区域可以有公共边界，但不能有公共区域。于是人们开始研究所谓“平面图”。人们把地图中的每一个区域称为一个“面”，地图染色就是对“面”染色。进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面”相邻接，即地图中的两个区域有一段或几段公共边界，则在表示这两个区域的点之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边。如此，就可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图。其特点是：所有的点及边均处在同一平面上，并且任意两条边除端点外可以不交叉，人们称这样的图为平面图。例如图1的对偶图如图2所示。