毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
Welch-Powell图的点染色在现实生活中的应用(2)
染色理论是图论发展的重要分支之一。它起源于著名的“四色猜想”,就是在一个平面或球面上的任何地图总可以用至多四种颜色给每一个国家染色,使得没有两个相邻的国家染有相同的颜色。
经过四年的应用数学的本科教育,我了解到生活及科学领域中许多问题都可以由数学模型来建立,然而以图的形式来建立数学模型近年来更是推陈出新,它对图中某些对象按照一定规则进行分类,而染色正是对这些分类方法的一种直观的表现。所以染色问题是解决诸如时间表问题、排序问题、交通状态、运输安排、电路设计和贮藏问题等涉及任务分配的实际问题的基本方法[3]。
1.2 国内外的
研究现状
与发展
1.3 文中符号说明
1. [6]: 定义图 为一个有序对
2. [6]: 完全图
3. [6]: (顶)点集
4. [6]: 边集
5. [6]: 图 的色数
6. [6]: 图 的最大度
7. [6]: 图 的最小度
8. [6]: 度序列
9. [6]: 顶点的度
10. [6]: 图 的独立数
1.4 基本概念
图[7]:一个图是一个有序二元组 ,其中 是一个有限集合,称为 的顶点集合,其元素称为顶点; 是 元素的无序对的集合,称为 的边集合,其元素称为边。为方便起见,我们通常分用以 和 分别表示图 的顶点集合和边集合, 和 分别表示图 的顶点数和边数。若 和 都是有限的,则称图 是有限图,否则称为无限图。若 ,则称图 为 阶图。
完全图[7]:每两个各不同顶点之间都有一条边相连的简单图称为完全图。
导出子图[7]:若 且 包含了 中所有满足 的边 ,则称 是 的导出子图。
邻接矩阵[8]:有 个顶点的图 的邻接矩阵 是一个 矩阵,其中如果 邻接 则 ,否则 。
独立集[8]:一个图的点独立集(简称独立集)是指图中一些互不相邻的点构成的点子集。图 中含点数最多的独立集称为 的最大独立集。最大独立集所含的顶点数称为独立数,记为 ,简记为 。
二、与点染色相关的定义及定理
2.1 相关定义
定义1[4] 图 的一个正常 染色是指 种颜色 到 的各顶点的一个分配,使任意两个相邻点有不同的颜色。
定义2[4] 若 有正常 顶点染色,则称 是 顶点可染色的,给 进行正常染色所需要的最少颜色数称为 的色数,记为 。若 ,则称 为 色图。
定义3[4] 给定图 的一个 染色,用 表示 中染以第 色的顶点集合 ,则每个 都是 的独立集,因而 的一个 染色对应 的一个划分 ,其中每个 是独立集。反之,给出 的这样一个划分 ,其中每个 均是独立集 ,则相应的得到 的一个 染色,我们称 的这样一个划分为 的一个色划分。每个 称为色类 。因此 的色数 就是使这种划分成为可能的最小自然数 。
定义4[4] 设定图 是 染色图,若对 的所有 染色导出的关于 的划分均相同,则称 为唯一 可染色图,简称唯一可染色图。
共2页:
上一页
1
2
下一页
上一篇:
指数分布与几何分布的关系探讨
下一篇:
基于SVR支持向量回归模型的在线商品评论信息可信度分析研究
浅谈中学数学函数最值问题的求解方法
基于决策树算法的篮球联赛预测
数形结合在中学数学中的...
浙江省工业企业发展的因子分析
中美小学数学课堂教学的比较
杭州历年中考三角形的题型分析
论数形结合在中学数学教育中的应用
C#学校科研管理系统的设计
志愿者活动的调查问卷表
承德市事业单位档案管理...
公寓空调设计任务书
神经外科重症监护病房患...
医院财务风险因素分析及管理措施【2367字】
10万元能开儿童乐园吗,我...
AT89C52单片机的超声波测距...
中国学术生态细节考察《...
国内外图像分割技术研究现状