عنوان پایان‌نامه
خواص گرافهای متقاطر
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 6310;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75974;کتابخانه پردیس علوم شماره ثبت: 6310;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 75974
- تاریخ دفاع
- ۲۹ شهریور ۱۳۹۵
- دانشجو
- فاطمه حاجی
- استاد راهنما
- محمدرضا درفشه
- چکیده
- هدف این پایان‌نامه آشنایی با خواص گرافهای متقاطر است. در این پایان نامه گرافها و گرافهای جهتدار متقاطر را مطالعه می‌کنیم و به بررسی ویژگی‌های این دسته از گرافها می‌پردازیم . سپس به معرفی و دسته بندی گرافهای فاصله منظم می‌پردازیم و برخی از انواع این گرافها از جمله گراف متقاطر فاصله منظم و گرافهای قویاً منظم را تعریف می‌کنیم. در ادامه به معرفی گراف جانسون پیچیده، گراف مثلثی و گراف مکعبی نصف شده‌ی پیچیده می‌پردازیم و مثالهایی از این نوع گرافها ارائه می‌کنیم. سپس فرض می‌کنیم که G یک گراف قویاً منظم غیر دو بخشی با n رأس از درجه k باشد. ثابت می‌کنیم اگر G پوشش متقاطر فاصله منظم با قطر 4 داشته باشد، آنگاه ? ?(2(n+1))/5? kاست. مگر اینکه G مکمل یکی از سه گراف مثلثی T(7) ، گراف جانسون پیچیده J(8,4) یا گراف 8- مکعبی نصف شده‌ی باشد. و سپس بیان می‌کنیم که برای این سه نوع گراف خاص کران بالای k به‌صورت ?(n-1)/2? k ? می‌باشد. این نتیجه حاکی از آن است که تنها یک جفت مکملی از گرافهای قویاً منظم را می‌توان به عنوان خارج قسمت متقاطر گراف فاصله منظم در نظر گرفت.در بخش آخر پایان نامه نیز خانوادهی جدیدی از گرافهای متقاطر فاصله منظم را معرفی می‌کنیم. این خانواده پوشش‌های 2^(2t-1) - لایه‌ای متقاطر از گراف کامل2^2t رأسی هستند. همچنین بعد از معرفی این دسته از گرافها، گروههای خودریختی این گرافها را مشخص می‌کنیم و با استفاده ازگشت‌های موجود در این گرافها کدهای پری‌پاراتا توسیع یافته را بازسازی می‌کنیم.
- Abstract
- The aim of this dissertation is to study the characterization of antipodal graphs. We study antipodal garphs and digraphs in section 1 and 2 of this dissertation. In section 3 ,we define distance-regular graphs and then characterize this kind of garphs. We also define folded Johnson graph, triangular graph and n-cube graph and give examples of this graphs. Then we suppose that G be a non-bipartite strongly regular graph on n vertices of valency k. We prove that if G has a distance-regular antipodal cover of diameter 4, then k ? ?(2(n+1))/5? , unless G is a complement of triangular graph T(7) , the folded Johnson grph J(8,4) or the folded halved 8-cube. However, for these three graphs the bound k ? ?(n-1)/2? holds. This result implies that only one of a complementary pair of strongly regular graphs can be antipodal qoutient of an antipodal distance regular graph. In the end section of this dissertaion, section 4, a new family of distance-regular graphs is constructed. They are antipodal 2^(2t-1)-fold of the complete graph on 2^2t vertices. The automorphism groups are determined, and the extended Preparata codes are reconstructed using walks on these graphs.key words : Antipodal graph, antipodal digraph, antipodal distance regular graph, antipodal covers, strongly regualr graph, quotient graph, Preparata codes.
