题名 | 三角格及满二叉树上的全一问题; All-ones problem on triangular grids and full binary trees |
作者 | 平征 |
答辩日期 | 2008 ; 2008 |
导师 | 钱建国 |
关键词 | 全一问题 偶等价覆盖 奇集合 三角格 满二叉树 all-ones problem parity cover odd set triangular grids full binary trees |
英文摘要 | 细胞自动机是一种离散动力系统,它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则.其数学刻画如下:假设在一个无向图的每个顶点上安装有一个指示灯和一个按钮.如果在该图中按下一个按钮,则它的所有相邻点上的灯将由暗到亮,反之亦然.开始时,所有灯都是暗的.问题是:是否有可能按下一系列的按钮使得最终所有的灯都亮了?该问题被称为全一问题,特别地,若图的每一个点都有一个自环,则它也被称为全一问题,起源于Sutner[29]引入的棋盘上的全一问题,后被Peled[20]称为点灯问题.近年来全一问题已经被广泛的研究,见文Sutner[30,31],Barua和Ramakrishnan[2]以及Dodi...; A cellular automaton is discrete dynamical system that consist of an arrangement of basic components called cells together with a transition rule. This system can be mathematically modeled as the following problem: Consider an undirected graph equipped with an indicator light and a button in each of its vertices. If a button is pressed, then the light of all its edge-adjacent vertices will change ...; 学位:理学硕士; 院系专业:数学科学学院数学与应用数学系_应用数学; 学号:X2005170018 |
语种 | zh_CN |
出处 | http://210.34.4.13:8080/lunwen/detail.asp?serial=20702 |
内容类型 | 学位论文 |
源URL | [http://dspace.xmu.edu.cn/handle/2288/47564] ![]() |
专题 | 数学科学-学位论文 |
推荐引用方式 GB/T 7714 | 平征. 三角格及满二叉树上的全一问题, All-ones problem on triangular grids and full binary trees[D]. 2008, 2008. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论