全球研究计算机科学杂志》上
菜单石头:2229 - 371 x
石头:2229 - 371 x
|
访问更多的相关文章全球研究计算机科学杂志》上
A sequence of nonnegative integers can represent degrees of a graph G and for the graph H. there may be many different 1-to-1 or 1-to-many mapping functions by which G can be mapped into H. That is it is feasible to construct isomorphic or regular or connected or disconnected graphs. Finding connectedness of a graph from degree sequence is analogues to Reconstruction Conjecture problem. It is our intention in this paper to infer about the connectedness of the graph only from the degree sequence and no need of any other information. It is evident that there is no unique conclusion about the connectedness of a given graph from the algorithm we project here. However, we can say that whether the sequence represents a connected or disconnected graph.
关键字 |
| 图像序列、连通性、正则图,图同构,重建猜想 |
介绍 |
| 一个序列x = d1、d2、d3…。,dn of nonnegative integers is called a degree sequence of given graph G if the vertices of G can be labeled V1, V2, V3, …, Vn so that degree Vi = di; for all i=1,2,3,…..n [2]. For a given graph G, a degree sequence of G can be easily determined [1]. Now the question arise, given a sequence x = d1, d2, d3, …, dn of nonnegative integers, then under what conditions does there exist a graph G. A necessary and sufficient condition for a sequence to be graphical was found by Havel and later rediscovered by Hakimi [1,2]. As a sequel of this another question arises, if the sequence x = d1, d2, d3, …, dn, be a graphic sequence then is there any condition for which we can say that x represents a connected or disconnected Graph sequence[4,5,6,7,8]. |
预赛 |
| 定义1:序列x = d1、d2、d3…, dn的非负整数是图形序列如果存在一个图G的顶点度di和G称为实现x [1]。 |
| 定义2:对于任何图G,我们定义 |
| d (G) =分钟{度(v) |我v (G)} |
 |
 |
 |
 |
| 一个图形,但B不是图形。那么x不能代表任何断开连接的序列。这是真的为θ图。 |
目前,业主 |
| 重建猜想,每一个有限的简单的对称图形,三个或三个以上顶点是坚决的,由其集群的诱导子图同构,[5]。猜想是第一个发明于1941年,有许多相关的问题。 |
结论 |
| 我们提出的算法识别给定的图形序列代表任何连接或断开连接图序列。任意两个同构图形代表了完全相同的序列。然而,反过来不是真正的[1]。提出的定理和标准实际上决定了,如果给定的图像序列是拆卸序列或序列或至少一个序列图可以可能(这是连接或断开连接)。 |
引用 |
|