推荐星级：
- 1
- 2
- 3
- 4
- 5
基于标签分组的RFID系统防碰撞算法
资料介绍
防碰撞算法是射频识别(RFID)系统中提高标签识别效率的关键技术。针对确定性的RFID标签防碰撞算法存在的识别效率不高、系统数据交换量大等问题,该文提出一种标签分组机制防碰撞算法,将其与融合后的二进制树搜索算法相结合,读写器系统分批次识别标签组中的标签,能有效地减少数据通信量。实验仿真结果表明,该算法相比其他几种算法,具有识别效率高、数据交换量小等优势。
部分文件列表
| 文件名 | 大小 |
| 基于标签分组的RFID系统防碰撞算法.pdf | 844K |
部分页面预览
（完整内容请下载后查看）第39 卷第1 期
2017 年1 月
电 子 与 信 息 学 报
Vol.39No.1
Jan. 2017
Journal of Electronics & Information Technology
一种特殊的多米诺扩缩运算
刘小青
许
进*
(北京大学信息科学技术学院 北京 100871)
(北京大学高可信软件技术教育部重点实验室 北京 100871)
摘
要：该文提出一种称为 334 扩缩运算的多米诺扩缩运算。使用该运算构造了一类特殊的极大平面图——334-
型极大平面图，证明了该类图均为树型 2-色不变圈着色，且每个4k -阶 334-型极大平面图恰有2k-1 个 2-色不变圈
着色及2k-2 个树着色。证明了该运算可用于构造纯树着色极大平面图，并提出猜想：若极大平面图G 是纯树(纯圈，
混合)着色，则对G 实施334 扩(缩)轮运算后，所得之图仍是纯树(纯圈，混合)着色。
关键词：半封漏斗；树型2-色不变圈着色；纯树着色；334 扩轮运算
中图分类号： O157.5
文献标识码： A
文章编号：1009-5896(2017)01-0221-10
DOI: 10.11999/JEIT160886
Special Type of Domino Extending-contracting Operations
LIU Xiaoqing
XU Jin
(School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China)
(Key Laboratory of High Confidence Software Technologies, Peking University, Beijing 100871, China)
Abstract: In this paper, a new domino extending-contracting operation, called 334 extending-contracting operation,
is put forward, on the basis of which, it is proposed to construct a particular kind of graphs, i.e., 334-type maximal
planar graphs, and proved that all those graphs are tree-type and 2-chromatic cycle-unchanged colored and every
334-type maximal planar graphs of order 4k has exactly 2k-1 2-chromatic cycled-unchanged colorings and 2k-2
tree-colorings. Additionally, it is proved that an infinite family of purely tree-colored graphs can be generated by
implementing a series of 334 extending-wheel operations, and conjectured that if a maximal planar graph G is
purely tree-colored (purely cycle-colored or impure-colored), then the graph obtained by implementing one 334
extending-wheel (contracting-wheel) operation on G is still purely tree-colored (purely cycle-colored or
impure-colored).
Key words: Semi-funnels; Tree-type and 2-chromatic cycle-unchanged colored; Purely tree-colored; 334 extending-
wheel operations
1 引言
图G 的一个k -着色，是指从图G 的顶点集V 到
颜色集C
的xy Î E
(
k
)
=
{
1, 2,, k
}
的一个映射f ，满足对任意
。图G 的色数，记作
本文所言之图皆指有限、简单、无向图。对于
给定图G ，分别用V , E 和dG (v)来表示图G
的顶点集，边集，顶点v 的度数，可分别简记为V ,E ,
d(v)。图G 的阶是V 中元素的个数V 。若
V' ÍV , E' Í E ，且E' 中每条边的2 个端点均在V'
中，则称图H = V',E' 是图G 的一个子图。
(
G
)
，有f(x) ¹ f y
( )
(
G
)
( )
G
( )
c G ，是指满足图G 有一个k -着色的最小数值k 。
图G 中所有不同的k -着色构成的集合用Ck
示，若 2 种着色可通过颜色互换达到对方，则这 2
种着色被认为是相同的。
(
G
)
表
(
G
)
( )
G
(
)
设G 是一个k -可着色的图， f ÎCk
(
G
)
，
{1, 2,,k} 为颜色集。G 中所有着颜色i 与颜色t 的
顶点构成的顶点子集导出的子图称为 2-色导出子
图，2-色导出子图中的分支称为 2-色分支，其中，
i,t = 1, 2, , k , i ¹ t 。Kempe 变换是指对图G 中某
个 2-色分支实施颜色互换，并使其余顶点着色不变
收稿日期：2016-08-29；改回日期：2016-12-06；网络出版：2016-12-14
*通信作者：许进
基金项目：国家973 计划项目(2013CB329600)，国家自然科学基金
(61372191, 61472012, 61472433, 61572046, 61502012, 61572492,
61572153, 61402437)
Foundation Items: The National 973 Program of China
(2013CB329600), The National Natural Science Foundation of
China (61372191, 61472012, 61472433, 61572046, 61502012,
61572492, 61572153, 61402437)
的一种着色运算。设f, f' ÎCk
( )
G ，若从f 出发，通
过若干次 Kempe 变换可获得f' ，则称f 与f' 是
222
电 子 与 信 息 学 报
第39 卷
Kempe 等价的。图G 的基于f 的 Kempe 等价类是
指由f 以及所有与f 互为Kempe 等价的着色构成之
集。有关 Kempe 变换的最新研究进展可查看文献
[1-5]。
( )
设G 是一个4-色极大平面图，f ÎC4 G 。若G
有一个偶圈C ，C 在f 下仅含有2 种颜色，则称f 为
圈着色；否则，称f 是树着色。若G 不含树着色，
则称G 是纯圈着色的；若G 不含圈着色，则称G 是
纯树着色的；若G 含圈着色和树着色，则称G 是混
合着色的。若基于f 的 Kempe 等价类Ff 满足：存
在一个偶圈C ，使得C 在任意g Î Ff 下仅含2 种颜
色，则称f 为 2-色不变圈着色。若G 仅有树着色和
2-色不变圈着色，则称G 是树型 2-色不变圈着色。
文献[6,7]对平面图的着色类型进行了研究，将
着色分为树着色和圈着色，依据着色类型将 4-色平
面图分为 3 类：纯树着色型、纯圈着色型和混合着
色型，并提出了纯树着色猜想“一个平面图是纯树
着色图当且仅当它是正二十面体或哑铃极大平面
图”，若该猜想成立，则著名的已有 43 年历史的唯
一4-色平面图猜想[8-12] 成立。文献[13]定义了一类特
图1 漏斗与45-型半封漏斗子图
d v = 4 ，d v = d v = 5，则称H 是G 的一
(
)
G ( )
( )
G
3
1
G
3
个45-型半封漏斗子图，简称为45-型子图。
334扩轮运算的对象图是极大平面图中的45-型
子图。334 扩轮运算，记作V ，是指按照如下步骤，
将G 的一个 45-型子图H (如图 1(b)所示)变成图
2(a)~2(d)中最右边所示构形的过程：
步骤 1 确定H 的漏腰顶点和漏底顶点。显然，
漏腰要么是v4 ，要么是v2 。若选择v4 作为漏腰，则
2 个漏底要么是v1 和v2 ，要么是v3 和v2 ；若选择v2 作
为漏腰，则2 个漏底要么是v1 和v4 ，要么是v3 和v4 。
以下步骤中假定选择v4 为漏腰，v3 和v2 分别为漏
底。
殊的圈着色
2-色不变圈着色，在此基础上，将
步骤 2 对由漏腰和 2 个漏底构成的三角形
v2v3v4 实施扩 3-轮运算，将新生成的 3 度顶点记作
v5 ，所得结果如图2(a)第2 个图示。
步骤 3 对由漏腰、3 度顶点v5 及一个漏底(满
足：与漏顶v1 距离为2)构成的三角形实施扩3-轮运
算，将新的3 度顶点记作v6 ，所得结果如图2(a)第
3 个图示。
4-色非 Kempe 平面图的 Kempe 等价类分为树型，
圈型和循环圈型，这也是非Kempe 平面图存在的根
源。若一个k -色图的都有k -着色构成一个 Kempe
等价类，则称该图为Kempe 图。
本文给出了一种构造具有相同着色类型的极大
平面图类的方法，包含 334 扩轮运算和 334 缩轮运
算。具体安排如下：第 2 节给出了334 扩轮运算及
334 缩轮运算的定义；第 3 节基于 334 扩缩运算研
步骤 4 对以漏腰v4 为 2-长路的内点，漏顶v1
和新生成的3 度顶点v6 为该路的端点构成的2-长路
实施扩4-轮运算，得到图2(a)最右边所示的构形。
334 扩轮运算的逆运算称为 334 缩轮运算，记
究了一类树型 2-色不变圈着色极大平面图
334-
型极大平面图的基本性质；第4 节讨论了334-型极
大平面图的着色性质；第 5 节给出了用 334 扩轮运
算构造纯树着色极大平面图的方法。
文中未给出的相关定义、记号与理论参见文献
[6,13-15]。
( )
作V ，并把图2(a)–图2(d)中最右边的构形称为V G
的 334 缩轮对象子图，简称为 334 子图。显然，经
过334 扩轮运算后，v1 , v2 , v3 和v4 在V
数均为6。
(
G
)
中的度
注意：(1)在上述334 扩轮运算过程中，若选择v4
作为漏腰，v1 和v2 作为漏底，则得到图2(b)最右边
所示构形；若选择v2 作为漏腰，v3 和v4 作为漏底，
则得到图6(c)最右边所示构形；若选择v2 作为漏腰，
v1 和v4 作为漏底，则得到图2(d)最右边所示构形。
(2)在图2(a)与图2(d)中，2 个最右边构形的区
别仅是构形的内部顶点标号不同，若对一个极大平
面图的同一个45-型子图分别实施如图2(a)和图2(d)
所示过程的 334 扩轮运算，则得到 2 个相同的极大
平面图，故视这2 个构形是相同的；同理，图2(b)
与图2(c)中2 个最右边的构形是相同的。
2 334 扩缩运算
把图 1(a)中所示的图称为漏斗，其中度数为 1
的顶点称为漏顶；度数为 3 的顶点称为漏腰；2 个
度数为 2 的顶点称为漏底。若一个图的顶点导出子
图是漏斗，则该子图称为漏斗子图。334 扩缩运算
本质上是一种多米诺扩缩运算[14]，其中，334 扩轮
运算包含2 次扩3-轮运算以及一次扩4-轮运算；334
缩轮运算包含2次缩3-轮运算以及一次缩4-轮运算。
设G 是一个极大平面图，图H 是一个标号如图1(b)
所示的半封漏斗。若H 是G 的一个子图，且d v
G ( )
=
1
全部评论(0)