The Fully Cycle Extensibility Of K_1,4-restricted Graphs And Methods For Ranking In Multi-attribute Decision-making

Graph theory is an important research method which uses graphs toanalysize the problems, and it is widely used in the scientific research .Multiple attribute decision making is an important one in the conplicatedresearching system. It not only has the applying prospect, but also hashighly theorical value. The thesis is mainly about the two questions inthe the fully cycle extensibility of K1,4-restricted graphs and two resultson multiple attribute decision making, and it is divided into three parts:The first chapter includes two sections, and the first section includessome of terminology and notation, the simple but very importantK1,p-restricted graghs, and the researching background of this section,andthe achieved results.Theorem 1.1 K_1,p-restricted graghs should be K1,p+1-restricted graghs.From theorem 1.1 we can easily see that K1,p-restricted graghs whichis studied in this thesis cantains claw-free graph.Theorem 1.2, Every connected, locally connected claw-free graphon at least three vertices is fully cycle extensible.Theorem 1.3 Suppose G is a connected, locally connected almostclaw-free graph G on at least three vertices. If G does not contain anyinduced subgraph that is isomorphic to K 1,4, then G is fully cycleextensible.Theorem 1.4[16] Every connected,almost locally connectedquasi-claw-free graph on at least three vertices is fully cycle extendable.Theorem 1.5[17] Every connected, locally connected K 2 ∨K2-free K1,4–confined graph on at least three vertices is fully cycle extendable.The second section shows the result of this chapter and itsidentification:Theorem 1.6 It is shown that every a connected,locally connected K1,4–restricted graph with δ ≥3 is fully cycle extendable.And the example shows that the condition of " δ ≥3" is sharp in thetheorem of K1,4–restricted graph. When δ ≥3,Theorem 1.1[17] can easily showthat theorem 1.6 is the generalization of Theorem 1.5[17], and at the sametime gives the graph that satisfy Theorem 1.6's condition but not thecondition of Theorem 1.3[11].As another science branch science of Operation Research ,controltheory studies quantitive analysis methods of decision making under riskyor uncertain situations. The core of its solution is to decide the rankingamong alternatives after evaluation, and choose the best. The secondchapter and the third chapter of this paper will mainly discuss thealgorithm ranking in multi-attribute decision making problems in thefollowing situations.Currently, there are lots of solutions to the multi-attribute decisionmaking problems with all the information about weights or without anyinformation about weights. Therefore, researchers are very interested inthe case when the weights information is only partly available. Article[33]gave a algorighm ranking method under weak index ordering. The secondchapter of this paper will study algorighm ranking methods under strongindex ordering with preferences among algorighms.With strong indices ordering ,we can construct a decision moder asthe following:min H (W)= C1W1+C2W2+CnWnBy analytic calculation,we can solve the weights Wj in the linearprogram problem above. we can complete our ranking work just by calculatingthe subjective expectation value E (Xi )=∑=njaijWij1for each alternative Xi.This method includes the situatian of weak index ordering, on the otherhand ,it also considers the active attending of the other reseachers inorder to let the decision making more reasonable.This capter gives the analysis of the example.The TOPSIS method is an effective multi-attributedecision-making.Article [19] gives us the vivid process of calculatingmethod, and then, article [34] makes further discussions about it. But allthis methods are analysised under the conditions of indices weights andattributes. However, due to the effects of many factors such as thecomplexity of the subjects and incompleteness of decision-makinginformation. It is very difficult to determine all the indices value foreach alternative or to objectively decide the weights for each index. Butit will be relatively easier if we only need to give them a proper interval.Therefore, the reseach of interval value decision-making has the important???????≥=≥?≥=?+++=?0(1,2,,)(1,2,,1)1. .112WjnWMWWMjnWWWstjnnjjjntheorical and applying value.the third chapter mainly discusses that theindices weight and attributs can't be completely defined but can be definedits multiple attribute decision making in its interval valuedecision-making, also, gives the actions ranking theory and method on thebasis of traditional TOPSIS.Define the ideal solution and negative ideal solution as following:Compute the weighted distance [ S i? ,Si+] between the decisionalternatves and the ideal solution, and the weighted distance [ Di ? ,Di+]between alternatives and the negative ideal solution.Using the relative closeness interval [ e i? ,ei+] between alternativesand negative ideal solution,we construct a preference degree comparisonmatrix P, and therefore depict the value of different alternative andcomplete the ranking.This capter also gives the analysis of the example.x+ = { m1 ≤ia ≤xmai+1,m1≤ia≤xmai+m}={a1+,an+}x? = {1 m≤ ii ≤nmai?1,1m≤ii≤nmai?m}={a1?,an?}...