摘要
π为非负整数序列 ,若存在以该序列为度序列的图 ,则称 π为可图的 .特别的 ,若此图是一个定向图 ,该序列则称为是定向可图的 .本文提出了一个判断序列是否为定向可图的充分必要条件 。
A sequence π of nonnegative integers is said to be graphic if there is a graph whose degree sequence is π. Especially, if such graph is an oriented graph, the sequence is said to be oriented graphic. In this paper, we provide a sufficient and necessary condition to judge whether a sequence is oriented graphic. Furthermore, in the proof of the theorem, an algorithm is provided to construct the oriented graph with the given degree sequence when a certain pair of adjacency matrices has been found.
出处
《数学研究》
CSCD
2002年第2期140-146,共7页
Journal of Mathematical Study
基金
Project supported by the National Natural Secience Foundatons of China(Grant No.199710 86 ) and the Doctoral Program Foundation of National Education Department ofChina
关键词
定向可图
度(偶)序列
定向图
graph realization
degree sequence
oriented graph
