عنوان پایان‌نامه
G - گراف گروههای متناهی
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 6311;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 76125;کتابخانه پردیس علوم شماره ثبت: 6311;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 76125
- تاریخ دفاع
- ۲۹ شهریور ۱۳۹۵
- دانشجو
- صفورا مددی مقدم
- استاد راهنما
- محمدرضا درفشه
- چکیده
-
ارتباط گروه و گراف یکی از شاخه‌های معروف و پر محصول نظریه جبری گراف است. یکی از مشهورترین این ارتباطات ساختن گراف کیلی با استفاده از ساختار یک گروه است. این گراف‌ها اولین بار توسط آرتور کیلی در سال 1878 تعریف شد. برای گروه G و زیرمجموعه ی S ?? G که عنصر همانی داخل S نیست، گراف کیلی Cay(G,S) ، گرافی است با مجموعه رئوس Gوx, y ? G توسط یال جهتدار (x,y) به هم وصل هستند اگر و تنها اگر s ? S وجود داشته باشد به طوریکه y = sx . در حالتیکه S¯¹ = S گراف کیلی در واقع تبدیل به یک گراف ساده می‌شود، گراف بدون طوقه و جهت.
در سال 2007 ،G -گراف توسط اَلِین برتو و اَلِین فِیسنت تعریف شد و خواص و کاربرد‌های زیادی از آن ارائه شد. این نویسندگان ثابت کردند که G-گراف درواقع تعمیمی برای گراف کیلی است. نحوه ی ساخت G-گراف ? (G,S) به این ترتیب است که فرض کنید G گروهی متناهی از مرتبه‌ی n و S زیرمجموعه‌ای ناتهی از آن باشد. برای هر s ? S نگاشت gs : G ? G را اینگونه تعریف می کنیم که برای هر G ? x ،
gs(x) = sx. فرض کنید Ts مجموعه‌ی همه‌ی x ? G باشد که {
x | x ? Ts}دقیقا مجموعه‌ی همه‌ی همدسته‌های راست گروه < s > باشد، آنگاه دور‌های حاصل از gs به صورت زیر است : {(x , sx , s²x , . . . , s°???¯¹) | x ? Ts} هر دور (x , sx , s²x , . . . , s°???¯¹) را به صورت (s)xنمایش می دهیم. هرgs ، دارای (o(G))/(o(s)) دور به طول o(s) است. حال مجموعه رئوس(G,S) ?، مجموعه‌ی همه‌ی دور‌های موجود درgs ، به ازای همه‌ی s های داخل S است، و دو راس (s)x و (t)y توسط p یال به هم متصل هستند اگر و تنها اگر = p | (s)x? (t)y | . اگر طوقه‌ها را حذف کنیم، G-گراف حاصل را با¯(?(G,S) ) نمایش می‌دهیم. همچنین اگر شرط وجود یال را به0 ?| (s)x? (t)y | محدود کنیم، گرافی ساده به دست می‌آید که آن را با ?(G,S) نمایش می‌دهیم. در این رساله خواص زیادی از جمله خواص زیر را برای G-گراف ?(G,S) ثابت می‌کنیم : 1- اگر= k | S | باشد، آنگاه (G,S) ? یک گراف k بخشی است. 2- اگر k عددی فرد باشد، آنگاه (G,S) ? گرافی اویلری است. 3- (G,S) ? گرافی همبند است اگر وتنها اگر S مجموعه مولدی برای گروه G باشد. مفاهیم زیادی مشابه مفاهیم موجود برای گراف‌های کیلی، برای G-گراف‌ها نیز قابل تعریف است. از جمله همریختی و خودریختی‌های G-گراف (G,S) ?و همچنین گروه خودریختی‌های (G,S)) Aut(?. در این رساله بخشی از این مفاهیم را معرفی و بررسی می‌کنیم. همچنین گروههای معین Gرا در نظر گرفته و نسبت به مجموعه‌ی مولد S ، G-گراف(G,S) ? را می‌سازیم و خواص این گراف از جمله همیلتونی و اویلری بودن آن را بررسی می‌کنیم. - Abstract
- The relation between groups and graphs is one of the productive area of research in algebraic graph theory. One of these connections is the construction of Caley graphs using group structure. This graph for the first time was introduced by Arthur Caley in 1878. For a group G and a non-empty subset S of G such that S has not 1, The Caley graph Cay(G,S) is a graph with vertex set G in which the vertex x is joined to y iff y=sx for some s ? S . If S is chosen such that S=S?¹ , Then Cay(G,S) is a simple graph. The notion of G-graph was introduced by Alain Bretto and Alain Faisant in 2007 and they proved several properties and applications of G-graphs. They proved G-graph is a generalized of Cayley graph. The construction of the G-graph ?(G,S) is as follows : Let G be a group of order n and S is a non-empty subset of G. For s ? S the mapping gs : G ? G is defined by gs(x)=sx, where x ? G . Suppose Ts consists of all x ? G such that {< s > x | x ? Ts } is the set of all the right cosets of < s > in G, then the cycles in the permutation gs is of the form {(x , sx , s²x , . . . , s°????¹x) | x ? Ts }. For convince we write (s)x=(x , sx , s²x , . . , s°????¹x). Each gs has (o(G))/(o(s)) cycles of length o(s) . Then the vertex set of ?(G,S) is the set of all the cycles in gs for all s ? S, and two vertices (s)x and (t)y are joined by p edges iff | (s)x ? (t)y | = p. If we don't allow the loops, this G-graph is denotes by ¯(?(G,S)), and if the condition for the edge is changes to | (s)x ? (t)y | ?0, the resulting graph is simple and is denotes by ?(G,S). In this thesis many properties of G-graphs is proved. To mention a few let ?(G,S) be a graph, then :If | S | = k $, then ?(G,S) is a k-partite graph. If | S | = k $, k an odd number, then ?(G,S) is an Eulerian graph. ?(G,S) is a connected graph iff S is a generating set for G.Similar concepts as for the Cayley graphs can be defined for the G-graphs, such as homomorphisms and automorphisms of the G-graph ?(G,S). In this thesis we also consider certain groups G with subset S and construct the G-graph ?(G,S) and prove the Hamiltonicity and Eulerian of ?(G,S).Keywords: Cayley graphs, G-graphs, Cosets, Simple graphs, k-partite graphs, Connected graphs, Homorphisms, Automorphisms, Hamiltonicity, Eulerian.
