【作者】 赵光峰；

【导师】 徐扬；

【作者基本信息】 西南交通大学 ， 交通信息工程及控制， 2002， 博士

【摘要】 格蕴涵代数与图论是两个与人工智能及智能信息处理密切相关的数学分支。格蕴涵代数为格值逻辑与不确定性推理的研究提供了一种理论基础。Alavi猜想是图论中1987年提出的一个关于图的升分解问题的猜想，至今尚未得到证明。与图论中的其它问题一样，对图的升分解问题的构造式证明本质上是寻找一种解决可以抽象为图的升分解问题的一类实际应用问题的算法，因此，关于图的升分解问题的研究工作对利用计算机解决这类实际问题具有现实意义。 本文围绕格蕴涵代数与图论中的Aalvi猜想作了一些研究工作并取得了以下结果。 1．研究了格蕴涵代数的公理体系，给出了一组在没有任何代数结构的集合上建立格蕴涵代数的等价公理。 2．证明了利用格蕴涵代数上的一个模糊滤子可以得到格蕴涵代数上的一簇同余关系，证明了这簇同余关系构成一个完备链，在此基础上讨论了这簇同余关系诱导的格蕴涵商代数之间的关系，并用一个例子说明了这簇同余关系的确可以包含更多的同余关系。 3．对模糊LI-理想的性质作了进一步的研究，证明了利用格蕴涵代数上的一个模糊LI-理想可以得到格蕴涵代数上的一簇同余关系，证明了这簇同余关系构成一个完备链，在此基础上讨论了这簇同余关系诱导的格蕴涵商代数之间的关系，并用一个例子说明了这簇同余关系的确可以包含更多的同余关系。 4．讨论了模糊滤子与模糊LI-理想之间的关系。 5．提出了格蕴涵代数的关联理想的概念，讨论了它的性质，指出了关联理想与LI-理想、关联理想与关联滤子之间的关系。 6．提出了格蕴涵代数的模糊关联理想的概念，讨论了模糊关联理想的性质，指出了模糊关联理想与关联理想、模糊关联理想与模糊关联滤子、模糊关联理想与模糊LI-理想之间的关系。 7．给出了L-型模糊子格蕴涵代数的概念并讨论它的一些性质。 8．提出了L-型模糊滤子和L-型模糊理想的概念并讨论了它们的基本性质及它们之间的关系。 9．提出了格蕴涵代数的L-型模糊关联滤子的概念，讨论了L-型模糊关联滤子的性质，指出了L-型模糊关联滤子与关联滤子、L-型模糊关联滤子与L-型模糊滤子的关系。 n 西南交通大学研究生搏士学位论文 川．提出了格蕴涵代数的L－型模糊关联理想的概念，讨论了L－型模糊关 联理想的性质，指出了L－型模糊关联理想与关联理想、L－型模糊关联理想与 L－型模糊关联滤子、L－型模糊关联理想与L－型模糊理想之间的关系． 11．当 n阶完全图凡的子图 H的边数小于了时Kn—H有星升分解· 12．引进了慧星的概念并证明了以下结果． （ 1）设 n 3 2，wo，wl，…；w＊一＊是 Kn的 n一 1个不同的顶点，那么 Kn有慧 星升分解： 比CI，…，C．2，使得w。，wl；…，ln．2分别是 CO，CI，…，CnZ的中心 （2）设。。33，如果Hn＊的边数是1。一乙则Kn—Hnl有慧星升分解： q，CI；…，民－。，G－3，且适当指定 CO，CI和 CZ的中心后可以使这些慧星的中心各不相同． 山设 H是＊阶完全图凡的一个子图．则当 n 3 7，H的边数为 2，。一3时，N—H可以升分解为 SI，h，兄冯，…；c－5，C．4；其中C3，…，Cn－5，Cn－4的中心各不相同． 问设H是n阶完全图凡的一个子图·则当n＞6，e（川＜了一4时，Im—H可以分解为 GI，GZ，…。G。－4 U R；其中，当 6 ＜ 3时，G。2 S；当 6＞3时，G；2 C1，并且在这个分解中任何两个慧星O＞3时的子图）的中心都不相同．更多还原

【Abstract】 The lattice implication algebra and the graph theory are two branches of mathematics which offer the basic surport for the theory and application of artificial intelligence and intelligent information processing. The lattice implication algebra is a theoretical basis for the theory of lattice valued logic and approximate reasoning. In 1987,Alavi and others conjectured that every graph with positive size has an ascending subgraph decomposition. This conjecture is an unsolved problem in graph theory.This thesis contains the author’s research work on the lattice implication algebra and the Alavi Conjecture. Following are the main works contained in this thesis.1. Studied the axioms of lattice implication algebra,the axioms which can construct a lattice implication algebra on a set without any algebraic structure were given.2. Pointed out a family of congruence relations induced by a fuzzy filter of a lattice implication algebra and proved that this family of congruence relations is a complete chain,and then discussed the relations between the quotient lattice implication algebras induced by this family of congruence relations.3. Discussed the property of fuzzy LI-ideals,pointed out a family of congruence relations induced by a fuzzy LI-ideal of a lattice implication algebra and proved that this family of congruence relations is a complete chain,and then discussed the relations between the quotient lattice implication algebras induced by this family of congruence relations.4. Determined the relation between fuzzy filter and fuzzy LI-ideal.5. Proposed the concept of associative ideal of a lattice implication algebra,discussed the property of associative ideal,pointed out the relation between associative ideal and LI-ideal and the relation between associative ideal and associative filter.6. Proposed the concept of fuzzy associative ideal of lattice implication algebras,studied the the properties of fuzzy associative ideal,discussed the relations between fuzzy associative ideal and associative ideal,between fuzzy associative ideal and fuzzy associative filter and between fuzzy associative ideal and fuzzy LI-ideal.7. Introduced the concept of L-fuzzylattice implication algebra and discussed it’s properties.8. Proposed the concepts of L-fuzzyfilter and L-fuzzyideal of lattice implication algebra and investigated their properties and the relation between them.9. Proposed the concepts of L-fuzzyassociative filter,discussed it’s properties andthe relations between L-fuzzyassociative filter and associative filter and between filter and L-fuzzyassociative filter.10. Proposed the concepts of L-fuzzyassociative ideal,discussed it’s properties and the relations between L-fuzzyassociative ideal and associative ideal,between L-fuzzyassociative ideal and L/-ideal,and between L-fuzzyassociative filter and L-fuzzyassociative ideal.11. Proved that Kn - H has an ascending star decomposition when the size of H is less than 4p,where H is a subgraph of the complete graph Kn.12. Proposed the concept of comic and proved the following theorems by using comic.(1) Let w0,w1....wn-2 is n-1 different vertices of Kn,if n 2 then Kn has an ascending comic decompositionsuch that w0,w1.....wn-2 is the centers of the comics C0,C1,...,Cn-2 respectively.(2) Let n 3. if the size of Hn-1 is n - 1 then Kn - Hn-1 has an ascending comic decompositionsuch that the centers of any two of these comics are different when choose a convenient center for each one of the comics C0,C1 and C2.(3) Let H is a subgrpah of the complete graph Kn with order n. If n 7 and the size of H is In - 3 then Kn - H can be decomposed intoand the centers of any two of the comics C3,...,Cn-5,Cn-4 are different.(4) Let H is a subgrpah of the complete graph Kn with order n. If n 6 and e(H) <- 4 then Kn - H can be decomposed into subgraphswhere Gi = 5,when i 3 and Gi = Ci~ when i > 3,and the centers of any two comics in the decomposition are different.更多还原