图论教学范文

图论教学范文（精选9篇）

图论教学 第1篇

但是图论的应用难点却并不在于算法本身, 而在于如何构图。特别是当问题并不是显山露水地以“图的模型”呈现时, 不少学生因为不会构图而陷入困境。相反, 那些构图能力比较强的学生, 却在建图之后利用“现成的、经典的”图论基础算法, 几乎一气呵成解决了问题。所以图论的教学应该非常注重培养学生的构建图能力。

教学中, 笔者都不会直截了当一开始就告诉学生“这节课我们学习图的什么概念, 或者学习图的什么算法”。而是从学生熟悉的身边事例、或是感兴趣的现实问题出发, 精心设计案例, 改进新课导入方式, 启发学生在一筹莫展之际更换思维角度, 在大多数学生都陷入困境之时才引入图论的正题。这样就避免了让学生的思维一开始就束缚在图论的框架之中, 迫使学生对图论“为了学而学”;让学生体验到了图论的应用魅力, 再来开展具体教学, 就转变成了让学生“为了用而学”。

信息学奥赛的图论课程通常分成三个单元:

第一单元:图论基础

正如上文提过的思路, 实际教学中笔者并不会一开始就对学生说“今天我们学图论基础”, 而是通过例题、案例来引入。这一单元通常采用“运动会赛程”这类问题来引入, 问题描述如下:

一年一度的学校田径运动会眼看就要举行了, 今年的运动会共设了N个比赛项目, 全校共有M个运动员, 每个运动员可以选报其中的几项参加比赛。现在各班的报名表都已经收齐汇总到了体育组, 老师们正在安排竞赛日程, 这里会遇到一个众所周知的问题:那就是同一个运动员报名的两个项目是不能同时比赛的, 但全校运动员很多, 报名参加多个项目的运动员也肯定不少, 现在根据报名表, 请你协助体育老师, 安排一个不会冲突的比赛日程。

比如给出下面这张报名表, 请安排至少需要几天才能全部比赛完。

看到这个问题, 大多学生普遍无从下手, 少数几个就着这张表, 在纸上涂涂画画, 搞了半天兴许能算出一个答案来, 可是再问这些学生, 如果比赛项目N和运动员数量M大一点, 比如100个项目, 1000个运动员, 还能算出来吗?这时他们也目瞪口呆, 没辙了。

就在大家都对正确解题方法翘首以盼的时候, 启发学生:把比赛项目当顶点, 同一个运动员报名参加的项目之间连一条边, 构造一个无向图。有了图, 问题就转化成了经典的地图着色问题:用不同的颜色对地图顶点着色, 要求有边相连的顶点颜色不同, 求至少需要几种颜色才能完成着色。

一旦把原来的“安排比赛日程问题”转述为“地图着色问题”, 解题的思路就完全不可同日而语了, 这时只需要简单的回溯算法就绰绰有余了。

解决了这道题, 学生对“图”的第一印象便是“神奇、好用”。也为后续课程的教学激发了浓厚的兴趣, 结合这个例子再让学生学习边、点、度等等概念术语, 学习邻接矩阵、邻接表等等存储方式, 他们就不再感到枯燥乏味。因为学生的眼光已经看到了图的妙不可言的应用。

第二单元:图的生成树

这一单元通常采用“校园连网”这类问题来引入, 问题描述如下:

全县有若干所学校, 为了实现资源共享, 教育主管部门决定把这些学校连成网络并统一接入国际互连网。因为任意两个学校之间的距离不同, 所以布设电缆的成本也不同。现在有关部门已经把任意两所学校之间的布线费用测算出来, 并列在一张表上, 请你根据这些测算设计一种布线方案, 使全部学校都能互相连通的总费用最少。

有了第一单元的学习, 学生对“校园连网”这类的问题不再无从下手, 他们会很自然地以“学校”为顶点、以“费用”为边构图。聪明的学生已经发现了n个顶点的无向图最多有n* (n-1) /2边, 本题的实质就是在n* (n-1) /2中选择n-1条边, 使得n个点连通并且费用最少。基于这样的思想, 把原图的全部边擦掉, 将这些边按费用大小排序, 然后每次取一条最小边, 重复n-1次直到所有点连在一起。这就是经典的Kruskal算法, 教学中要引导学生注意出现“环”的解决方法。

做这道题之前, 不要先给学生讲生成树, 做完之后启发学生讨论:在最后的方案中n所学校之间至少需要几条电缆就能把全部学校连成网络?最低总费用是否唯一?布线方案又是否唯一?当边的数量相对顶点的数量大很多的时候 (边稠密) 有没有其它效率更高的算法?相信这些问题搞清楚之后, 图的生成树教学内容也就完成的差不多了。

第三单元:最短路径

这一单元通常采用“货币套汇”这类问题来引入, 问题描述如下:

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如, 假定1美元可以买0.7英镑, 1英镑可以买9.5法郎, 且1法郎可以买到0.16美元。通过货币兑换, 一个商人可以从1美元开始买入, 得到0.7×9.5×0.16=1.064美元, 从而获得6.4%的利润。

现在给定n种货币C1、C2、…、Cn的有关兑换率, 请判断是否存在套汇的可能性。

比如下表所示的三种货币兑换汇率, 是不存在套汇可能的。

对于学完图论全部课程, 尤其是掌握的比较好的学生来说, 他们犀利的目光一眼就能望穿:本题是一道“图论”题目。但是对于初学者来说, 他们却并不能做到这一点。

基于和前面两个单元相同的教学思路, 给出这个问题之后, 安排足够的时间让学生先思考、交流。在讨论阶段, 重点启发学生构图:“看看能不能以什么为顶点?以什么为边?”向学生多问几遍这样的问题, 经过训练, 学生的构图能力会提高的很快。

其实本题只要以“货币”为顶点、“兑换汇率”为边构造一个有向图, 问题就转化为:求是否存在一个结点, 从自身出发经过若干其它节点, 回到自身节点, 值大于本身的“正圈”。算法实现时可以采用floyd求“正圈”进行判断。用f[i, j]表示货币i到货币j的汇率, 如果没有汇率, 那么f[i, j]=0, 初始的时候f[i, i]=1, 如果经过floyd处理后, 存在f[i, i]>1, 那么就存在套汇。其中floyd的更新如下:

应用图论知识解决问题, 通常包括三个步骤:第一步是审清题意, 构建图型;第二步是套用经典算法编码;第三步是测试与优化。其中第一步是关键, 只要把对应的图论模型建立起来, 问题也就突破了。

基础图论课程的三个单元之间有着天然的、密切的关系, 教学中要非常注重前呼后应, 而且通过精选的例题引入新课之后, 每一单元都还有很多丰富的细节需要补充、完善、提炼。

教学有法, 但无定法, 改进导入方式, 也许只是调整知识点的授课顺序, 或者精心选择几个恰当的例题, 往往都能收到意想不到的好效果。

摘要：图论是信息学奥赛的必修课程, 相关的考题通常都是竞赛中的压轴题, 所以图论课程的教学显得非常重要。但是图论课程具有“丰富的内容、复杂的体系、灵活的应用”诸多特点, 这又使得图论的教学充满挑战, 必须积极探索教学方式的改革, 努力提高教学效果。本文针对新课导入这一环节, 结合教学实际, 谈谈图论课程的教学尝试与体会。

关键词：信息学奥赛,图论教学,新课导入,生成树,最短路径

参考文献

[1]《图论的算法与程序设计 (PASCAL版) 》吴文虎清华大学出版社

[2]《图论教学方法探析》胡传峰《中国科技信息》2012年12期

《离散数学》图论部分习题 第2篇

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

李鱓水墨三变图论 第3篇

摘要：李鱓绘画的艺术思想、审美情操和绘画技法，由工到写到笨而发生的根本性变化，是他由宫廷走向民间的必然结果。他的“三变画风”，不仅拓展了写意花鸟画题材空间，还提出了“水为笔墨之介绍”等的技法理论和美学思想，树起了写意花鸟画新高峰，提升了写意花鸟画的地位，为中国美术史发展谱写增添了光辉。

关键词：李鱓绘画；写意花鸟画；三变画风；图像贡献

李鱓（1686年-1762年），字宗扬，号复堂，别号懊道入等，江苏省扬州市兴化县人（现属泰州市）。李鱓康熙五十年时25岁中举，28岁至33岁进宫，以画技至清宫担内廷供奉。45岁至49岁再度进宫，二次出宫后曾在山东任县官，55岁罢官回南方，真正走向民间，画风三突变。他的《四季花卉卷》曾被清宫《石渠宝笈》收录，是扬州八怪中唯一一个得到此誉的。传世作品有《五松图》《芭蕉萱石图》和《墨荷图》等。对赵之谦、吴昌硕、齐白石、吴弗之等都产生了很大的影响，对今天我们学习与鉴赏中国画有很大的帮助与启发。

一、三变画风识李鱓

