科学网 › 标签 › 图论

标签: 图论

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

一个UyHiP趣题: murongxixi 2013-11-13 02:51; 一个公司里有n个员工，其中某些员工之间有“ 好友 ”的关系(这是一个对称的关系)。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半(仅当他有偶数个朋友时才会发生这种情况)，则第二天他的决策不变，继续喝自己今天喝的东西。由于$n$个员工一共只能产生$2^n$种不同的早饮组合，因此总有一天大家喝的东西会和过去的某一天一模一样，从而产生循环。证明：循环的长度不超过 $2$ 。用一个图论模型来描述这个问题，每个员工都用图里的一个顶点来表示。所不同的是，尽管这是一个无向图 (朋友关系是对称的)，但在下面的证明中我们仍然使用了有向图的模型。对于两个互为好友的顶点$x$和$y$，我们同时添加从$x$到$y$的有向边，以及从$y$到$x$的有向边。对于每一个有奇数个好友的员工，他的决策都很简单：昨天大多数好友都喝的啥，今天他就喝啥。但是对于有偶数个好友的员工，决策就没有那么容易描述了。妙就妙在这里：我们给所有有偶数个好友的员工添加一个从自己出发指向自己的自环，让他的出度入度也都是奇数。这样一来，当喝两种饮料的好友各占一半时，他自己的决策会打破平局；而当喝两种饮料的好友数量不同(至少相差$2$)时，算上自己喝的也不会改变结果。因此，对于有偶数个好友的员工，决策变得和其他员工也一样了：他所指向的顶点昨天喝什么的更多，他今天就喝什么，不必担心有平局现象发生。如果员工$x$和员工$y$是好朋友，并且第$i$天$x$喝的饮料与第$i+1$天$y$喝的饮料相同，我们就说第$i$天员工$x$ 影响了员工$y$。注意，那些有自环的人要把自己看作自己的朋友，因此自己影响自己也是要算的。那么在第$i$天，图里一共有多少条“ 影响边 ”呢？如果$x$的好友中，第$i+1$天里有$t_{i+1}$个人喝茶，有$c_{i+1}$个人喝咖啡，那么从$x$出发的影响边数量就是$t_{i+1}$或者$c_{i+1}$(取决于第$i$天$x$喝的什么)。遍历所有的$x$求出总和，就是图里总的影响边数量。在第$i+1$天，图里有多少条影响边呢？我们现在换一个方法，从“ 被影响 ”的角度来计算影响边的数量。对于$x$来说，指向他的影响边数目显然是$t_{i+1}$和$c_{i+1}$的较大值，因为按照规则，他在第$i+2$天喝的饮料应该与第$i+1$天多数人喝的一样。遍历所有的$x$求出总和，就是图里总的影响边数量。注意，影响边的数量不可能变少了，因为刚才我们累加的是$t_{i+1}$和$c_{i+1}$之一，但这次我们累加的是$t_{i+1}$和$c_{i+1}$的较大值。但是图里的影响边数量不可能一直在严格增加，因为它不可能超过图里的总边数。因此，总会有一天，图里的影响边总数和前一天相等。而考虑前面的证明过程，这就意味着，对于每个员工$x$来说，昨天从他出发的影响边数量和今天指向他的影响边数量取的$t_{i+1}$和$c_{i+1}$中的同一个数，即昨天他影响的那些人也就是今天影响了他的人。换句话说，昨天他喝的东西和明天他要喝的东西一样，因此，循环长度不超过$2$(这里的证明似乎并不太严谨，但是直觉上没什么问题)。问题的背景是社交网络里的 nonprogressive cascading 模型，可惜笔者对此一窍不通，就不胡言乱语贻笑大方了。; 个人分类: 数学相关|132 次阅读|0 个评论

网络拓扑学与医学: benlion 2013-3-7 19:48; - 东方思维模式（星象图）（洛河图）（经络图）（网络图 - 系统生物学/医学）中国象形文字与西方拼音文字的差异 - 在思维上体现为单元分析与图式关系。更多 - 参见 - http://blog.sciencenet.cn/blog-286952-667908.html 。; 个人分类: 2013|11505 次阅读|4 个评论

