-
题名完全图k_7上欧拉链和欧拉闭链的计数
- 1
-
-
作者
温一新
-
机构
兰州大学数学系
-
出处
《新疆大学学报(自然科学版)》
CAS
1989年第2期17-23,共7页
-
文摘
文[1]提出了 K_(2n+1)上有多少条欧拉链的计数问题,其中已知 K_3 上有一条欧拉链,K_5 上有22条欧拉链,对于 K_(2n+1)(n≥3)上有多少条欧拉链的计数问题没有解决.本文计算出 K_7 上的欧拉链的数目为541568条,在此基础上又计算出 K_7 上的欧拉闭链的数目为180544条,并估计出 K_(2n+1)(n≥4)上欧拉链的数目的一个上界.
-
关键词
完全图
欧拉链
计数
闭链
-
Keywords
complete graph
Euler trail
enumeration
-
分类号
O157.5
[理学—基础数学]
-
-
题名一类树问题的快速并行算法
- 2
-
-
作者
马绍汉
孙伟
-
机构
山东大学计算机科学系
-
出处
《山东大学学报(理学版)》
CAS
CSCD
1991年第1期41-53,共13页
-
基金
国家自然科学基金
-
文摘
本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.
-
关键词
树
有向树
欧拉链技术
并行算法
NC类
-
Keywords
tree
directed tree
Euler list technique
parallel algorithms
NC class
-
分类号
N
[自然科学总论]
-