李鱓和扬州八怪们一样，选择了不拘泥于枝叶形似，高度简括的手法塑造物象。在笔墨上，不受宫廷画技约束，直抒胸臆，和当时乃至今天流行的含蓄典雅工整的画风相违背，所以他们的怪就受到猛烈批评。我们从文史资料所知，李觯之怪的奥秘在“三变画风”，那么“三变画风”指什么样图式的“三变”？具体又表现在什么方面？我们不妨在此，以大致不同时期和相同画风的图像作品来作一点研究和赏评。

我考察李鱓各阶段的主要作品，认为应从其绘画风格鲜明变化、成熟创新作品和年龄阶段结合，来划分其变化的依据为妥，即建立“三变画风”的“风格说”进行概述。正如郑板桥对李鱓绘画发展在画上题跋所言：“复堂之画风三变。初从里中魏凌苍学山水，便尔明秀苍雄，过于所师。其后人都从南沙蒋廷锡学画。……后经崎岖患难，入都，得待高司寇其佩。又在扬州见石涛和尚画，因作破笔泼墨，画益奇。初入都一变，再人都又一变，变而愈上。盖规矩方圆，尺度颜色，深浅离合，丝毫不乱，藏在其中而外乏，浑洒脱落，皆妙谛也。六十外又一变……。”我认为“初人都一变”，这是指李鱓从小才智过人，早年在家乡学山水就超过老师，但28岁获得入宫作供奉内廷后，随蒋廷锡开始确立了院体工致花鸟画风，从山水转花鸟为“一变画风”，这里的“一变”毫无疑问（见图1）。我称之为“工致院体的一变画风”，即“工体一变画风”。

而“二变画风”应该是指李鱓二度进宫后“再入都又一变”“得待高司寇其佩”的写意画风基础上，加上二次出宫后“在扬州见石涛和尚画”而“因作破笔泼墨，画益奇”。并“变而愈上”“独立门户”才确立的写意花鸟画成熟的画风，这里不是简单地如板桥所言“再入都又一变”，仅学会写意而不“独立门户”就为“二变画风”。

李鱓45岁，已经是雍正八年1730年，得到第二次进宫的机会，被钦定随刑部侍郎高其佩学画。10月，他在扬州创作了这我称这时期的画风为“泼水写意的二变画风”即“泼写二变画风”。

既然水墨融趣泼写是李解二变的特征，那么他的“三变画风”又表现在哪里呢？他的好友郑板桥曾批评他说：“途穷卖画画益贱，庸儿贾竖论是非，昨画双松半未成，醉来怒裂澄心纸。”又说“六十外又一变，则散漫颓唐，无复筋骨，老可悲也”。这里恰恰道出了李鱓老后的寂寞与心情，常常因“昨画双松半未成，醉来怒裂澄心纸”偶作粗画。

从李鱓时年64岁（1749年乾隆十四年）作的图4《鸳鸯图》，见证他晚年风格由泼辣率意的成熟期，转而返璞归真的“老笨期”，即“三变画风”时期代表图像。“散漫颓唐，无复筋骨”的风格，正是他“三变画风”时期的意境。画面描绘荷塘水畔，鸳鸯双栖，笔墨老硬迟厚，颇重筋骨，造型与线势均是圆曲委婉。在今天看来是“象外之情”到“心中意境”的大美境地。此时作品不见笔墨，只见“大象”，“大象无形”是李觯老而笨的归宿。并非“散漫颓唐”之病。画中动物简直呼之欲出，虽锐气大减，但画面物象造型温顺，笔底顿挫腾挪，把玩自娱心境，而且不仅可玩赏、耐玩还更显养心善心温心，内在之真、人文涵养和创新精神尽显其中。当然，每个画家每个时期均有偶作粗画流于世或反复阶段，此漏非主流不作代表论。而板桥是个雅俗共赏而重造型的画家，无法到达和理解其“泼写艺境”到“拙真意境”的出现，故认“散漫颓唐”之病。我称之此为“拙笨归真的三变画风”即“拙真三变画风”。

二、“水为笔墨介绍”论

李鱓中年“二变画风”成熟时期，开始认识到了用水的重要性，形成破笔泼墨作画之时，领悟到用笔挥洒自如，泼墨酣畅淋漓，必须以水为媒方能达到理想的艺术效果，彰显写意之精神。我们发现他以用水见长代表作品中的芭蕉，最具水氣淋漓，用笔重厚水味十足，展现出枯湿浓淡均在一瞬间的天然之趣，让人叹为观止。可以说，确立李解美术史上的地位，恰是因其善于用水而写意的绘画技法和理论的突破，这是李鱓二变时期的精华所在。

图5《蕉竹图》是李鱓二出宫后泼写水墨经典作品，蕉叶侧锋入笔，竹竿中锋勾勒，竹叶空间多变化，芭蕉叶用水泼辣淋漓，颇似雨后湿润之气，后衬石块，随意写来，点苔不多但简练，通幅气势磅礴，用墨用水淋漓尽致。做到了水破墨和墨破水，二者并用，合而为一，已见其得悟于天然，得意于以水推墨和以水化意的艺术情境，是“以水为笔墨介绍”的典型代表作品。用水用得水气淋漓，气韵生动，既有徐渭的挥笔狂扫，也有八大的明润纯洁；既能水墨饱满，也能声色俱佳，是李鱓绘画不摹古人，展现出较强的创新艺术表现力，成为形成自己艺术风格的根本之道。以水韵墨，以水显味，水墨互泼，进一步衬托出芭蕉的鲜嫩之感、湿润之气和生命之美。友人郑燮在《芭蕉萱石图》题诗说：“君家蕉竹浙江东，此画还添柱石功。最羡先生清贵客，宫袍南院四时红。”可见其用水的艺术手法产生的美感使板桥羡慕不已。

正如李鱓对笔墨之道在《冷艳幽香图卷》自题说：“苏、米、倪、黄盛于元宋，有明若文衡山之文秀，白石翁之苍老，天池生之幽怪……本朝虞山夫子，画苑传人；高司寇指头生画，另开生面；八大山人长于用笔，清湘大涤子长于墨，至予则长于水。水为笔墨之介绍，用之得法，乃凝于神，甚矣，笔墨之难也……”在自题水墨花卉云：“八大山人长于用笔，而墨不及石涛。清湘大涤子用墨最佳，笔次之。笔与墨作合生动，妙在用水。余长于用水，而用墨用笔又不及二公甚矣。笔墨之难也。”反映了他绘画风格之变的实践心得和创新之幅《松藤图》（见图2）是写意画初始精品，图中之松，不见首尾，可见其雄伟。老藤盘绕，枝叶交错，用笔挥洒，用墨酣畅。画面上，苍老的松干上缠绕褚色藤萝，构图讲究，设色淡雅，用笔苍劲，泼墨淋漓，随意点染，却不零乱，很有整体感。尤其擅于用水，画面像刚画完时一样湿润清新。体现了他以抒发性情为个性的写意画风初步显露。

但他二次出宫，生活真正从宫廷转变到民间，艺术思想与艺术审美发生了根本性的变化，由于艺术手法上他有研究前辈大师林良、徐渭、高其佩等名家基础，故能在扬州见石涛笔法而备受感动，写意的天赋被唤醒，如鱼见水，破笔泼墨作画一发不可收拾。表现手法才开始有了新方向，艺术情趣转向了追求以娱为上的自由境界。所以，“绘画格调以画为娱则高，以画为业则陋”的思想呼之而出，他开始不断地拓展写意花鸟画的表现领域，如花草树木、日常用具、桑蚕之类等能画则画。这时的他从宫内到宫外，犹如一头饥饿的猛兽，以广泛创新的题材，寻求“画为娱则高”的艺术之境。创造性地把“破笔泼墨和没骨法综合为一”，直舒心怀的写意花鸟画表现新变法，人们称这时期画风为“水墨融成奇趣”。至此，我们观其画风才真正感知到水墨融趣的“二变画风”。作品达到了晚清画论家秦祖永《桐荫论画》所曰：“李鱓复堂，纵横驰骋，不拘绳墨，自得天趣，颇擅胜场。”的艺术效果。

看“二变画风”时期，李鱓56岁在扬州之力作图3《年年有余》，突破了日常平面样式构图，采用凌空倒挂式的超空间构图，两条鲶鱼一肚一背的造型安排，凸现主题突出，印象深刻；再以草绳连之，形成三线交错而成“女”字形，图像生动轻灵，自由舒展，一气呵成，生趣盎然。从鱼背的水墨技法表现，我们发现其以浓破淡而富层次，以水运墨而不走形，造型用笔以不拘于物象而生动。画中长文题跋，字迹参差错落，犹如自然植物由上而下舒展，与鱼一起随风荡漾，构成画面灵动气息，不仅增进了鱼的动态形式美，也表现出双鱼在前书法在后的空间艺境美。画面左边，上面一条鱼以写意之线，结构造型，形成淡色清韵，下面一条鱼以水泼墨，线面结合，结构造型，形成灰色墨味；画面右边，以浓墨书法线意造型，三线通长的书法组合，直中带曲窜在鱼后，形成重墨之色，达到黑白灰相交的变化效果。这种以书法结体和长短形状作为画面章法的形式来安排，成为他画面形式创新而自得其趣的风格标志，是其画风由工转写二变时期的成熟作品之一（图5更是泼写的代表作）。正是秦祖咏评价所说：“书法古朴，款题随意布置，另有别致，殆亦摆脱俗格，自立门庭者也。”