《Elements of Algebraic Graphs》英文版=《代数图基础》刘彦佩: ustcpress 2012-12-17 19:14; 丛书名：当代科学技术基础理论与前沿问题研究丛书——中国科学技术大学校友文库（“十二五”国家重点图书出版规划项目）出版日期：2013年1月书号ISBN：978-7-312-03008-6 出版社：中国科学技术大学出版社正文页码：420页（16开）定价：78.00元编辑邮箱： edit@ustc.edu.cn （欢迎来索要目录、样章的PDF）当当网购书链接：暂未上架【内容简介和特色】本书以图的代数表示为起点，着重于多面形、曲面、嵌入和地图等对象 , 用一个统一的理论框架，揭示在更具普遍性的组合乃至代数构形中 , 可通过局部对称性反映全局性质 . 特别是通过多项式型的不变量刻画这些构形在不同拓扑、组合和代数变换下的分类 . 同时 , 也提供这些分类在算法上的实现和复杂性分析 . 虽然本书中的结论多以作者的前期工作为基础发展得到 , 但仍有一定数量的新结果 . 例如 , 关于图在给定亏格曲面上可嵌入性的识别 , 沿四个不同理论思路的判准就是新近得到的 . 在亏格为零的特殊情形下 , 它们中的一个可一举导出 Euler 、 Whitney 、 MacLane 和 Lefschetz 在图的平面性方面沿不同理论路线的结果 . 本书适合纯粹数学、应用数学、系统科学以及计算机科学等方面的大学生及相关教师使用，还可供相关专业研究生和数学研究人员阅读 . 【目录】 Preface to the USTC Alumni's Series Preface Chapter 1 Abstract Graphs 1.1 Graphs and Networks 1.2 Surfaces 1.3 Embeddings 1.4 Abstract Representation 1.5 Notes Chapter 2 Abstract Maps 2.1 Ground Sets 2.2 Basic Permutations 2.3 Conjugate Axiom 2.4 Transitive Axiom 2.5 Included Angles 2.6 Notes Chapter 3 Duality 3.1 Dual Maps 3.2 Deletion of an Edge 3.3 Addition of an Edge 3.4 Basic Transformation 3.5 Notes Chapter 4 Orientability 4.1 Orientation 4.2 Basic Equivalence 4.3 Euler Characteristic 4.4 Pattern Examples 4.5 Notes Chapter 5 Orientable Maps 5.1 Butterflies 5.2 Simplified Butterflies 5.3 Reduced Rules 5.4 Orientable Principles 5.5 Orientable Genus 5.6 Notes Chapter 6 Nonorientable Maps 6.1 Barflies 6.2 Simplified Barflies 6.3 Nonorientable Rules 6.4 Nonorientable Principles 6.5 Nonorientable Genus 6.6 Notes Chapter 7 Isomorphisms of Maps 7.1 Commutativity 7.2 Isomorphism Theorem 7.3 Recognition 7.4 Justification 7.5 Pattern Examples 7.6 Notes Chapter 8 Asymmetrization 8.1 Automorphisms 8.2 Upper Bounds of Group Order 8.3 Determination of the Group 8.4 Rootings 8.5 Notes Chapter 9 Asymmetrized Petal Bundles 9.1 Orientable Petal Bundles 9.2 Planar Pedal Bundles 9.3 Nonorientable Pedal Bundles 9.4 The Number of Pedal Bundles 9.5 Notes Chapter 10 Asymmetrized Maps 10.1 Orientable Equation 10.2 Planar Rooted Maps 10.3 Nonorientable Equation 10.4 Gross Equation 10.5 The Number of Rooted Maps 10.6 Notes Chapter 11 Maps Within Symmetry 11.1 Symmetric Relation 11.2 An Application 11.3 Symmetric Principle 11.4 General Examples 11.5 Notes Chapter 12 Genus Polynomials 12.1 Associate Surfaces 12.2 Layer Division of a Surface 12.3 Handle Polynomials 12.4 Crosscap Polynomials 12.5 Notes Chapter 13 Census with Partitions 13.1 Planted Trees 13.2 Hamiltonian Cubic Maps 13.3 Halin Maps 13.4 Biboundary Inner Rooted Maps 13.5 General Maps 13.6 Pan-Flowers 13.7 Notes Chapter 14 Equations with Partitions 14.1 The Meson Functional 14.2 General Maps on the Sphere 14.3 Nonseparable Maps on the Sphere 14.4 Maps Without Cut-Edge on Surfaces 14.5 Eulerian Maps on the Sphere 14.6 Eulerian Maps on Surfaces 14.7 Notes Chapter 15 Upper Maps of a Graph 15.1 Semi-Automorphisms on a Graph 15.2 Automorphisms on a Graph 15.3 Relationships 15.4 Upper Maps with Symmetry 15.5 Via Asymmetrized Upper Maps 15.6 Notes Chapter 16 Genera of Graphs 16.1 A Recursion Theorem 16.2 Maximum Genus 16.3 Minimum Genus 16.4 Average Genus 16.5 Thickness 16.6 Interlacedness 16.7 Notes Chapter 17 Isogemial Graphs 17.1 Basic Concepts 17.2 Two Operations 17.3 Isogemial Theorem 17.4 Nonisomorphic Isogemial Graphs 17.5 Notes Chapter 18 Surface Embeddability 18.1 Via Tree-Travels 18.2 Via Homology 18.3 Via Joint Trees 18.4 Via Configurations 18.5 Notes Appendix 1 Concepts of Polyhedra, Surfaces, Embeddings and Maps Appendix 2 Table of Genus Polynomials for Embeddings and Maps of Small Size Appendix 3 Atlas of Rooted and Unrooted Maps for Small Graphs Bibliography Terminology 【作者简介】刘彦佩，北京交通大学教授， 1939 年生，天津宝坻区人。 1963 年毕业于中国科学技术大学数学系并留校工作。三个月后被调到中国科学院数学研究所。 1986 年晋升为研究员。 1989 年被国务院学位委员会评选为博士研究生导师。 1994 年调入北京交通大学。在基础理论方面 ,20 世纪 70 年代末，提出用演生网（派生图，或平面性辅助图）判定图的平面性，开辟了图论研究的一个新方向，解决了确定图的最大亏格问题。所创立的方法，之后被完备成联树法。为曲面嵌入建立了最简洁表示论。 80 年代最终完成缺一个三角形的完全图最小亏格的确定并简化了曲面地图着色定理。 90 年代揭示图的同调与上同调定理，第一次简单地证明了高斯关于辨别纽结在平面上投影的猜想，以及一并推广了拓扑学中琼斯多项式和图论中塔特多项式。新世纪以来，着重研究以图为代表的组合结构的代数化，完备了地图及其计数理论。将曲面、嵌入、地图以及根图等统一为一种多面形理论。发现了一批组合泛函方程，建立了它们的定性理论并且提供了求出解的有限正项和表示的统一方法。在应用理论方面，主要做与运筹学、系统论以及计算机科学有关的组合优化研究。至今，已单独出版学术专著 15 部（其中英文 6 部），发表专业文章 400 余篇（合作篇数近半）。其学术小传被选入《 20 世纪中国知名科学家学术成就概览》（数学卷第四分册）。; 个人分类: 校友文库|4783 次阅读|0 个评论

