共查询到17条相似文献,搜索用时 62 毫秒
1.
本文讨论了2-重自补图和有向自补图的连通性以及2-重自补图的直径,同时以自补置换作为工具研究了当2-重自补图或有向自补图被分成两个连通分支后,这两个连通分支之间的边数与顶点数之间的关系. 相似文献
2.
3.
本文通过对自补图的4阶和5阶自补子图个数的讨论,给出了两类自补图同构的必要条件。在文章的最后讨论了将这些条件扩充成为自补图同构判断的充要条件的可行性。 相似文献
4.
5.
龙安国 《西安理工大学学报》1994,10(3):174-177
提出并证明了几个自补图的构造命题,探讨了自补图的构造方法。完成了9个点以内的所有自补图构图,并对12个点的自补图的构图进行了初步探讨。 相似文献
6.
王自果 《陕西理工学院学报(自然科学版)》1992,(1)
本文利用自补图的性质和自补图的构造方法证明了阶数 p=5,8、9的所有自补图的周长最大的为 p,最小的为 p—2,它们完全由自补图的度序列和自补图的构造所确定。 相似文献
7.
8.
9.
蓝开允 《四川大学学报(自然科学版)》1990,27(3):293-296
研究了非平凡自补图,给出了自补图的最大度与最小度的关系,提出了自补图连通度的公式.上述两项结论,以4阶图和5阶图为例,进行了分析讨论. 相似文献
10.
Read在1963年就算出5个顶点的有向自补图共有136个,但这些图一直未被全部构造出来,本文应用2-重自补图的结果,构造出了136个有向自补图. 相似文献
11.
利用度序列的概念,证明变换图G~(--+)与H_n~(--+)同构,当且仅当G与_n同构.以及在G连通的条件下,G~(--+)与C_n~(--+)同构,当且仅当G与_n同构. 相似文献
12.
ResearchonDNAcomputingwasinitializedin1994 ,whenAdleman[1] proposedamethodofsolvingasmallinstanceoftheHamiltonianPathproblembyalaboratoryexperimentinvolvingDNAmolecules .Later,Lipton[2 ] demonstratedhowalargeclassofNP completeproblemscouldbesolvedbyencodingtheprobleminDNAmolecules .Inparticular ,LiptonshowedonefamousNP problem ,theso called“satisfiability”problem (SAT)andsubsequentlytheotherNP problemscouldbeencodedandsolvedusingmolecules .TheadvantagesofDNAcomputingareitsmassivepa… 相似文献
13.
An algorithm for solving the graph isomorphism problem with 3-D DNA structures is proposed in this paper. The karmed branched junction molecules are used to code k-degree vertices. Double stranded molecules are used to code edges. Then the molecules are mixed in a tube to be ligated. The result can be detected by gel electrophoresis. The time complexity of the algorithm is O(n2), where n is the number of vertices of the graph. 相似文献
14.
关于不含3正则子图图的最大边数 总被引:1,自引:1,他引:0
对无自环、无重边的简单图,Erdos和Saucer在1974年提出如下问题:设 f(p) 是p个顶点的不含3正则子图图的最大可能边数,确定f(p).本文对p ≥4、4≤p≤40给出了f(p)的下界,对4p刁≤16给出了f(p)的值,并对4≤p ≤15得出了所有的极图. 相似文献
15.
通过剖析4n阶和4n+1阶自补图之间的关系,应用度序列的方法,以4n阶自补图为基础,给出了构造4n+1阶自补图的递推方法。 相似文献
16.
Hongbing Fan 《科学通报(英文版)》1998,43(2):99-99
An edge e of a graph G is called a fixed edge if G-e+e′ G implies e′=e, and an isomorphic fixed edge if G-e+e′ G implies that there exists an automorphism of G-e, which maps the ends of e to the ends of e′. It is proved that almost every graph is with all its edges as fixed edges and isomorphic fixed edges, and it is conjectured that all graphs contain isomorphic fixed edges. 相似文献
17.
LIQing-hua ZHANGZhi-xiang BENKe-rong 《武汉大学学报:自然科学英文版》2004,9(4):444-448
The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decom-posed into subgraphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. 相似文献