通过作品图像分析，其中的期盼生活“年年有余”和“美好吉祥”的精神涵义，让人想起他欲东山再起之念。然此时，他已进入用水见长、墨色造型和精于笔墨的世界，浓淡清润的水墨天趣，率真简练的平民意趣，使他的画风跨入了叛逆之路，命运已让他走向了“扬州八怪”。思，特别是对用水的认识。

由此，我们对他的用水之法便有了更进一步的体悟。他从工到写，将众家之长化为己有，使其最终在笔墨理论上对水与墨的关系有了自己的论述，使文人画理论与实践得到进一步的发展。至此，李鱓因发现水融笔墨的奥秘，完成了泼写技法的创新。

三、画风独立品自高

李鱓的画风由“工整”走向了“泼写”又走到了“老笨”，是一个有俗到雅到玩的过程。是一个自我创新，自立门户的画风创新过程，从而奠定了自己的艺术发展方向。郑板桥曾说：“花卉翎羽虫鱼皆妙绝，尤工兰竹，然燮画兰竹，绝不与之同道；复堂喜日：是能自立门户者。”观察图6、图7、图8、图9作品我们发现，1.左发式出边章法是李觯独立画风特色之一，画面构成饱满，物状以直带曲，形成纵横抱团交错动态，形式走势统一而富有变化。2.用水用笔生动酣畅，水墨层次清晰，主题突出，画风清新，调子统一，自然优雅的艺术效果是李解独立画风特色之二。3.通过画面呈现出顶天立地，勃勃向上，不屈不饶的拟人化人格精神，而彰显个人独立品自高的鲜明艺术特征，是李解独立画风特色之三。因而，二变画风后的李解，进入了一个淋漓酣畅的泼写天趣，流溢率真的平民情怀。有霸悍之气，落笔劲健，纵横驰骋，不拘绳墨，画风自立，彰显自高艺境。

如图6《苍松幽兰》构图以松石为骨架，由右向左并向上至松树破画面后，再由松枝曲折向左下延向傲首湖石，并继续贯穿于内有傲骨而无傲气的左发式灵动端庄之兰，造成气韵生动，传神写照之美感。不同事物之间的空间处理恰到好处，通过画笔描绘出了刚中带柔的独立品格特色，这些特色在其《五松图》中可以更加清晰地看到。

图9《五松图》是李鱓自壮年到暮年反复创作的题材，目前已发现的就有12幅，年代跨度从雍正十三年（1735年）到乾隆二十年（1755年）不等，都是应人之请为祝寿而作。《五松图》章法、造型和笔墨画亦各具特色。首先，章法上构图饱满，打破院体工整端庄之章法，松树直、斜、曲、横，穿插有致，天骨开张的奇效，松树的参差低昂，向背招应，浓淡聚散都极经意。造成了疏密、节奏、点线、曲直、动势等形式和抽象之美，与西方的现代构成风格不谋而合；加上左上角长篇款书题诗，穿插错落，变书画互补为诗书画三者的相生互动，凸显松的高度，大大增加了畫面气势，形成画面统一而又富有韵律，诗的内容又点明了画的主题。这正如图2章法之妙，是其“自立门庭”不可缺少的重要组成部分。二是在用笔上，他善于借笔势而造化于腕，用笔道劲沉着，不失自然，尽在章法物象之中。这得益于借鉴了明代宫廷花鸟画家林良稳健沉着、干净利落、线条准确、恰到好处的运笔技法。当时画院的画家墨守成规，小心供职，在传统的旧法上，均未见有新的突破。而“锦衣卫镇抚”林良和“锦衣卫指挥”吕纪，能兼工带写，形成自己的独特面目，对后世影响较大，《五松图》这幅画的技法从他们这里可找到根源。三是在用水墨上，焦枯浓淡，干湿交互，粗笔放纵，细笔入微，以黑衬灰，以水统筹，变化自如。四是在造型造势上，采用巨大尺幅，声势浩荡有利凸现主题；画中三棵松直杆为主形态进行造型，向右上倾斜聚会，两棵曲杆盘绕，向左回转，相互交成三个女字形，形成主次、静动和曲直对比，刚正中不失委婉，造成生机勃勃之气势，视觉节奏合理舒坦，抱团向上凸现主题和艺境。五是此图与晚年所谓荒率颓唐判然有别，是画家人到中年而不得志，内心渴求勃发进取的一种自然情趣和清高自娱的独立反叛精神的表露。

李鱓在《五松图》中以借物寓意的拟人化艺术手法，表现赞其刚正不阿、不畏强暴的风范，寄望于社会中品格高尚的人们，从中寄托和表达自己的政治思想、人生理想和艺术追求，从而得到美术史家的重视。

四、成就卓越添光辉

从上面的图像赏评来看，李鱓“三变画风”所呈现的艺术成就主要体现在以下三方面：

第一，他的写意花鸟画题材表现领域的拓展，使中国写意花鸟画的定义得到進一步的延伸。从大自然中的花草树木鸟类，到日常生活的各种用具，乃至农家食用之物，如鱼、桑、蚕之类，题材广泛多样、内容丰富，此堪称扬州八怪之最，为写意花鸟画的创新开拓了空间，为其持续发展与繁荣提供了可能，为中国美术史的谱写增添了光辉。

第二，他的写意花鸟画表现技巧的突破，在于学习石涛破笔画法，而又能发现以水泼墨画法。彰显写意画的酣畅淋漓，笔墨奔放的艺术效果，富有动感和情感，充分表达了作者的创作激情、创作思想和艺术境界。因而，我们认为他的艺术高度因泼水泼墨法而确立，也使中国写意画法走向极致。我认为：写意技法无线意不中国，无墨色不高雅，无水韵不写意，三者合一为上，正是当今国画人难以逾越和理解的写意大法和写意高度。李觯对水的发现，进一步提高了写意画的技术难度，树起了写意花鸟画技法新高峰，完善了写意画的美学境界。

第三，他的写意画技法与理论独创的提出，是由青年时代的工细严谨、色彩艳丽，到中年转破笔写意、泼水墨融，再到老年纯真自然、玩娱老笨的“三变画风”所得。他以一生绘画实践，不断体验，有画有论，有感而发，自觉性地提出“水为笔墨之介绍”“绘画格调以画为娱则高”等写意技法与评价标准，以及“自立门户”的创新精神，发展丰富了写意画美学理论。为彰显扬州八怪精神，文入画内涵的拓延，提高写意花鸟画的地位作出了贡献。

五、小结

李鱓的三变绘画图像走势，代表其身处时代的呼唤发展所求。李觯的绘画题材越发多种多样，可见对生活的热爱向往和艺术创新精神。他的绘画从表物走向表意到表真，是借技法以水为媒，泼水自如，纵横挥洒，体现出审美造型和笔墨创新的驾驭能力，进一步表达了他刚正孤傲、人文意趣和返璞归真的品格。从此，成为用水第一人而独立门户，使文入画写意技法达到一个新高峰，成为扬州八怪之干将，为彰显人文艺术思想起到积极的促进作用，为中国写意花鸟发展产生巨大影响。

图论在初中数学教学中的应用 第4篇

一、图论思想在初中数学中应用的必要性

图论作为重要的数学思想方法,在初中教学中有着广泛的应用领域,从图论的思想体系来看,图论具有以下重要特征:

1.图论的简约性特征。

图论简约性特征主要体现在,“有向图”的思想,将数学问题转化为“有向图”进行思考,从而使问题大大简化。

比如,苏科版初中数学课本中有例:“小明的爸爸存入3年的教育储蓄8500元(3年期教育储蓄的年利率为3.96%,免缴利息税)到期后本息和(本金与利息的和)自动转存3年期的教育储蓄,像这样,至少要转储几次才能使本息和超过10000元。”

教材简洁地处理这个问题,使用了图论的数学思想,给出了简洁的数学模型,使学生很快发现数量之间的关系,得出解决问题的办法。

在这个例题中,笔者将教育储蓄的8500元建立了第一个“结点”,8500元3年的本息额作为第二个“结点”,10000元作为第三个“结点”,并用有向线建立一个连接,构成一个“图”。在这个“图”中,让学生清楚地理解数据前进的方向,让学生很好地感受到图论的价值。

2.图论加“权”性特征。

图论在建立有向图的同时,对每一条边都赋予了“权”,这个“权”可取为一个正数值,用来表示距离、流量、费用等等,组成加权图,用来研究系统特性。加“权”的数学思想更容易让学生理解数量之间的关系。

比如:函数,为描述这个函数的特征,我引入了图论“权”的数学思想,在建立有向连接的同时,在每个连接上,赋予了“权”,使学生很快理解了函数的对应特点。

3.图论的同构特征。

同构性思想,在初中数学中应用非常广泛,同构的概念就是一种“相同”的意思,对给定两个一般图G=(V,E)和G′=(E′,V′),如果它们的顶点集之间存在一一对应,θ =V→V′使得:对V中任意一对顶点x和y,G中连接x和y的边的个数,与G′中连接θ(x)和θ(y)的边相同,则称G和G′是同构的。

