极大平面图的结构与着色理论(2)多米诺构形与扩缩运算

业已证明四色猜想的数学证明可归结为刻画4-色漏斗型伪唯一4-色极大平面图的特征。为刻画此类极大平面图的结构特征,本文提出一种构造极大平面图的方法 扩缩运算。研究发现:此方法的关键问题是需要清楚一种构形,称为多米诺构形。文中构造性地给出了多米诺构形的充要条件;在此基础上提出并建立了一个图的祖先图与子孙图理论与构造方法。特别证明了:任一最小度4的n(9)-阶极大平面图必含(n-2)-阶或(n-3)-阶祖先图;给出极大平面图的递推构造法,并用此方法构造出6~12-阶所有最小度的4极大平面图。扩缩运算是本系列文章的基石。     

极大平面图的结构与着色理论 (4)-运算与Kempe等价类

设G是一个k-色图,若G的所有k-着色是Kempe等价的,则称G为Kempe图。表征色数3的Kempe图特征是一尚待解决难题。该文对极大平面图的Kempe等价性进行了研究,其主要贡献是:(1)发现导致两个4-着色是Kempe等价的关键子图为2-色耳,故对2-色耳的特征进行了深入研究;(2)引入-特征图,清晰地刻画了一个图中所有4-着色之间的关联关系,并深入研究了-特征图的性质;(3)揭示了4-色非Kempe极大平面图的Kempe等价类可分为树型,圈型和循环圈型,并指出这3种类型可同时存在于一个极大平面图的4-着色集中;(4)研究了Kempe极大平面图特征,给出了该类图的多米诺递推构造法,以及两个Kempe极大平面图猜想。     

工程数学

0157.5 2004050002几类平面图的分数染色/高波,孙磊,赵海霞(山东师范大学)“曲阜师范大学学报(自然科学版)一2 004,30(2)一29一32图G的一个分数染色是从G的独立集的集合疗到区间10,1}的一个映射c,麟对任意顶点x,都有又,‘;,、。、:c(“)乡,将此分数染色的值定义为艺s。(c(s)·图G的分数色数灯(G)是它的所有分数染色的值的下确界.讨论了几类平面图的分数色数.图3参5(木)的适应度曲面.仿真实验证明了其优越性能.图4参创刚)0157.5 2004050003完全二叉树理论的模型及性质/陈磊,沈复兴(北京师范大学)l/北京师范大学学报.一2004,40(2).一177一18…     

工程数学

0157.5关于几类图的L(3,2,大学学报图G的(自然科学版 2004060002·标号问题/邵振东(南京大学)I]曲阜师范一2004,30(3)一24一28L(2,l)一标号是一个从顶点集V(G)到非负整数集的函数则}了(:)一f(,)}全1.图G的L(2,1卜标号数久(G)是使得G有max{f(。):?任V(G)}二k的L(2,l)一标号中的最小数k.该文将L(2,l)一标号问题推广到更一般的情形即L(3,2,l)一标号问题,并得出了Kneser图、高度不正则图、Halin图的入3(G)的上界.参6(木)、.J尹1工、石f(x),使得若d(x,y)二1,则!f(x)一f(军)}全2;若d(x,y)二2,工程数学~~…     

工程数学

0 157.5 2003040014H图的一些充分条件和一个猜想/赵克文,吴炎(琼州大学)“应用科学学报.一2003,21(1)一99一102提出了新概念:n阶图G的距离为2的任两点两点均不相邻且到这两点之一的距离为2的任一点 v及和这.若均满足}N(u)UN(v)}+d(w)》n,则G是H图.并得到这条件的Hamil-tonian最好结果.图1参9(木)0224 2003040015改进遗传算法创乍线性变参数估计中的应用/高铁红,李冲宵.韩彦芳,陶媚(河J匕工业大学))j数据采集与处理.一2 002,17(3)一271-275针对解决非线性系统模型变参数估计问题要求运算速度快、效率高的情况,提出了实数编码遗传算法的…     

东芝公司的TMM41256C/P

MOS动态RAM于1970年1k位实用化以来,以3年4倍的比率继续向大容量化发展,现在64k位正在大批量生产。从16k位向64k位发展,作为前进中的技术问题,除所谓4倍集成度以外,工作电压从3电源方式(+12v、+5v、-5v)变成单电源(-5v)方式。而更进一步向256k位开发前进将带来如下问题。即,     

T2E真空管单端甲类合并功率放大器

