恰有d个顶点带环的本原有向图的公共后继的界

华南理工大学学报（自然科学版） ›› 2005, Vol. 33 ›› Issue (7): 101-104.

• • 上一篇

恰有d个顶点带环的本原有向图的公共后继的界

陈小亘彭宏

华南理工大学计算机科学与工程学院，广东广州 510640

收稿日期:2004-10-13 出版日期:2005-07-25 发布日期:2005-07-25
通信作者: 陈小亘(1964-)，男，讲师，在职硕士生，现任职于湛江师范学院，主要从事图论和计算机科学的研究 E-mail:oamc@ 163.com
作者简介:陈小亘(1964-)，男，讲师，在职硕士生，现任职于湛江师范学院，主要从事图论和计算机科学的研究
基金资助:
国家自然科学基金资助项目(10261003)；广东省科技攻关项目(A10210200)；广州市科技攻关项目(2004Z-D0091)

Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop

Chen Xiao-gen Peng Hong

College of Computer Science and Engineering,South China Univ,of Tech.,Guangzhou 510640,Guangdong,China

Received:2004-10-13 Online:2005-07-25 Published:2005-07-25
Contact: Chen Xiao—gen(bom in 1964)，male，lecturer，master candidate in—service，now works at Zhanjiang Normal University，mainly researches Oil graph theory and computa—tional science E-mail:oamc@ 163.com
About author:Chen Xiao—gen(bom in 1964)，male，lecturer，master candidate in—service，now works at Zhanjiang Normal University，mainly researches Oil graph theory and computa—tional science
Supported by:
Suppo rted by the National Natural Science Foundation of China(10261003)，the Key Technologies R&D Program of Guangdong Province(A10210200)and the Key Technologies R&D Program of Guangzhou(2004Z一130091)

摘要/Abstract

摘要： 如果存在正整数P，使有向图G中任一有序顶点对u和ν都有长为P的途径，则有向图G称为本原有向图．设P_n(d)是n(n≥3)阶恰有d个顶点带环的本原有向图的集合，L_G(k) 是本原有向图G的k-公共后继 (k-c,c.)，2≤k≤n；又设L(n,d ,k)=max{L_G(k)| G ∈ P_n (d)}，由此得到了k-公共后继的界：n-「d/2」≤L (n,d,k)≤n-1,1≤d≤n。

关键词: 布尔矩阵, 公共后继, 本原有向图

Abstract:

A digraph G is said to be primitive if there exists a positive integer P such that for each ordered pair of vertices u and ν ,there is a walk oflength P from u to v.Let P_n(d) be the set ofall primitive digraphs oforder n(n≥3)with exact d vertices having loops,L_G(k) be the k-common consequent (k-c,c.)of primitive digraph G,2≤k≤n,and L(n,d ,k)=max{L_G(k)| G ∈ P_n (d)},In this paper,the bound of k-common consequent,namely,n-「d/2」≤L (n,d,k)≤n-1,1≤d≤n,is obtained.

Key words: Boolean matrix, common consequent, primitive digraph

陈小亘彭宏. 恰有d个顶点带环的本原有向图的公共后继的界[J]. 华南理工大学学报（自然科学版）, 2005, 33(7): 101-104.

Chen Xiao-gen Peng Hong. Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop[J]. Journal of South China University of Technology (Natural Science Edition), 2005, 33(7): 101-104.

[1]	陈兴蜀张帅童浩崔晓靖. 基于布尔矩阵和 MapReduce 的 FP-Growth 算法[J]. 华南理工大学学报（自然科学版）, 2014, 42(1): 135-141.
[2]	庄晓琼. 一类非本原有向图第κ个顶点指数集[J]. 华南理工大学学报(自然科学版), 2004, 32(6): 85-88,92.

恰有d个顶点带环的本原有向图的公共后继的界

Bound of Common Consequent of Primitive Digraphs with Exact d Vertices Having Loop

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价