比如初中数学中方程的求解,给出了下面例题:

在这个问题中就利用同构的数学思想,形成解方程的两种方法互相印正,使学生很快掌握解方程的方法。

再比如有一道竞赛题:北京准备建一批公交站,要求从其中一个站点上车,只间隔一站就可以到达目的地下车,每个站最多与其他3个站点连接,这样的公交站至多建多少个,并给出设计方案。

4.图论的“树”的思想特征。

在图论中给出了“树”的思想,“树”是这样一个连通图,去掉其任意一边后就不连通了,因此“树”是一个连通图,其每一个边都是桥,即每条边对图的连通性都是必不可少的。这样的连通图就是一个最短的“链”。

比如有这样一个问题,有一个数25,将各位数字的平方求和得到29,我们称为一次“组合”。再将29各位数字的平方求和得到85称为第二次组合。那么至少经过多少次组合可以得到58,你发现了什么规律?

为引导这个问题,我建立了这样一个模型。

在这个模型中形成的“树”很好地解决了学生的疑问。

作为一个数学教师就是要在学生的“数学大厦”中建立一个“连通图”,而且要明白建立连通图所需要的“树”。同样,我们在设置问题时,首先就要建立解决问题的树,这样才会有效地提高教学质量。

5.图论的趣味性特征。

图论的发展过程就是解决问题的过程,而早期的图论问题都充满着趣味性,比如著名的“七桥问题”“四色问题”。这些问题很容易上手,却又趣味无穷,很适合开发学生的思维能力、构图能力和动手能力。

二、图论思想在初中数学中应用的渗透性

在初中教学中渗透图论的数学思想必须要注意下列几个方面:

首先,吃透图论的思想精髓,并将其转化到初中的数学知识体系中去,成为教师和学生的思想方法。

图论的数学思想主要指:“数形结合”的思想;“数学模型”的思想;简约性特征、加“权”性特征、同构性特征、“树”的思想特征和趣味性特征。只有深入地把握图论的这些思想特点,才能将问题巧妙地引入到初中教学中去,在深入浅出中展现图论的思想精髓。

第二,结合初中数学教学中已经出现的图论思想教学案例,深入挖掘,拓展应用的范围,让学生在应用中体会图论数学思想的优越性。

第三,图论的引入要和学生已有的水平相一致,不要注重图论的理论研究,引入图论的问题不能超出学生已有的知识水平。要明白我们在初中阶段不是去研究图论理论,而是让学生感受图论的数学思想,成为学生解决问题自然而然的思想工具。

第四,引入图论问题要和生活实际相联系,不要以介绍图论的数学名词为主线,而是以图论的数学思想解决数学问题为主线。

第五,熟悉图论的发展历史,把握图论的经典问题,在游戏中、玩味中,感受图论的数学思想。

第六,用图论的数学思想指导我们的数学教学思路。

深入研究教材,把握初中教材中知识体系的每一点,在每个点上要建立合理的数学模型,构建有向性连通图,形成完整的树,在每一个边上加“权”,这个“权”就是方法。同时要求,在教学实践中创造性地形成适合学生实际的同构,创新教学方法,完成自己的初中数学教学体系的图论。

图论中数学归纳法的应用 第5篇

关键词：图论,数学归纳法,应用

0 引言

在数学学习过程中, 尤其在证明与自然数相关的命题中, 大多数情况下都可以采用数学归纳方法进行证明。但是对于数学归纳方法的运用技巧和理论基础以及运用情况等, 学生可能了解不是很多, 特别在证明图论学科中的命题时, 学生更是不知道该如何着手进行解题。所以, 唯有掌握好数学归纳法的原理和运用技巧, 才能正确解决图论证明中的一些复杂问题。

1 反归纳法的实际运用

假设这个命题T与自然数有关, 假如命题T可以成立若干个自然数, 如果n = k是正确的, 假设根据命题T, 我们可以推出n = k - 1。

则命题T确实可以成立n个自然数, 对全部自然数都适用。

例: 如果n阶图G可以作为完整的二叉树, 那么G可以有n - 1 个边的连通图形。

论证: 在归纳顶点n时, 如果在n = 1 或者n = 2 时, 这个命题是正确的。

假如成立顶点n命题, 则n = 1 个顶点图形G应该分为两种不同情况进行研究: 假如在n阶图中G所移除长度为1 的叶端点, 那么G有可能转换成G1和G2两个分离图。如果在G1总共有n - 1 个顶点图形, 那么边数总共为p, 在这样的情况下, G2也只能是只包括1 个顶点的图, 因此p = n - 2; 假如在n阶图中, 在G中所移除并不是一个度值为1 的一个叶端点, 那么G有可能转换成G1分离图, G2分离图, G3分离图。如果用p1代表G1的边数, n1代表G1的顶点数, 那么p2代表G2的边数, n2代表G2的顶点数。则G3顶点数值为1, 总结归纳得知: n1, n2< n - 1, 有p1= n1- 1, p2= n2- 1, 由于p1+ p2+ 2 = n - 1, 从而n1+ n2= n - 1, 如果G1, 与G2是相互连通的, 那么G1, 与G2有一条边是相互连通的。在G1与G2相互连通转变成G图时, 这时候G包括着n - 1 个顶点, 其边长值为p1+ p2+ 1, 如果p1= n1- 1, p2= n2- 1, 那么p1+ p2+ 1 = n1+ n2- 1 = n - 2; 也就是G图是n - 1 个顶点, 则边数为n - 2。

2 边数q的具体证明过程

在任何一种类型的连通平面图G中, 都可以应用欧拉公式, 共有p - q + r = 2, 其中平面图用r代表, 面数用G代表。

