可k-重图序列的充要条件与实现算法

The Characterizations and Realization Algorithm of Potentially Multi-graphical Sequence

每对顶点之间至多有k条边相连接且无自环的图称为k-重图；一个非负整数序列π=（d1，d2，…，dp）称为可k-重图序列的，如果存在某个k-重图G，使得它的度序列π（G）=π。本文对于可k-重图序列的基本特征进行了较为详细地研究。引入一种称为向量与正整数的减法运算，并对这种运算的基本性质进行了较为详细地研究。在此基础上获得了一个非负整数序列π＝（d1，d2，…dp）是可k-重图的充要条件；进而给出了可k-重图序列实现的一种算法。

The multigraph G is called a k-multigraph if there are at most k edges between each pair of vertices in G.A non-negative integer sequence K = (d1, d2, ..., dp ) is called a potentially k -multi-graph sequence if there is at leastone k-multigraph G such that its degree sequence is K .The some properties of k-multigraphical degree sequence areconsidered by intfoducing a new minus operation between a vector and a natural number. It is given a sufficient and necessarycondition of potentially k -multi-graphical sequence, and furthermore, a realization algorithm of k-multigraphical sequenceis given in this paPer.