پديد آورنده :
صفر پور، طيبه
عنوان :
ابر گراف ها و گراف هاي يالي آنها
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
رياضي كاربردي
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده رياضي
صفحه شمار :
يازده، 96ص: مصورف نمودار
يادداشت :
ص.ع:به فارسي و انگليسي
استاد راهنما :
بهناز عمومي
استاد مشاور :
رامين جوادي
توصيفگر ها :
گراف اشتراك يالي , تجزيه كروز
تاريخ نمايه سازي :
25/09/1392
استاد داور :
عباد اله محموديان، غلامرضا اميدي
چكيده فارسي :
به فارسي وانگليسي: قابل رويت در نسخه ديجيتال
چكيده انگليسي :
Abstract A hypergraph H is called linear if Ei Ej for all Ei Ej E H i j and is called k uniform if all edges have the same cardinality k The line graph L H of a hypergraph H V H E H is a graph that the vertices of L H are in a bijective correspondence with the edge of H and two vertices are adjacent in L H if and only if the corresponding edges have a nonempty intersection hypergraphs are denoted by Lk and Lkl respectively The classes of line graphs of k uniform hypergraphs and linear k uniform let C C Cq be a clique covering of a graph G We say C is linear if any two different cliques in C have no common edges and C is k covering if every vertex of G belongs to at most k cliques from C A linear k covering is also called a Krausz k covering or Krausz k partion or Krausz k decomposition Classes L and L l the line graphs of multigraphs and of simple graphs respectively have been studied for a long time In the classical work of Beineke the class L l is characterized by a finite list of forbidden induced subgraphs such a characterization was independently obtained by Nail Roberson Efficient algorithms for recognizing these classes and constructing the corresponding Krausz type decompositions are also known The situation changes radically if one takes k instead of k Lov sz posed been showed that the recognition problem G Lkl for k is NP complete the problem of characterizing the L and noted that it has no characterization by a finite list of forbidden induced subgraphs a finite characterization It has But the case k is special because in this and only in this situation the restrictions on vertex degrees are essential This follows from the arguments below In Naik et al found a finite list of forbidden induced subgraphs for linear uniform hypergraphs with minimum vertex degree at least Metelsky and Tyshkevich in in and Jacobson et al in in improved this bound to Skums et al in in reduced this bound to also polynomially solvable in class of graphs with minimum vertex degree skums et al in proved that the problem of recognition of the class L l is This thesis contains five chapters Chapter includs an introduction to fundamental definitions In chapter a review on the history of hypergraphs and its related problems are presented Chapter deals with some application of hypergraphs in real world problem In chapter the concept line hypergraphs is introduced In chapter algorithm of recognition of the graph in the class L l is explained PDF created with pdfFactory trial version www pdffactory com
استاد راهنما :
بهناز عمومي
استاد مشاور :
رامين جوادي
استاد داور :
عباد اله محموديان، غلامرضا اميدي