论证: 归纳q边数q, 假设q = 0 时, 由于G是相互连通的, 因此G是平凡图, 显然结论是正确的。假设q = k ( k≥1) , 如果q = k + 1 时, 那么对G进行如下几点猜测: 如果G是树, 那么G不是平凡的, 所以在G中至少包括两片树叶, 假设v为树叶, 其G' = G - v, 则G'还是连通图, 并且G'的边数m' = m + 1 = k, 在进行归纳和总结中可以得知: n' - m' + r' = 2, ( n'代表G'的顶点数, m'代表G'的边数, r'代表G'面数) 则n' = n - 1, r' = r可得知n - m + r = ( n' + 1) - ( m' + 1 ) + r' = n' - m' + r' = 2; 如果G并不是树, 那么G中含圈, 假设e在G中某一个圈子上, 设G' = G- e, 则G'依然是相互连通的, 并且m' = m - 1 = k, 在假设之后, n' - m' + r' = 2, 而n' = n, r' = r - 1, 则n - m + r = n' - ( m' + 1 ) + ( r' + 1) = n' - m' + r' = 2 。

讲解: 图的边数和顶点作为图的两个基本要素, 在图论中, 很多命题都与图形的边数有很大关系。一些需要证明的命题, 针对于其边数q展开归纳和总结, 在证明时就可以达到目的。在例题之中, 命题想要证明其等式p - q + r = 2, 在这其中共有3个自然数, 对边数q进行证明和归纳可达到目的。在这种类型的图论题中, 只需要掌握图的边数和顶点数, 再利用归纳法进行求解, 便可轻松求解。

3 采用第二数学归纳法的证明过程

在第二数学归纳法中, 所涉及的原理是假设与自然数n相关的命题, 假如: 设n = 1 时, 成立此命题; 如果n≤k时, 成立此命题, 那么n = k + 1 时, 此命题也成立, 则命题对所有自然数n都可以成立。

假设: 如果G是树, 那么 ε = v - 1 ( v代表图G的顶点数, ε代表图G的边数) 。

论证:如果v采用归纳法。在v=1时, GK1并且ε=0=v-1。

假如定理对v个顶点的全部树都可成立, 并且假设G中包括v≥2个顶点的树。假设uv∈E, 由于uv是G中唯一一条 (u, v) 路, 因此G-uv不可能包括 (u, v) 路。因而G-uv并不连通, 并且s (G-uv) =20G-uv的分支G1与G2没有圈子, 并且是相互连通的, 所以是树, 且G1与G2的顶点数都是小于v。

所以假设命题 ε ( Gi) - 1 = v ( Gi) - 1, 对i = 1, 2 是成立的, 因此 ε ( G) = ε ( G1) + ε ( G2) +1 = v ( G1) + v ( G2) -1 = v ( G) -1。

4 顶点数p归纳的证明过程

假设: 如果p阶图G是树, 那么G一定有p -1 条边连通图。

论证:总结归纳顶点p进行证明, 如果p=1, 或者p=2时, 明显此命题一定成立。假如这个命题对少于其p顶点的全部树都是成立的。因为在树G之中两个顶点间的道路是特定的, 移除在G中的一条边, 都可以使其变成为两个分支G1、G2的分离图。假设G1的边数用q1代表, 顶点数用p1代表, G2的边数用q2代表, 顶点数用p2代表, 采用归纳法进行假设, 则q1=p1-1, q2=p2-1, 又因为p1+p2=p, 所以q=q1+q2+1= (p1-1) + (p2-1) +1=p1+p2-1=p-1。

讲解: 在图论中, 大多数命题都是与顶点有联系的, 其需要证明的命题, 我们可以根据顶点数p加以总结和归纳, 更能快速达到目的。

5 跳跃归纳法的证明

如果命题T对1, 2, …, l所有自然数都是正确的, 假设命题T对k这个自然数正确, 那么命题T对自然数k + l正确, 则推出命题T对所有存在的自然数都正确。

定理1: 对整数k, l≥1, r ( k, l) ≤ (kk-+1l - 2)

证明对k+l展开归纳。由于k (1, l) =r (k, 1) =1与r (k, 2) =k, 因此k+l≤5时, 此定理正确。假设m是正整数, n也是正整数, 并假设定理对全部符合5≤k+l<m=n的正整数k和l成立, 那么根据定理:对随意两个整数k≥2与l≥2, r (k, l) ≤r (k, l-1) +r (k-1, l) 假设归纳法, 则r (m, n) ≤r (m, n-1) +r (m-1, n) ≤ (m+n-3m-1) + (m=n-1m-2) = (m=n-2m-1) , 所以定理对任意正整数k与l是适用的。

6 结语

从上述各类型的论证命题中, 我们可以看出运用数学归纳法论证与图论相关的各种命题, 可以使证明过程简单化, 让学习者容易理解和明白, 同时推理过程也更加清晰和简单, 既按照推理的严谨性要求进行, 也遵循推理的科学性进行。所以, 在学习图论的过程中, 灵活引用数学归纳法可以解决很多问题, 使问题简单化。

参考文献

[1]达瓦, 边巴扎西.反证法及其在图论中的应用[J].中国电力教育, 2007 (S4) .

图论在电网建设中的应用 第6篇

改革开放三十年以来, 我国经济逐步从过去“高投入、高能耗、高污染”的粗放型经济发展模式逐步向以资源节约和提高效率为主的新的经济模式转变。这一转变的根本原因在于社会经济中的资源相对于人们无限的需求而言是有限的, 人们总是面临着资源稀缺性与人们需求无限性的矛盾问题。这就需要我们要积极地寻求如何最优化利用资源以部分缓解资源稀缺性问题。从针对生活和生产中用电电网铺设的随意性和浪费现象, 利用图论的相关理论, 在不涉及安全性的前提下, 给出了一种较好的系统的安排用电电网的最优铺设方案。

2 图论中的相关理论

图论是运筹学的一个重要分支, 在现代生活中有着广泛的应用。

所谓图, 直观地讲就是在平面上n个点, 把其中的一些点对用曲线或直线连接起来, 不考虑点的位置与连线曲直长短, 这样形成的一个关系结构就是一个图。通常图G是一个偶对 (V, E) , 其中是非空有限集, 其元素称为顶点, E中的元素称为边。是从顶点vi连接vj的边, vi为该边的始点, 称vj为该边的终点。图G的一条路是指一个有限的非空顶点不同的点边交错序列, 称m为路P的长。如果vo=vm, 即起点和终点相同, 则称为圈。对于图

G (V, E) 的每条边eij= (vi, vj) , 赋以一个实数wij, 则称wij为边eij= (vi, vj) 的权, G连同边上的权称为赋权图。如果G' (V', E') 是一个图, 并且, 则称G'是G的子图。如果图G的任意两个点之间均有路相连, 则称G是一个连通图。若图G是连通的, 且不包含有圈, 则称该图G为树。若G'是包含G的全部顶点的子图, 且G又是树, 则称G'是G生成树。

定理1设G是具有n个顶点的连通图, G是树的充分必要条件是G有n-1条边。

定理2如果图G是有限且连通的, 则在G中必存在生成树。

3 电网铺设问题的解决

在电网的铺设中, 不妨假设该电网中有n个用户, 我们将每个用户用一个点表示, 则得;若用户和用户之间有线路相连则我们将这两点连上一条边, 边集合即为。这样就利用点和边将用电网络抽象成图论当中的图, 我们将其记为G (V, E) 。对于图G (V, E) 的每条边的权值wij, 我们用这两点间所要铺设线路的实际长度来表示。这样, 要研究电网的最优铺设问题, 我们只需要在抽象成的赋权图G (V, E) 上研究即可。

首先, 我们确保该电网中的每个用户的用电需要, 只需图上任意两个点间皆有路相连即可。这样, 只要图G是一个连通图即可满足要求。

其次, 任意两个点之间的边最多只有一条。因为如果两点间的边不止一条, 即两个用户之间的线路不止一条, 则我们选取线路短的一条即可。因此, 图G中没有重边。

再次, 图G中应该不含有圈。因为将圈中任一条边去掉后, 图G仍然保持连通, 因此, 将该圈中去掉一条边之后, 相当于是保持了用户的用电需要且又节省了资源。

最后, 图G本来是任意两个点之间都有边相连的完全图, 要满足我们前三个条件, 则图G变成了一个连通的没有重边和圈的简单图, 实际是一个树图, 是图G的一个生成树。

通过以上讨论, 我们可以得出这样一个结论:对于实际用电电网所抽象出来的图G而言是一个完全图, 本着最优化原则最终所要求的最优的铺设方案即为求图G的最小权值的生成树。

对于最小权值的生成树问题, 我们有如下的非常方便的算法:

step1:将图G的边按照其权值从小到大排列

step2:若, 停止, 此时即为所求;否则, 转向step3;

当该算法不能继续执行时停止, 此时所得的边构成的图即为图G的最小权值生成树。以上算法有时也称为Greedy算法, 即贪心算法。

我们以一个具体例子为例加以说明。

有1, 2, 3, 4, 5五个城市, 假如要在这五个城市之间建立电网, 这五个城市彼此之间建立线路的长度 (百公里) 已知, 抽象为赋权图如图1所示。问如何安排架设线路可以使得整个工程所用线路的长度最短。

计算的迭代过程如下 (见图2)

通过上面的过程, 我们很容易求得整个电网所用线路总长为1+2+2+2=7 (百公里) , 当然, 最优方案可能不唯一, 但最优值确实唯一的。

4 相关问题的解决

对于上面的电网铺设问题, 我们是从节约资源角度出发, 寻求耗费资源最少的铺设方案。当然, 对于边上权值的不同意义, 我们也可以用来求解最少费用的铺设方案, 此时, 只需要将边上的权值用来表示在两个不同用户间架设线路的费用即可。

一些类似的问题, 例如要修建一个连接若干城市的通讯网, 已知城市vi与城市vj之间通讯线路所需费用为cij, 问应在哪些城市之间架设线路, 既能使所有城市之间都能连通, 又要求架设的总费用最小等等这一类问题都可以转化为求解图的最小生成树, 对于我们的目前的现代化建设有着极大的借鉴意义。

参考文献

[1]龚六堂.动态经济学方法[M].北京:北京大学出版社, 2002.

[2]胡运权.运筹学基础及应用[M].北京:高等教育出版社, 2003.

图论教学 第7篇

一、景区游览线路研究现状

国外对于旅游线路的研究较多且较为成熟, 如在旅游线路设计模式研究中的Campbell模式、多目的地旅游模式、Lundgren旅行模式等。然而, 发达国家的研究是基于其优良的交通设施条件以及其公民较为成熟的旅游态度, 因此, 我们仅能将这些研究作为借鉴, 不能搬用。国内现有的文献中, 关于游览线路的研究可以分为两类:一类是从线路规划的角度考虑, 主要包括游步道的修建、游览标志系统设计等等, 主体是景区;另一类是以旅行社为主体来研究对游客游览线路的安排和管理问题, 其中包括对游览节点的选择和组合、游览顺序的安排、游览线路设计等, 例如, 1999年管宁生的关于旅游设计若干问题的研究、2005年马晓龙的基于游客行为的旅游线路组织研究等。两类研究有一个共同点, 就是定性的研究较多, 定量的很少, 即使是定量的文章也大多是对数据的统计分析, 没有用定量的模型来关注其内在的关系。图论在线路设计中应用的研究很少, 尽管很多文献中都提及图论在旅游中应用的可行性, 如刘啸等所做的旅游运筹学开设的可行性研究, 但很少有更深入的研究。唐力帆在1998年提出图论在旅游线路设计中的应用, 是较早的这方面的研究, 他主要以旅游线路设计原则为背景介绍了图论在游览线路设计中在缩短时间、节约费用上的应用, 构建了简单的着色模型;2004年, 吴凯定性解释了图论在旅行社设计旅游线路中的作用;2008年, 蒋满元从旅行社的角度出发研究旅游线路优化设置问题, 构建了具体的图论模型。这些文献着重介绍了线路设计优化, 少有提及这种优化在提升景区线路服务上的重要性。总的来说, 线路优化服务是一个新的研究角度, 而图论方法是一个较新的研究工具, 两者的结合带来新的研究方法和研究意义。

本文将在现有文献的基础上, 借鉴相关模型讨论图论视角下如何更好地优化景区线路以及它与景区服务提升的关系。

二、图论的基本原理及其与游览线路网络的关系

图论是近几十年来运筹学中发展最迅速、也十分活跃的一个分支, 由于对事物描述具有直观性, 广泛用于信息论、控制论、现代经济管理等方面, 尤其是在计算机科学领域的应用, 使得图论解法更加便捷、直观。图论中所研究的图实际上是从实际问题中抽象出来的关系。

图1中的顶点是景区内的旅游节点;节点之间用游览线路线性连接;边上的权值视做两点之间的距离或者游览时间;S是入口, T是出口。这样的抽象使得景区游览线路网络更为直观, 然后我们借用对图的分析来研究游览路径、游览时间等旅游线路优化问题。

三、景区游览线路优化

在游览过程中, 时间、距离是游客比较重视的因素。游客往往需要在最短的时间内游览最多的景点, 体力不好的游客更希望不要走“冤枉路”。这就需要景区在游览线路设计上对游客有很好的指导, 告诉顾客怎样能游遍所有景点而不走冤枉路, 哪条路径是两个景点间的最短路径, 怎样走才能更节省时间等。同时, 为了使游览秩序更有条理的同时又能使尽量接待最多的游客, 景区又不得不考虑最大流量问题。总之, 在景区的游客游览线路安排中, 游览遍历、最短路径、最大量是最为重要和常见的问题。

游览线路的安排涉及到心理、美学、文化等多方面因素, 本文弱化这些因素, 仅从运筹学的角度, 着重对时间及游览路径进行优化, 给出客观的线路, 以供参考。对于节点较为简单的网络来说, 用枚举法便可直观判断, 而对于节点较为复杂的网络, 人为的安排缺乏科学性, 以数据和程序支撑的计算更为合理。当然, 作为一个工具, 图论并不能解决所有问题, 已有的较为成熟的方法有旅行商问题、网络流问题, 文章也就从这些已有的算法入手, 来分析旅游线路设计中用得到的模型。

(一) 景区遍历及最短旅游路径

很多游客都有遍历景区内所有景点的要求。他们希望能够在最短时间内或是走最少的路而游览所有节点, 该模型描述为:游览者要从进口处游览景区内的n个景点, 最终仍回到出口处, 每个景点只游览一次, 不应重复, 同时希望所走距离最短。此目标有三个约束条件, 第一个是每一个景点都将游览到, 第二个是游客应从每个景点离开而不得滞留, 第三个是出进口外任意景点都不重游。而有着最短路径要求的线路设计着重考虑的如何寻求景点之间的最短旅游路径。在大的方面来讲, 可以寻取旅游景区组成的旅游网络之间的最短路径, 从某个景区来说, 也可以看做不同景点之间的最短路径选择。无明确目标的游客也可以对自己的游览路径和时间都有明确的估计, 此模型最终得到完整的遍历方法以及任何两个节点之间的最短路径。

在一些较大的景区内, 若靠旅游者漫无目的游览的话, 总会体力不支, 方向感不好的游客还会重复游览, 造成时间和体力上的浪费。景区若能够明确指出景点之间的最短路, 游览目标明确的游客便可以舍弃不喜欢的景点, 直达目的地。景区管理者也可以利用此模型建立游览遍历指示系统, 引导游客充分游览所有景点;旅行社也可用来做游览线路设计;景区规划者则可将此模型用于游步道的规划, 从而获取最小成本。

(二) 最大流量问题

景区的承载能力除了与景区本身资源有关以外, 与游客流量安排也有着重要关系。合理指导游客游览路径, 统筹安排游客可以使得景区在满足本身资源限制的条件下可以接待最大量的游客。以图1景区流量图为例。

在该图中有ABCDEF等6个游览节点, 每两个节点之间的数字是该条线路容纳量及节点接待量限制下的最大游客通过数目 (以百人为单位) , S是入口, T是出口。我们知道到达每一个节点的游客并不是线路容纳量的总和, 因为每一条线路都必须受其之前线路容纳量的限制。我们最终得出这个网络系统最大可达流量为15, 流量分配具体为:SCEFT3;SBEFT4;SBDFT3;SADFT5。对于复杂的景区线路网络, 我们很难凭直觉判断出应当如何分配流量才能使景区接待人数最多, 而利用图论中的有关算法就可以很容易解决这个问题。

最大流问题可以帮助景区科学估算景区的最大容纳能力, 景区也可以对游客进行合理的引导来达到这个最大量, 这个过程需要景区与游客进行很好的沟通, 也需要旅行社提供相应帮助。

四、模型在景区服务提升中的应用

景区可从以下方面来考虑以上模型的应用: (1) 模型可帮助景区在每个游览节点容纳量的限制下科学把握景区总体容量。 (2) 景区可设置标志牌等信息引导设施给游客提供更好的游览线路引导服务, 例如, 告诉顾客如何游览可以在最短路径内遍历所有景点, 如何游览可以最节省时间等。 (3) 景区可与游客进行有效沟通来避免出现游览线路冷热不均的情况, 这样一方面可以使游客得到个性化的服务, 一方面又可以满足景区接待量最大化的目标。 (4) 景区也可与旅行社合作共同优化景区游览路径, 这样旅行社可以更有秩序的安排游客, 景区可以更有效率的分配游客流量, 而游客也可以因此而获得一个更为轻松有序的旅程。

结语

本文主要探讨了景区内游览线路安排中常见的三种问题:游览遍历、最短路、最大流量。而这三个问题恰恰可以在抽象成图的旅游网络中进行优化, 将图论应用于此是一个非常得体而实用的工具, 数据和模型的支撑使得线路的制定避免了直观性和盲目性, 更加科学化、合理化。然而, 研究中只注重运筹学角度的考虑, 弱化了景区文化、游客心理、游览美学等其他影响因素, 使得本研究会有一定的片面性。除此之外, 本文只着眼于总体线路设计, 没有涉及到旅游过程中经常遇到的卡口瓶颈等一些实际问题, 深感遗憾的同时也希望做更多深入研究后再行解决。

本文的研究适用于各种游览型景区, 也适用于大型主题公园及游乐型景区, 可作为景区安排游客、提高服务质量和管理质量之用, 也可供旅行社进行游客组队参考。由于一个景区的线路网络在某种意义上可以看作是一个大的旅游网络的缩影, 因此本文的研究也可继续扩展为大的旅游线路设计研究。

参考文献

[1]周存宇, 钟振全.我国旅游线路设计研究概述[J].科技信息, 2008, (20) .

[2]蒋满元.旅行社的旅游线路优化设置问题探讨[J].技术经济与管理研究, 2008, (4) .

[3]唐力帆.图论在旅游线路及游览线路设计中的应用[J].水运管理, 1998, (10) .

[4]吴凯.旅游线路设计与优化中的运筹学问题[J].旅游科学, 2004, (3) .

[5]刘啸, 文谨, 刘亚玲.旅游运筹学开设的可行性研究[J].江西农业大学学报, 2007, (6) .

[6]邓成梁.运筹学的原理和方法 (第二版) [M].武汉:华中科技大学出版社, 2002.

[7]韩中庚.数学建模方法及其应用[M].北京:高等教育出版社, 2005.

基于图论的图像分割技术探讨 第8篇

1 图像分割的传统方法归纳

1)边缘检测分割法