系统医学 - 拓扑网络学: benlion 2012-10-22 13:48; 我的出生地是湖南古台山林场，父亲从城里来到那里创建，种植药材。儿时，我在屋前石拱桥下的小溪里是抓螃蟹，在屋后欣赏那些美丽的芍药花；因此，首先接触的是中药，后来因教生药学和药用植物学时来到南京药科大学，参加了到狼牙山采集药材的实习。然而，自中学、大学到任教，读得最多的书籍还是科学史与哲学、心理学与医学等，比如，炼金术士罗吉尔·培根的光学和化学实验方法，博物学家林耐的生物分类学，以及托马斯 · 杨的光干涉实验和菲涅耳的光衍射理论、声波的多普勒效应等，精神分析学和格式达心理学等，而后，彭加勒的实在论和胡塞尔的现象学等。中药炼制实验和本草纲要的分类学等，在近代实验方法和生物学系统学（ systematics ）中的贡献是什么？这需要科学史学家深入研究；但是，无疑欧洲近现代科学、哲学、艺术乃至体制的建立，其中，不少源自对中国古代文化与体制的研究。直接的也许就是系统医学提出，起初研究动物形态发生与环境相互关系，而后思考拓扑生物学，那时，刚阅读中医的理论书籍，也阅读数学的图论和拓扑学，猛然间发现：一是西医解剖学的器官恰好可以与中医理论的脏象对应，余下的就是经络系统对应神经 - 内分泌、免疫系统；二是四色定理可等价于四面体，金刚石的晶体结构以顶点的连线（ connection ）关系等恰好是阴阳五行图的联结模式；三是生理学的内分泌细胞甾体激素调控基因表达和神经 - 内分泌网络等，于是，代谢系统的控制论节律稳态和发育系统的基因与神经协调变化和分子 - 细胞、器官 - 个体、种群 - 生态的生物系统层次的清晰模型出现 – 1992年获得湘潭市医学科技先进工作者奖，并评上讲师；但是， 1999 年我放在互联网上时却为国外一物理学家链接在他的超弦（ string theory ）网页上。 1994 年到了北京中关村，生物发育、细胞分化的 mRNA 差异显示分析和核移植、转基因等，基因群与蛋白质系统对应关系 - 即，现在所谓之组学（ omics ）的研究及其调控的系统遗传学，转换到细胞信号传导与基因调控、细胞代谢系统的层次，以及基因组自组织化与程序化特异表达的系统研究，传感器与反应器的系统生物工程开发等。参见“ Network topology ”（ http://biomatics.org/index.php/Systems_Bioengineering ）。续，系统医学 - 回忆录（ http://blog.sciencenet.cn/blog-286952-624743.html ）附，分子与系统医学发展的关系：; 个人分类: 2012|1923 次阅读|0 个评论

专题讨论班：图论及其应用（六）：随机图的计算技术简介: GrandFT 2012-7-24 09:31; 题目：图论及其应用——随机图的计算技术简介时间：2012年7月25日上午9:30 复杂网络的动力学过程是我们感兴趣的问题。目前，描述动力学过程的一种主要数学技术是主方程（master equation）。然而，描述复杂网络需要依靠随机图。我们之所以建立动力学过程也是希望描述随机图的演化。所以，有关随机图的数学技术——作为复杂网络的基础——是尤为重要的。主要内容： 1. Generating function 2. Component size 3. Phase transition 其中涉及无向图，有向图，二部图以及一些例子。参考文献：Random graphs with arbitrary degree distribution and their applications ( M. E. J. Newman, S. H. Strogatz, D. J. Watts); 个人分类: 专题讨论班|5210 次阅读|0 个评论

专题讨论班：图论及其应用（五）: GrandFT 2012-7-17 22:31; 题目：图论及其应用时间：2012年7月17日上午9:30 内容： 1. 网络与图 2. 随机图; 个人分类: 专题讨论班|2259 次阅读|0 个评论