父2C(6J5,6e5P,民%T)5.zk 6NSP(63N7』6HSP)EL34石(五极管接法)15k5:*自士乏品、油漫 L IN么以迄卜20k}1 90V工魂产丁‘00v油浸0 .47尸275V宝尔真牌18W单端愉出牛9砚砚叭签400V2匕es勺5台l20k1 5k5鉴盆卫︺︺Iv冻l一加0 d ..1 ILLI CDT启FESG7 1 1278泛份{{。v}}2.5侧8刃SQ刃魂Q刃00(A)、0二tb)、o口(c犷240k47X282023档步进高级电位器2‘“估t’v 厂一1 Zk描}湍+B16Ull50宝尔真牌300,万2翌) {下一-止望丝阅 OV 0.5人需让』望巡一刃280V卜l辛36kTZE真空管单端甲类合并功率放大器(6cZc放大.乱3吸习功率输出J油浸电容福合…     

任意长度离散Hartley变换的快速算法

本文把长为plq(p为奇数,q为任意自然数)的DHT转化为Pl个长为q的DHT的计算及其附加运算,附加运算只涉及P点cos-DFT和sin-DFT的计算;对长度(P1l,1,Psls 2l (p1, , ps为奇素数)的DHT,用同样的递归技术得到其快速算法,因而可计算任意长度的DHT;文中还论证了计算长为N的DHT所需的乘法和加法运算量不超过O(Nlog2N)。当长度为N=pl时,本文算法的乘法量比其他已知算法更少。     

一种快速递归全局最小二乘算法

针对FIR系统输入和输出信号均被噪声干扰的情况,提出一种快速递归全局最小二乘(XS-RTLS)算法用于迭代计算全局最小二乘解,算法沿着输入数据的符号方向并采用著名的快速增益矢量,搜索约束瑞利商(c-RQ)的最小值得到系统参数估计。算法关于方向更新矢量的内积运算可通过加减运算实现,有效降低了计算复杂度;另外XS-RTLS算法没有进行相关矩阵求逆递归运算,因而具有长期稳定性,算法的全局收敛性通过Laslle不变性原理得到证明。最后通过仿真比较了XS-RTLS算法和递归最小二乘(RLS)算法在非时变系统和时变系统中的性能,验证了XS-RTLS算法的长期稳定性。     

Evolium~(TM) UMTS释放3G新动力

在中国,人们对3G的需求不可能像在2G初期对话音的需求那样在短时间内大规模释放,而将随着网络不断完善、价格稳步下调、业务逐渐丰富而逐步得到释放。随着信产部的TNET 外场测试即将结束,各大厂家的3G 移动网络解决方案都已经准备就绪,在移动领域一场新的革命正蓄势待发。 UMTS　是3G 的一个重要组成部分,在全球已经有众多的成功商用案例。首先来了解一下Evolium 猆MTS 系统,Evolium 猆MTS 由无线接入网(UTRAN)、核心网(Core　Network)以及应用平台三大部分组成。具体来说, v o l i u m 猆M T S 无线接入子系统主要有9100　M…     

The k-Diameter of a Kind of Circulant Graph

The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph, diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, n/2) be a circulant graph of order n whose spanning elements are i and n/2, where n4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n/2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.     

The k-Diameter of a Kind of Circulant Graph

The terminology and notion in this paper are similar to Ref.[1], all graphs discussed here are finite and simple. The diameter d(G) of a graph G is the maximal distance between pairs of vertices of G. The connectivity of G is the minimum number of vertices needed to be removed in order to disconnect the graph. When a network is modeled as a graph,a vertex represents a node of processor (or a station) and an edge between two vertices is the link (or connection) between those two processors. I…     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk(x,y) between the any vertices x and y is first obtained in a connected circulant graph G with order n(n is even) and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk(x,y).     

Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.     

Grid Colorings in Steganography

A proper vertex coloring of a graph is called rainbow if, for each vertex v, all neighbors of v receive distinct colors. A k-regular graph G is called rainbow (or domatically full) if it admits a rainbow (k+1)-coloring. The d-dimensional grid graph G_d is the graph whose vertices are the points of Zopf^d and two vertices are adjacent if and only if their l₁-distance is 1. We use a simple construction to prove that G_d is rainbow for all d ges 1. We discuss an important application of this result in steganography     

The L(2,1)-labeling and operations of graphs

Motivated by a variation of the channel assignment problem, a graph labeling analogous to the graph vertex coloring has been presented and is called an L(2,1)-labeling. More precisely, an L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)| /spl ges/ 2 if d(x,y)=1 and |f(x)-f(y)| /spl ges/ 1 if d(x,y) = 2. The L(2,1)-labeling number /spl lambda/(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v/spl isin/V(G)}=k. A conjecture states that /spl lambda/(G) /spl les/ /spl Delta//sup 2/ for any simple graph with the maximum degree /spl Delta//spl ges/2. This paper considers the graphs formed by the Cartesian product and the composition of two graphs. The new graph satisfies the conjecture above in both cases(with minor exceptions).     

分析方法在Ramsey数估值中的应用

“Yusheng等人曾给出-个独立数的下界公式：α（G）≥Nfa＋1（d）,其中fa（x）=∫0^1（1-t）1/a dt/（a＋（x-a）·t）。为了得到r（H,Kn）的上界,可以考虑建立不合H作为子图的临界图G的独立数的下界。即通过对临界图G及其邻域导出子图e的平均次数的分析,得出G的阶（顶点数）Ⅳ与n之间的不等式关系。再利用函数五（x）的分析性质得出当n趋于无穷大时,N＋1的最小可能渐近表达式,即为r（H,Kn）的渐近上界。主要介绍这种分析方法在解决Kk＋Kt,“K1＋Cm”,“Km．t”等图形和完全图Ramsey数渐近上界问题中的应用。     

Total Coloring of G×Pn and G×Cn

It is proved that if G is a (△+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and △ the maximum edge degree of the graph. The exact chromatic numbers of the product graphs Pr1×Pr1×...×Prn× and C3k×C2m1×C2m2×...×C2mn are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.