边缘检测是最基本的图像分割技术,顾名思义,即通过智能测算,来确定图像的边缘,并进行分割。首先识别出图像中的边缘点,然后以闭合曲线连结锚点,选出分割区域。

从色彩学的基本原理上看,图像的边缘,通常是灰度、色相或纹理等特性发生骤变的地方。因此,对于图像边缘的识别,主要是依赖算法对上述特征的界定。边缘检测算法种类繁多,且各有优缺点。其中,智能识别逻辑含义简单,边缘灰度变化明显,且噪点不多的简单图像。而对一些题材超现实,或是色彩和明度变化微妙,又或者噪点过多的图像,执行这一简单的算法就无法正确地识别边缘。即使反复操作,效果也不好:一来噪点过多,与图像本身的边缘区分不开,二来降低噪点又必然折损原图的结构纹理,更容易误导边缘识别。

2)阈值分割法

阈值分割则也是传统的分割技术之一,分割原理很容易理解,即利用图像中目标区域与背景区域之间的最大灰度差来识别不同物体之间的边界,此时便将相同物体上灰度的相对均匀作为分割依据。阈值分割通过一个或几个阈值将图像划分出几个不同区域。

阈值图像分割法的基本原理是根据直方图的像素分布来指定恰当的阈值,该方法也有局限性:只能对动态范围广,即像素分布均匀的图像进行精确分割。如果图像的直方图向左或向右倾斜过多(即像素集中分布在高亮部或暗部),实际区域划分就会出现严重的误差。

3)聚类分析分割法

聚类分析法的诞生,是图形分割由单一算法走向多元统计的标志。所谓的聚类分析,指的是根据图形数据的内部结构来划分类别,从而实现更智能化,成功率更高的边缘识别。

聚类分析有两种,一种是硬聚类,还有一种是模糊聚类分析法,一般前者比较常用,其基本工作原理是在非同一类别的函数中,将隶属度取值为0或1,换言之单个样本只可属于单一类别。