专题讨论班：图论及其应用（四）: GrandFT 2012-7-13 09:17; 题目：图论及其应用时间：2012年7月13日上午9:30 内容： 1）最短路径算法 2）平面图 3）染色问题; 个人分类: 专题讨论班|2447 次阅读|0 个评论

专题讨论班：图论及其应用（三）: GrandFT 2012-7-10 16:41; 题目：图论及其应用时间：2012年7月11日上午9:30 内容： Hamilton图和Euler图; 个人分类: 专题讨论班|2627 次阅读|0 个评论

专题讨论班：图论及其应用（二）: GrandFT 2012-7-6 08:56; 题目：图论及其应用时间：2012年7月6日上午9:30 内容： 1.3 图的顶点度和运算 1.4 路与连通 1.5 回与圈; 2339 次阅读|0 个评论

专题讨论班：图论及其应用（一）: 热度 1 GrandFT 2012-7-3 15:51; 题目：图论及其应用时间：2012年7月4日上午9:30 内容： 1.1 图与图的图形表示 1.2 图的同构 1.3 图的顶点度和运算 1.4 路与连通 1.5 回与圈; 个人分类: 专题讨论班|2940 次阅读|1 个评论

《趣味的图论问题》（第2版）单墫: ustcpress 2012-6-11 09:31; 出版日期：2011年出版社：中国科学技术大学出版社书号（ISBN）：978-7-312-02916-5 定价：12.00元购书地址及读者评价： http://product.dangdang.com/product.aspx?product_id=22739700 【作者简介】单墫教授 1943 年 11 月 1 日生于天津，江苏扬州市人，南京师范大学数学与计算机科学学院教授、博士生导师、广州大学教育软件所兼职研究员，享受政府特殊津贴。 1964 年毕业于扬州师范学院数学系后在南京人民中学任教， 1978 年考入中国科学技术大学，师从著名数学家王元院士攻读研究生， 1983 年在中国科学技术大学获理学博士学位，毕业后，留在中国科学技术大学校任教。 1989 年起，任教于南京师范大学，曾任南京师范大学数学系主任、南京师范大学学术委员会委员、学位评定委员会委员、中共南京师范大学委员会委员、南京市第九届政协委员。; 个人分类: 中学教辅|5677 次阅读|0 个评论

《图论及其应用》（第3版）徐俊明: ustcpress 2012-4-18 08:46; 丛书：中国科学技术大学精品教材（“十一五”、“十二五”国家重点图书出版规划项目）出版日期：2011年4月第7次印刷出版社：中国科学技术大学出版社书号（ISBN）：978-7-312-02248-7 正文页码：336页（16开）定价：33.00元编辑邮箱： edit@ustc.edu.cn （欢迎来索要目录、样章的PDF）当当网购买地址： http://product.dangdang.com/product.aspx?product_id=20822677 【内容简介】本书着眼于有向图，将无向图作为特例，在一定的深度和广度上系统地阐述了图论的基本概念、理论和方法以及基本应用，全书内容共分 7 章，包括 Euler 回与 Hamilton 圈，树与图空间，平面图，网络流与连通度，匹配与独立集，染色理论，图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等多方面的应用，每章分为理论和应用两部分，章末有小结和参考文献，各章内容之间联系紧密，许多著名的定理给出最新最简单的多种证明，每小节末都有大量习题，书末附有记号和名词索引。本书既可用作高校数学系、应用数学系、计算机科学系、电子学系、自动化系、管理科学系和相关的研究所的研究生和高年级本科生选修课教材，也可用作高校和研究所从事相关专业的教师和研究人员以及图论工作者的参考书。【作者简介】徐俊明，中国科学技术大学数学系教授、博士生导师，中国运筹学会理事，中国数学会组合与图论专业委员会理事。美国杂志《 Journal of Mathematics and Statistics 》编委，美国《 Mathematical Review 》和德国《 Zentralblatt Math 》评论员。先后访问过法国巴黎南大学、美国耶鲁大学、中田纳西州立大学、得克萨斯大学达拉斯分校。主要从事组合数学、图论、组合网络理论研究，发表学术论文 100 多篇。; 个人分类: 数学图书|9488 次阅读|0 个评论

