关于部分标定简单图的数目

On the Number of Partially Labelled Simple Graphs

摘要: 本文讨论部分标定简单图的数目，首先介绍了计算标定简单图的公式，然后确定了当顶点个数为3时的标定简单图的数目为8个。主要证明了当顶点个数为4时的标定简单图的计数以及所有画法，并用数学方法证明了它的数目的精确值为64。最后也给出当顶点个数为4时，非标定简单图的数目为11个以及全部画法。近百年来，国内外很多学者都对这一问题进行了研究。由于所涉及的画法较多并且证明过程较为复杂，国内外关于此领域的研究进展缓慢。相比较而言，本文给出了四个顶点的标定简单图的所有画法，并采用度序列的方法更简洁直观，更具创新性。

Abstract: In this paper, we discuss the number of partially labelled simple graphs. First, the formula for cal-culating the calibrated simple graphs is introduced. Then, when the number of vertices is 3, the number of calibrated simple graphs is determined to be 8. This paper mainly proves the counting and all the drawing methods of the labeled simple graph when the number of vertices is 4, and mathematically proves that the exact value of its number is 64. Finally, when the number of vertices is 4, the number of uncalibrated simple graphs is 11 and all the drawing methods are given. Over the past century, many scholars at home and abroad have studied this issue. Due to the many drawing methods involved and the complicated proof process, the research progress in this field at home and abroad is slow. In comparison, this paper gives all the drawing methods of the simple graph of the four vertices, and the method of degree sequence is more concise, intuitive and innova-tive.