模糊聚类则是在一种无监督的聚类方法,它是在样本点的正态分布区间中根据隶属度取值,如此一来,各个样本点对聚类都呈现出一种隶属关系。模糊聚类法是图像边缘不确定性的典型表征。因此在运用上硬聚类分割法更为繁琐,目前多用于医学图像处理中。

而可能性聚类则不同于上述方法,它不仅要顾及到样本与聚类中心的隶属关系,还要兼顾样本对分类结果的影响。传统聚类算法不能覆盖到图像的空间性,所以对局部强噪点和灰度变化大的图形解读能力较差。为了优化模糊聚类算法在图像分割中的效果,来自欧美顶尖实验室的技术人员优先提出了迭代优化法,该算法可以从三维视角识别图像的空间信息,算得上是最前沿的新型算法。

4)活动轮廓图像分割法

活动轮廓分割法最初诞生于上世纪九十年代初,主要是指在图像的阈值曲线或者曲面几何特性和数据的共同作用下,以最小化能量函数的形式向边界运动。这一方法从提出至今,已经过二十余年时间,活动轮廓建模理念已经在边缘检测、图像分割领域取得了可喜的实验结果,通过技术人员在算法上的优化与改进,最终使得圆滑轮廓曲线最大限度地切合目标物体的凹陷边缘,因此在很大程度上解决了参数活动轮廓方法易于陷入局部能量区域这一技术障碍。

2 基于图论的图像分割法

2.1 以图论为导向的研究方向

基于图论的图像分割技术是近年来图像分割领域中引起广泛关注的研究热点,它的基本思想并不复杂:即通过图像映射转化为无向图,在图像边缘界定锚点,令各个锚点之间边的权重分别对应不同像素之间的不相似度,从而计算出割的容量。截至目前,基于图论的图像分割方法的研究主要集中在以下几个方面:

1)最优切割准则设计原则;2)谱方法分割原则;3)快速算法。

基于图论的分割方法,从本质上讲,是将图像分割问题转化为特征识别问题,即转化为聚类方法。、而最优分割原则是指通过划分两个子图,取内部相似度最大值来作为界定图像边缘的参考。图割算法中割集准则的选取对最终分割结果有直接影响,使用频率较高的割集准则有最小割(Minimum cut)、平均割(Average cut)大小分流割(Max-minimum Cut)等。

2.2 割集选择的基本原理

1)图形最优分割

图论算法在计算机应用技术中扮演着很重要的角色,该方法灵活度很高,可以解决很多问题。遗传算法是解优化问题的有效算法,而并行遗传算法是遗传算法研究中的一个重要方向,受到了研究人员的高度重视。此类方法把图像分割问题与图的最小割(min cut)问题相关联。首先将图像映射为带权无向图G=<V,E>,图中每个节点N∈V对应于图像中的每个像素,每条边∈E都连接一对相邻像素,边的权值意味着相邻像素之间在灰度、色度和纹理方面的非负相似度。而对图像的分割就是对图以某种指标为准进行裁切,被裁切出的每个区域C∈S分别对应了图中一个子图。

因此,分割的最优原则意味着划分后的子图在内部保持最大相似度,而子图之间则保持最小相似度。基于图论的分割方法的根本原理就是移除特定的边,将图划分为若干子图从而实现分割。目前所了解到的基于图论的方法有智能图形分割(Graph Cut)和权函数运算等。

2)权函数运算

权函数一般定义为两个节点之间的相似度,也就是在数据统计中计算出平均数等指标,然后对各个变量值权衡大小,所以顾名思义地被称为“权函数”。在权函数运算中,对于灰度图像,一般用F表示像素的灰度值,X表示像素的空间坐标,Y为灰度高斯函数的标准方差(用于测算出两像素之间的有效距离)。一旦超过这一距离,则认为两像素之间的相似度较大;反之两像素之间的距离越小,则认为相似度越大。

3)图形相似度矩阵

图论分割算法常把最优割集准则转化相似度矩阵以便求解。相似度常用字母W和A表示。相似度矩阵又称亲和力矩阵,运算原理是将原图像中的像素重新排布。在相似度矩阵中,所有相邻像素的相似度都可以通过函数运算得到。将相似度矩阵的每行元素相加,即得到该节点的度,以所有度值为对角元素构成的对角矩阵即为度矩阵,度矩阵常用字母D表示。令低量算符矩阵为L=D-W,则在图论分割算法中低量算符矩阵为最常用的标准矩阵。

3 图论分割方法的应用

1)临床医学图像分割

图论图像分在医学领域可以用于脑心电图,以及脊椎骨核磁共振,即在区域生长和模糊连接度的基础上结合各向异性滤波和边缘检测算子检测边缘,继而从图像中划分出目标选区,为外科手术方案提供参考。同时,此项技术也可以患者肿瘤切片的深度分割,为医学工作者诊断病情,确定治疗方案提供了有效的数据参考。最新的研究方向表明,图像分割技术还有可能被用于重建细胞全息图,为医学人员攻克免疫方面的病症提供了更深入的数据分析,其潜在应用价值不可估量。

2)纹理分割

纹理分割(Texture Segmention)对后续图像的其他算法处理非常重要,对分割算法的掌握对于后续算法,比如目标跟踪,人脸识别等等,都是非常重要的。可将Normalize Cut准则用于图像中的边缘与纹理质地测算识别,即将图像信息分为干涉基元和纹理基元,并将两种信息进行数据合并。同时,Normalize Cut准则还具有较好的兼容度,对于将明度信息与纹理信息数据整合的分割方式也适用。

3)智能图形分割

智能图形分割(Graph cuts)最先由国外的技术人员研发,近年来开始在国内广为流传,因其智能度高,操作易上手,因而受到了广大商业运作机构的追捧,被广泛应用在UI设计,商业摄影后期制作等领域。智能图形分割的基本原理就是将图像分割问题与图的最小割(min cut)准则实行联合运算,使图像在保持较小容差值的情况下,依然可以大刀阔斧地进行轮廓识别,而不会被材质纹理造成的明暗变化所误导。基于这种基本原理,智能图形分割也难免存在局限性,即它只适合逻辑简单清晰地图形。尽管如此,它仍然可以胜任相当多的行业操作终端对于图像分割的需求。即使在操作中偶尔出现识别错误,通过若干次的容差值修改,最终也不难得到一个相对精确的图形分割方案。

4 结论

在前文中,作者首先总结了目前常用的集中图像分割技术,然后对基于图论的图形分割技术做出了详细的分类探讨。对图像分割算法的研究历史至今已有几十年,基于各种理论至今已开发出了千余种分割算法。目前,图像分割方法发展势头良好,正朝着更迅速、更精确、更智能的方向发展,通过研究新理论,引进国外先进技术,这一领域在不久的未来势将取得更大的突破和进展。

参考文献

[1]侯叶.基于图论的图像分割技术研究[D].西安电子科技大学,2011.

[2]罗青青.基于图论的图像分割技术研究[D].南京邮电大学,2014.

[3]贺锦鹏.基于图论的彩色纹理图像分割技术研究[D].哈尔滨工程大学,2011.

[4]郑倩.医学图像分割方法研究及其应用[D].南方医科大学,2014.

[5]董昌灏.基于图论的交互式PCB图像分割技术研究[D].解放军信息工程大学,2013.

基于图论聚类的汛期划分及其应用 第9篇

由于汛期的划分具有模糊性, 某一个时段是否归为某一汛期并不是泾渭分明的, 而是一个隶属程度的问题。图论聚类法基于模糊相似矩阵, 利用图论中“距离”和“树”等概念实现对样本的聚类, 因其操作简单, 聚类效果明显而得到广泛应用[2]。

现有的汛期划分方法有数理统计法、变点分析法、矢量统计法、有序聚类法和系统聚类法等, 这些方法都有其优缺点[3], 究竟何种方法最优, 国内尚且没有定论, 而图论聚类法在汛期划分上的应用几乎仍是空白。本文在介绍图论聚类法后, 试图以洪家渡水库的汛期来水为基础, 并在考虑汛期划分时序性的基础上, 用改进的图论聚类法确定初汛、主汛和后汛并对划分结果进行分析。

1 图论聚类法

经典图论聚类法最早是由Zahn提出来的, 又称作最大 (小) 支撑树聚类算法[4]。图论聚类法要先把需要聚类的数据表示成一个带权的无向图G= (V, E) 的形式, 其中V是图的顶点集, E是图的边集, 图是由顶点以及连接顶点的边所构成的几何图形。运用图论聚类法首先要建立与问题相对应的图, 图的节点与被分析数据的最小单元对应, 图的边与最小处理单元数据之间的相似度 (“距离”) 对应。所以, 每一个最小处理单元数据之间都会有一个“距离”, 这就能保证在处理数据时, 数据的局部特征不会失真。图论聚类法的原理是将样本数据的局域连接特征作为聚类的主要信息源, 因而其主要优点是易于处理局部数据的特征[5]。图论聚类法的主要步骤分为生成模糊相似矩阵、求解最大树、利用阀值进行聚类3个步骤。

1.1 生成模糊相似矩阵

聚类是按照论域X内各元素之间的接近程度, 将彼此接近的元素归为一类[6]。所以用一个[0, 1]间的数dij来表示Xi与Xj间的距离。