《图的拓扑理论》（英文）刘彦佩: ustcpress 2012-4-11 08:28; 丛书名：当代科学技术基础理论与前沿问题研究丛书——中国科学技术大学校友文库（“十一五”国家重点图书出版规划项目）出版日期：2008年9月书号ISBN：978-7-312-02275-3 出版社：中国科学技术大学出版社正文页码：472页（16开）定价：88.00元编辑邮箱： edit@ustc.edu.cn （欢迎来索要目录、样章的PDF）当当网购书链接： http://product.dangdang.com/product.aspx?product_id=20364761 【内容简介】本书不在于图的拓扑性质本身，而是着意以图为代表的一些组合构形为出发点，揭示与拓扑学中一些典型对蠏，如多面形、曲面、嵌入、纽结等的联系，特别是显示了定理有效化的途径对于以拓扑学为代表的基础数学的作用。同时，也提出了一些新的曲面模型，为超大规模集成电路的布线尝试构建多方面的理论基础。本书可作为基础数学，应用数学、系统科学、计算机科学等专业高年级本科生和研究生的补充教材，也可供相关专业的教师和科研工作者参考。【第一作者简介】刘彦佩教授，生于 1939 年， 1963 年毕业于中国科学技术大学数学系，荷兰 KLUWER 学术出版社 “Combinatorics and Computer Science （ COOS ） ” 丛书主编， 1986 ，中国科学院研究员（首批聘任）， 1989 ，被国务院学位委员会评选为博士生导师。 1987 ，美国罗杰斯大学运筹学中心和离散数学与计算机科学中心研究员； 1989 ， 1992 ，意大利罗马大学数学系、概率与统计系和计算机科学系，客座教授。 1990 ，法国社科高研院人文数学中心客座研究员，法国波尔多第一大学数学与计算机科学系客座教授。 1997 ，美国辛辛那提大学计算机科学系，客座杰出教授。 2001 年，韩国浦项科技大学组合与计算数学中心研究员。在国外公开出版物中，早期（ 1978 ）在判别图的平面性方面的一个结果被 P. Rorenstieh1 （欧洲组合学杂志三主编之一）等称为 “ 吴-刘判准 ” 和 “ 吴-刘定理 ” 。八十年代，在 Euler 地图计数方面的一个结果被 E.A.Bender （美国《组合理论杂志 A 》主编）等称为 “ 刘彦佩（ Y.Liu ）公式 ” 。在梵和（ Dichromate sum ）方面的工作，被国际著名按在 Math.Rev. 上评论的论文页数，在地图计数和拓扑图论两领域连续 3 年（ 01 ， 02 ， 03 ）分别排名第一和第二。; 个人分类: 校友文库|3762 次阅读|0 个评论

医学研究人员的数学修养: zzkpumc 2010-9-27 17:28; 昨天，是我的硕士导师韩向午教授八十华诞和从教 55周年，在座谈会上，韩教授介绍了医学研究人员数学修养的培养，不无裨益。韩教授师从我国流行病学前辈苏德隆教授（苏教授的导师则是因发现青霉素而获得诺贝尔医学奖的弗莱明爵士）。苏教授回国后，正赶上刘邓大军下江南，当时，南方正值血吸虫病流行，很多士兵因为接触疫水感染发病，部队减员严重。苏德隆教授临危受命，使用最原始、最简单的方法，成功阻止了血吸虫病的流行。解放后，苏教授在上海医学院任教，并一直致力于血吸虫病的防控理论研究。他当时就认识到，如果没有从理论上解决血吸虫的传播-扩散-控制问题，等于没有从根本上认识该问题。几年后，提出了自己的血吸虫病数学模型，并得到了霍普金斯大学同行的认可。在研究流行病学理论的过程中，苏教授非常清楚地认识到，自己在数学基础方面存在着明显的缺陷，于是，给研究生开设的课程中，增加了现行代数、数理统计学等基础课程，同时，请华东师大的数学老师到上海医学院授课。授课方式也很特别。苏教授定期把Biometrics和Biometrika的文章拿下来，根据授课内容和进度，结合文章范例，直接让数学老师把理论讲解和应用结合起来。这些学习经历，可能是韩教授数学修养的最直接来源。在我们学习研究生课程期间，韩向午教授照猫画虎，也给我们开设了类似课程，并指导我们用手工方法，完成了三例病例预后因素的半参数回归分析（COX-model）。当时，感觉到这些课程非常枯燥，也没有意识到它对我自己科研思路的影响。读博士期间，在英国处理数字信号，用到了比较简单的微分方程和矩阵计算，那时，才由衷地感叹先生的高明！韩教授说，医学工作者的数学修养至少应该达到什么程度？你的医学问题，能够用简单的数学语言，让数学专业人员听明白。要求不高，但达到的确不容易。最近，带研究生课题，选定的题目是空间距离与手足口病的传播问题，目的是想检验自然村落之间的空间对于手足口病的发病率是否有影响。我们已经获得了每个村落的空间坐标、0-5岁儿童的手足口病发病率，用什么方法来计算统计参数，并检验这些参数呢？除了经典的相关分析、空间预测中使用的半方差模型外，还有没有更直截了当的解决方案呢？或者，这个问题从一开始就是错误的？我想到了图论中的一些基本原理。或许，半个月后，我能够为研究生指出下一步的努力方向。医学生的数学修养有多深，他的路就能做多远。; 个人分类: 乱七八糟|6278 次阅读|2 个评论

从图的标号问题谈图论问题的机器证明: formleaf 2010-8-11 22:27; 曾经研究过一段时间图的标号问题。主要的方法是通过计算机辅助找到某类图的所有可能标号的集合，从中发现这一类图的标号规律。当时就有一个想法，能否设计一个算法在生成的标号集合中找到这样的规律，不过当时没能实现这个想法。后来看到吴文俊先生的数学机械化及其在几何机器证明中的应用，让我不禁想到在图论中是否也存在这样的机械化方法，哪些图论问题是可以机器证明的呢？其实图论问题的机器证明早已有之。例如欧拉图的判定，平面图的判定等等算法，都可以看成是机器证明图性质的例子。还有一些特殊的例子，比如四色定理的计算机证明，只不过这样的方法没有一般性，因此从方法的角度看意义不是很大。然而，我现在关心的是对某一大类图论问题（例如标号问题）是否存在一个通用的方法，使得如果图的性质存在规律性的东西，这个方法能够通过计算机把它找到。如果能找到，也就意味着这类问题有一个构造性的证明。我很期待能看到这样的方法，同时我也在做这方面的尝试。; 个人分类: 机器证明|2020 次阅读|0 个评论

请教一个数学问题: 热度 1 creator 2010-6-25 09:35; 最近在做一件事时，遇到一个非常棘手的问题。如图所示这是著名的七桥问题的图解模式，问题出在用工具画最右边的图上面。现在假设蓝色圆点的直径按照一定的规则可以改变，比如取1-10的整数。它们之间的连线先考虑直线。同时在连线的过程中不跨过圆点。因为某些点之间有两条连线以上，所以假设连线不一定穿过圆点圆心。问题来了，该用什么样的计算准则来确定圆点的位置，使其满足要求的同时，看上去还比较美观，产生美观的要求可以参照圆点的平均分布，连线距离差值较小或其方差较小，大小圆点位置分布成一定比例，最紧密联系圆点间形成集合区等。三四个点容易徒手解决问题，问题是如果我要在不同路径中间不停的添加新的圆点和路径时，怎么保证整个圆线图的美观协调。比如达到100个圆点时怎么保证其美观协调？再者如果我要选择某个或某些圆点为固定时，怎么确定其分区的美观性紧凑性？如果连线是曲线的情况下又应该如何确定？现在是在二维的平面内解决布点与布线美观的问题，那么如果每个圆点换做圆球，使用空间的三维坐标，空间位置的协调性该如何保证。我能想到的就是利用不同圆点的位置坐标来尽量平均圆弧间的距离。同时根据不同圆点间，连线的级数来决定圆点靠近的原则，然后在利用级数越低的圆点间采用更趋直线的布点方式。但是这完全停留在想法阶段，不知道用什么数学公式去限制计算。大意就如同将这张图，美观化，规则化。一个画图排版的问题该用什么数学原理去计算。希望博友们不吝赐教。拜谢先！; 个人分类: 科学|1611 次阅读|3 个评论

介绍几个图论和复杂网络的程序库 —— BGL，QuickGraph，igraph和NetworkX: 热度 6 yanxiaoyong 2010-2-24 12:05; 刚加入复杂网络圈子，暂时还没有成熟的研究内容，先发个资料性的东西占坑：）作复杂网络研究离不开对各种实际或模拟网络的统计、计算、绘图等工作。对于一般性的工作，我们可以用 Pajek 、 Netdraw 和 Ucinet 等软件完成。但对一些特殊应用（比如自己开发了一个新模型），现有的软件不能提供相应的建模或计算功能，这时就必须要通过编程的办法来解决问题了。在这篇文章中，向大家介绍我使用过的4个面向图论及复杂网络分析的程序库，它们可以（分别或同时）用C、C++、C#和Python等语言调用。同时这些库都是开源的，可以通过研读它们的源代码提高编程水平。好，下边开始介绍，第一位出场的是：一、Boost Graph Library 准C++标准库 Boost Graph Library（BGL）是C++ Boost库的成员之一。Boost是一个经过千锤百炼的C++库，作为标准模板库STL的后备，是C++标准化进程的发动机之一。Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，是不折不扣的准标准库。 BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C++专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。此外，BGL的代码结构良好，是非常值得研读的精品，对于学习算法与数据结构会有很大的帮助。从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。参考资源： BGL官方网站： http://www.boost.org/doc/libs/1_42_0/libs/graph/ 技术书籍《The Boost Graph Library》，作者: Jeremy G. Siek，Lie-Quan Lee，Andrew Lumsdaine，见： http://www.douban.com/subject/1463103/ 《使用Boost Graph library》，一个简短的BGL使用介绍，适合快速上手，见： http://www.cppprog.com/2009/0408/100.html 《Boost Graph Library 学习笔记》，讨论学习BGL中遇到的问题，见： http://blog.csdn.net/magicblue/archive/2009/05/22/4208976.aspx 二、QuickGraph .NET平台下的BGL QuickGraph是一个用C#语言编写的.NET组件库，所提供的算法与BGL类似，可以看作是Boost Graph Library在.NET平台下的实现。目前QuickGraph的最高版本是3.3，支持.NET 2.0和.NET 3.5平台。对于复杂网络研究，QuickGraph能够提供的帮助与BGL基本类似。如果你对C#语言（以及其它支持.NET的语言）比较熟悉，可以考虑选择这个库。但由于.NET程序是在虚拟机下运行的原因，所以效率不够高，不适合处理大规模的计算问题。参考资源： QuickGraph官方网站： http://www.codeplex.com/quickgraph 中文资料暂时还找不到。三、igraph C语言写的复杂网络分析库 igraph是一个建立和操纵无向图、有向图的开源C程序库，它既包含经典图论里的各种算法（例如最小支撑树、网络流等），也包含了最近的出现的一些网络分析算法（如社团结构搜索等）。 igraph是C写的，这意味着你很容易在C/C++中使用它。如果你不熟悉这两种语言，或者觉得用C/C++太繁琐的话，igraph还提供了R语言（一种国外很流行的统计分析语言）和Python语言的接口，所以也很适合科研人员使用（我现在用的是Python，调用igraph很简单）。参考资料： igraph官方网站：http:/ /igraph.sourceforge.net/ 关于Python语言的介绍，见： http://zh.wikipedia.org/wiki/Python 关于R语言的介绍，见： http://zh.wikipedia.org/wiki/R语言四、NetworkX 全面支持复杂网络分析的Python包 NetworkX是一个创建和操纵复杂网络，并对复杂网络的结构、功能和动力学进行研究的Python包，它提供了目前应用最广泛的一些复杂网络分析算法，当然也包括基本的经典图论算法。NetworkX目前只能在Python语言中使用（这也是我学Python的原因之一，见《从C#到Python 谈谈我学习Python一周来的体会》）。我个人认为NetworkX比igraph要好用，因为NetworkX的文档更清晰易读，程序结构组织得也很好，我现在主要在用这个包。但NetworkX的执行效率多数情况下会比igraph要低（见Drew Conway所作的对比： http://files.meetup.com/1406240/sna_in_R.pdf ）。所以也不适合作太大规模的网络分析计算。此外，NetworkX和Python的一个绘图包Matplotlib结合得很好，可很方便地进行复杂网络可视化。参考资源： NetworkX官方网站： http://networkx.lanl.gov/ Matplotlib（科学绘图的Python包）： http://matplotlib.sourceforge.net 五、总结本文介绍了图论与复杂网络研究常用的一些程序库。用好这些程序库（以及其它一些软件工具），可以避免我们无谓的re-invent the wheel，从而提高工作效率。在网上了解到，国外同行用这些库的很多，而在国内还很少搜索到这方面的资料（除了BGL）。作为我进复杂网络圈的敲门砖，向各位圈友推荐这几个库。另外，我近期正在学习Python和NetworkX，如果您感兴趣，欢迎和我交流：）附：几个库的开发及调用语言对比（*看来学Python还是不错的，这几个库都可以调用-_-）库名称原始开发语言可用某语言调用 BGL C++ C++/ Python（通过boost-python） QuickGraph C# 支持.NET平台的任何语言(Python程序员可用IronPython) igraph C C/C++/R/Python（理论上至少有50种语言可直接或间接调用C程序） NetworkX Python Python; 个人分类: 复杂网络|43405 次阅读|45 个评论