在对样本进行分类时, 样品之间的相似程度用“距离”来度量。常用的距离有明考夫斯基 (Minkowski) 距离、兰氏 (Lance和Williams) 距离、马氏 (Mahalanobis) 距离和斜交空间距离等。本文将采用兰氏距离进行计算, 其计算公式如下:

式中:c为一不超过1的正数;n为样品个数;m是需要考虑的因素个数;μk是第k个因素所占的权重, μk∈ (0, 1) 。

将各元素之间的距离合成为一个矩阵R, 该矩阵的第i行第j列表示Xi与Xj间的距离, 矩阵R就是模糊相似矩阵。

1.2 求解最大树

假设G= (V, E) 是一个网络, U是顶点集合V的一个真子集。给定模糊相似矩阵R后, 有多种方法画出对应于R的赋权图的最大树, 常用的方法有Prim法和Kruskal法。本文将采用Prim法进行计算, 其基本步骤如下:

首先从集合V中任取一顶点 (例如取顶点v0) 放入集合U中, 这时U={v0}, TE=NULL;然后在所有一个顶点在集合U里, 另一个顶点在集合V-U里的边中, 找出权值最大的边 (u, v) (u∈U, v∈V-U) , 将边加入TE, 并将顶点v加入集合U;重复上述操作直到U=V为止, 这时TE中有n-1条边, T= (U, TE) 就是G的一棵最大树。

1.3 利用阀值进行聚类

因初始顶点的选取不一样, 所以画出的最大树可能不唯一。但是可以证明, 分类结果是一样的[4]。在已经得到最大树的基础上, 砍去权重小于λ的边而留下权重大于或等于λ的边, 把各联通分支内的元素归为一类。考虑到实际问题的复杂性, 有时需要合并某些类别或调整阀值λ, 使得聚类结果更加合理。

2 实例应用洪家渡水库的汛期划分

2.1 洪家渡水库概况

洪家渡水电站位于贵州西北部黔西、织金2县交界处的乌江干流上, 是乌江梯级水电站中唯一具有多年调节水库的“龙头”水电站。洪家渡径流主要由降水补给, 汛期一般从5月上旬到10月下旬, 最大洪流一般在6月、7月, 枯水期一般从11月初到次年4月末, 最枯流量多出现在3月或4月, 个别年份在5月中旬出现[7]。

2.2 基本资料说明及数据处理

流域的汛期划分主要考虑洪水的时程分布及变化规律, 本文基于洪家渡水库1959-2007年的洪水过程资料 (精确到小时) 来分析。考虑到聚类本身存在一定的随机性和误差, 没必要将汛期划分精确到天, 所以选取最小的划分单位为旬。洪家渡径流主要由降水补给, 汛期一般从5月上旬到10月下旬[7], 所以确定论域为5月上旬到10月下旬 (共18个旬) , 并求得每旬的多年平均洪水流量 (见表1) 。

2.3 洪家渡水库的汛期划分

2.3.1 聚类过程

用聚类方法划分汛期的前提是聚类具有连续性的效果, 一般采用有序聚类方法。如果用基本的图论聚类法则不能体现汛期划分的时序性。本文采用的方法是, 将时序性作为影响“距离”的一个因素, 在计算模糊相似矩阵R时将其考虑进去。这样一来, 影响每两旬之间的“距离”就有多年平均洪水流量和时序性2个因素;模糊相似矩阵R中的每个元素将由下式求得:

式中:μ1是多年平均洪水流量在“距离”计算时的权重;μ2是时序性在“距离”计算时的权重;由于汛期划分时每2旬之间的“距离”具有相对性, 故可取c=1, μ1=1, μ2的取值待调整;xi1和xj1是指第i旬和第j旬的多年平均洪水流量 (见表1) ;pij是指第i旬和第j旬的时序性距离刻度, 其大小由以下方法确定。

引入时序性距离矩阵P, 每2旬之间间隔的时间越长, 时序性距离刻度pij的值就越大, 其范围用0~17间的整数表示, 即:

为保证各因素间单位一致, 需要对时序性这一因素进行“标准化”, 使pij变为一个0到1之间的无量纲量。这里拟定的pij本身无量纲, 为保证其大小在0到1之间, 需要满足μ2∈ (0, 1/17) 。

经过试算, 初取μ2=0.02, 运用式 (2) 计算各旬之间的距离, 得到模糊相似矩阵R (见表2) 。

根据表2模糊相似矩阵R, 利用Matlab编写程序实现Prim算法, 求得一棵最大树 (见图1) 。

对于以上求得的最大树, 取λ=0.85, 砍去权重小于0.85的边而留下权重大于或等于0.85的边, 把各联通分支内的元素归为一类, 可以将整个汛期分为7类:Ⅰ类 (5上, 5中) ;Ⅱ类 (5下, 6上) ;Ⅲ类 (6中) , Ⅳ类 (9中, 9下, 8下) ;Ⅴ类 (10上, 10中, 10下) ;Ⅵ类 (8中, 9上, 8上, 7上, 7中, 6下) ;Ⅶ类 (7下) 。考虑时间的连续性, 调整聚类结果, 定出主讯为{Ⅳ, Ⅵ, Ⅶ}, 即6月下旬至9月下旬。

为了使聚类结果更加合理, 另选取μ2=0.01, μ2=0.005, 划分结果见表3。

2.3.2 聚类结果

由表3的聚类结果可知, 主汛期的终止时间较稳定, 但是起始时间随μ2的变化有些微波动, 结合洪家渡水库历史上主汛期的观测资料, 最终定下洪家渡水库的主汛期为6月中旬至9月下旬。

由聚类结果可知, 除主汛之外, 其他2类时间不具连续性, 考虑到主汛期在时间上居于初汛期和后汛期之间, 所以将5月上旬至6月上旬定为洪家渡水库的初汛期, 10月上旬至10月下旬定为洪家渡水库的后汛期。

2.3.3 结果分析

为评价图论聚类法的统计特征, 本文利用洪家渡水库历史洪水的汛期划分结果, 统计图论聚类法划分出的主讯覆盖历史上主讯的旬数, 并计算其百分比 (见表4) 。

由表4可知, 平均覆盖率达89.12, 说明图论聚类法结果较精确。另外文献[8]基于水库汛期隶属函数, 运用模糊理论最终确定乌江梯级电站的主汛期为6月20日至9月10日, 与本文的结果相似, 在一定程度上证明了图论聚类方法的正确性。

3 结论

(1) 由图论聚类法确定洪家渡水库的主汛期为6月中旬至9月下旬, 初汛期为5月上旬至6月上旬, 后汛期为10月上旬至10月下旬。

(2) 图论聚类法的精度是可控的。本文采用的最小计算单位是旬, 如果将最小计算单位改为天或小时, 利用计算机程序计算, 结果会更加精确。

(3) 阀值λ的取值需要根据实际情况调整, 具有一定的任意性。好在实际中汛期往往有特定的界限, 当λ的取值使得汛期划分不符合基本来水规律或导致结果无法聚类时, 应该考虑重新选择阀值λ。

(4) 在划分汛期时, 最关心的往往是主汛。洪家渡水库汛期的图论划分结果表明, 主汛 (6月中旬至9月中旬) 在时间上恰好是连续的, 这在一定程度上说明了该方法的合理性。但是初汛和后汛被划分为时间上不连续3类, 这主要是所选取的划分汛期的因素单一所致 (只有多年平均洪水流量) , 为提高图论聚类的效果, 可以选取多因素 (如暴雨日数、面均雨量、旬最大3d洪量和年最大洪峰次数等[3]) 进行更深入的研究。

摘要：基于汛期划分的模糊性, 阐述了图论聚类在汛期划分中应用的合理性, 介绍了图论聚类的思想和方法。以洪家渡水库多年平均实测洪水流量为基础, 考虑汛期划分的时序性, 将基本的图论聚类法进行改进, 利用最大树法划分了初汛、主汛和后汛, 其中洪家渡水库的主讯期被确定为6月中旬到9月下旬。

关键词：图论聚类,汛期划分,模糊聚类,洪家渡水库

参考文献

[1]顾圣平, 田富强, 徐得潜.水资源规划及利用, 教材[M].北京:中国水利水电出版社, 2009.

[2]李相镐, 李洪兴, 陈世权, 等.模糊聚类分析及其应用[M].贵州:贵州科技出版社, 1994:77-116.

[3]王宗志, 王银堂, 胡四一, 等.水库控制流域汛期分期的有效聚类分析[J].水科学进展, 2007, 18 (4) :580-585.

[4]钱云涛, 赵荣椿, 谢维信.鲁棒聚类——基于图论和目标函数的方法[J].电子学报, 1998, 26 (2) :91-94.

[5]刘锁兰, 王江涛, 王建国, 等.一种新的基于图论聚类的分割算法[J].计算机科学, 2008, 35 (9) :245-247.

[6]高波, 刘克琳, 王银堂, 等.系统聚类法在水库汛期分期中的应用[J].水利水电技术, 2005, 36 (6) :1-5.

[7]李程.乌江流域径流演变规律分析及径流预报模型研究[D].西安:西安理工大学, 2010.