[转载]Google搜索与因特网的数学: 热度 1 wjc05 2010-1-25 19:33; http://www.casad.cas.cn/gzdt/200512/t20051206_43268.html 2005年12月3日下午，科学与中国院士专家巡讲团在南开大学伯苓楼一楼报告厅举办主题报告会，邀请中国科学院院士、第三世界科学院院士马志明研究员作题为Google搜索与因特网的数学的报告。此次报告会由南开大学副校长陈永川教授主持，近400名来自天津市各大高校的师生到场聆听了报告。马志明院士首先演示了Google可以在0.36秒内搜索出26,000项相关页面，而排在最前面的就是我们最感兴趣的。由此引申到报告的第一部分利用网络拓扑结构对网页进行排序。他说，实际上，我们的这个世界就是一个网络，因特网把我们的世界连成一体。Google搜索可以在极短的时间内把网页排序，根本原理就是利用网络的拓扑结构判断网页的重要性。马志明院士用一个形象的比喻来解释这一原理。在申请升职、提级的时候，或者申请博士答辩的时候，你会说你的文章多么重要，但是很可能评审专家们并不明白你的成果有多重要。现在流行的办法就是问你这些成果被引用的次数以及是否有国际权威引用，这两条往往是外行评价内行的一个办法。虽然这不应该是唯一的评价标准，但是在其他方法失效的情况下却是很有效的。Google在给出页面排序时也有两条标准，一是看有多少超级链接指向它；二是要看超级链接指向它的那个页面重要不重要。这两条直观的想法就是Google搜索的数学基础，是Google最基本的工作原理。马院士说，这样一个基本原理是和你们同年龄或者比你们年龄还小的两个年轻人发现的。1998年斯坦福大学的SergeyBrin和LarryPage想到了用上述原理刻画网页重要性，发表了一篇文章，并且把他们的算法取名叫做PageRank。这不仅是理论上的发现，文章发表之后他们就办公司实践了PageRank算法，并且非常成功。他们就是Google公司的创办人。马志明院士从图论的角度解释Google的排序原理：一是看这个页面对应顶点的度；二是要给连在这个顶点上的边一个权重，表明这个超级链接的重要性。具体的讲就是把所有的页面看作图里面的点，然后给每一个页面一个数量，用这个数量来刻画页面的重要性，这样网页的重要性就脱离了它的具体内容。我们只需从网络拓扑结构出发研究网页的重要性，最后转变为求有向图关联矩阵的非负特征向量，这样就可以用矩阵论来研究随机复杂网络。图论里面的这么一点知识解决了这样一个大的问题。而且按照这个原理对网页排序具有三个特点：第一，排序与问讯的问题无关；第二，排序与网页的内容无关；第三，只需要知道网页的图的结构。马志明院士指出，现在不同的公司包括微软研究院，Google公司，因特尔公司等都在相互竞争，都在研究怎样淘汰大量的垃圾页面，提高网页搜索的质量。然而，提高网页搜索质量的关键是算法的收敛速度。我的一位博士后用马氏链的办法解决了WWW2005一篇文章中关于算法收敛速度的猜想，而且证明的结论比这个猜想还广，可见数学真的很有实际意义。他说，随机复杂网络虽然是在经典图论的基础上发展起来的，但是它们之间存在很大的差别。复杂网络和图的不同之处在于网络是动态的、随机的，结点是大量的。在图论里面，我们可以问去掉哪几个点这个图就不连通了。对于随机复杂网络，我们要的是去掉百分之几的点网络就不工作了。网路和图，在我们日常生活中到处都有。例如信息网络：WWW,Internet，计算机共享，Email网,专利使用；技术网络：电力网，电话线路网；交通运输网：航线网，铁路网，公路网，自然河流网；社会网：演员合作网，友谊网，论文引用；姻亲关系网，科研合作网；生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络等等都是随机复杂网络。这些领域相差甚远，但是人们发现，它们形成的随机复杂网络具有惊人的相同的统计特征：第一，小事件现象：网络中任意两点间距离的平均值很小；第二，聚集现象：网络中有足够多的三角形；第三，无标度现象：顶点的度的分布满足Scalingfree规律。马志明院士报告的第二部分讨论了因特网上病毒传播的阈值问题。他说，传统的疾病传播，把人和人之间的接触看作是等概率的，人跟人接触之后被传染的机会也是等概率的，这样所有的疾病都有一个传播的临界值。而一些统计物理学家证明，因特网上只要出现病毒，哪怕出现的概率很小，也会传播开来，也就是说网络上病毒的传播阈值是零。用随机复杂网络研究疾病预防会节约很多成本。预防疾病传统的方法是随机挑选百分之几的人打预防针，但是这不是最好的方法。随机选点将所有的结点平均化了，然而实际上有些结点的度数很高。接触传染的疾病预防应该基于网络模型，根据网络不均匀、不对称的分布特点，预防疾病较有效的方法是随机选取边，按照边来选择预防对象，这样可以最快的找到度数高的节点，并且可以节省很多人力和物力。例如对艾滋病的预防，非洲有些地方就是这么做的，效率非常高。在报告内容的第三部分，马志明院士介绍了随机复杂网络的研究现状。他说，目前人们在社会网络或计算机网络上传染过程、网络顶点故障对通讯网络性能的影响、网络相变与网络动态系统、蛋白质基因的网络结构等方面已经有了一些初步的研究。虽然，现在关于随机复杂网络的研究仍处于初级阶段，至今还没有成熟的理论框架和系统的程序和方法来研究复杂网络，甚至关于随机复杂网络的哪些属性属于最重要的研究目标这样一个基本问题都没有清楚的答案。但是，随机复杂网络蕴涵了很多深刻、有趣的数学难题，这些正吸引着国际一流的科学家。近年来Science,Nature,PhysicsRev.Letter等杂志上发表了大量研究和探讨复杂网络的文章。随机复杂网络的研究是一大片没有开垦的土地，在这里面有大量的工作值得我们去投入。最后，马志明院士总结道，现在网络的影响已经遍及世界的各个角落，研究随机复杂网络对社会发展具有战略意义，而数学正是研究它的有力、高效的工具。今后，我们需要继续研究发生在网络上的各种过程行为及其应用。随机复杂网络与自然科学、社会科学相互交叉融合，具有巨大的理论和应用前景。如果大量的老师和同学参与进来，就可能会做出开创性的工作。随机复杂网络是一个真正的交叉学科，它将成为跨学科研究的生长点，它的发展和广泛运用，都将有力地推动学科间的整合和交叉学科的诞生与繁荣。马志明院士生动精彩、内涵丰富、深入浅出、高瞻远瞩的报告激起了广大师生的强烈反响，受到了与会者的广泛好评。报告的同时，南开BBS上还进行着现场报道，共发消息30余篇，引发了同学们的热烈讨论。随着报告的结束，进入现场提问环节。来自天津市各大高校的数学学院、计算机学院、物理学院等不同专业的青年学子纷纷举手踊跃提问，马志明院士一一给予耐心、详细的解答。马志明院士深厚渊博的学识、精彩丰富的演讲和新颖独到的见解博得了与会师生热烈的掌声。 Google搜索与 Inter网的信息检索; 个人分类: 复杂网络|3981 次阅读|2 个评论

两个有关魔方的问题: shaoww 2009-6-28 08:36; 两个有关魔方的问题最近玩魔方，想到这样两个问题： 1、一个三阶魔方有多少种排列组合？进一步，在同构的意义下，一个三阶魔方有多少种排列组合？ 2、证明或否定：一个三阶魔方不存在任意两个小方块同色面互不相邻的状态。等价的说，一个三阶魔方不存在这样一种状态：任一面中的9个小方块没有同色边。另外，第一个问题前一部分网上有一个说法 4325 亿亿，本人猜测是不对的。; 个人分类: 问题征解|5393 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 图论

相关帖子

相关日志

关闭安全验证