ریاضیات

از ویکیپدیا، دانشنامه آزاد

در نظریه گراف ، یک گراف مور است نمودار به طور منظم از درجه D و قطر K که تعداد رئوس برابر کران بالا

یک تعریف معادل از نمودار مور این است که نمودار نمودار باشد با دور شدن . تعریف معادل دیگری از نمودار مور این است که آن را محکم است  و دقیقاً  چرخه های طول ، جایی که  و به ترتیب تعداد رئوس و لبه های . در واقع با توجه به تعداد چرخه هایی که طول آنها گراف است ، افراطی هستند. [1]

نمودار مور توسط نام برده شد هافمن و سینگلتون (1960) بعد از ادوارد اف مور ، که این سوال را از توصیف و طبقه بندی این نمودار را مطرح کرد.

نمودارهای مور علاوه بر داشتن حداکثر تعداد راس ممکن برای یک ترکیب معین از درجه و قطر ، دارای حداقل تعداد راس ممکن برای یک نمودار منظم با درجه و دور مشخص شده هستند. یعنی هر نمودار مور یک قفس است . [2] فرمول تعداد رأس در نمودار مور را می توان تعمیم داد تا بتوان تعریفی از نمودارهای مور با یکدست و همچنین دور فرد را ارائه داد و دوباره این نمودارها قفس هستند.

فهرست

• 1رئوس محدود شده بر حسب درجه و قطر
• 2مور به عنوان قفس نمودار می شود
• 3مثال ها
• 4همچنین ببینید
• 5یادداشت
• 6منابع
• 7لینک های خارجی

رئوس محدود بر اساس درجه و قطر [ ویرایش ]

پترسن گراف به عنوان یک گراف مور. هر درخت جستجو برای اولین بار دارای d ( d -1) i رأس در سطح I است.

بگذارید G هر نمودار با حداکثر درجه d و قطر k باشد ، و درختی را که با جستجو در وسعت تشکیل شده است در نظر بگیرید که از هر راس v شروع می شود . این درخت دارای 1 راس در سطح 0 ( خود v ) و حداکثر d رئوس در سطح 1 (همسایگان v ) است. در سطح بعدی ، حداکثر رئوس d ( d -1) وجود دارد: هر همسایه v از یکی از مجاورتهای خود برای اتصال به v استفاده می کند و بنابراین می تواند حداکثر d -1 همسایه در سطح 2 داشته باشد. به طور کلی ، یک استدلال مشابه نشان می دهد که در هر سطح 1 ≤ من ≤K ، وجود دارد می توانید حداکثر باشد د ( د -1) من راس. بنابراین ، تعداد کل رئوس می تواند حداکثر باشد

هافمن و سینگلتون (1960) در ابتدا نمودار مور را به عنوان گرافی تعریف كردند كه این محدوده به تعداد رئوس دقیقاً برای آن برآورده می شود. بنابراین ، هر نمودار مور دارای حداکثر رأس های ممکن در میان تمام نمودارها با حداکثر درجه d و قطر k است .

بعداً ، سینگلتون (1968) نشان داد كه نمودارهای مور را می توان به طور معادل با قطر k و اندازه 2k + 1 تعریف كرد . این دو مورد نیاز ترکیب را به زور از نمودار به د به طور منظم برای برخی از د و برای برآوردن به فرمول راس شمارش.

نمودارهای مور به عنوان قفس [ ویرایش ]

به جای اینکه از نظر حداکثر درجه و قطر آن ، تعداد راس های یک نمودار محدود شود ، می توانیم از طریق روش های مشابه ، یک حد پایین تر از تعداد رئوس از نظر حداقل درجه و دور آن محاسبه کنیم . [2] فرض کنید G دارای حداقل مدرک د و دور 2 K 1. خودسرانه یک راس ابتدایی v را انتخاب کنید ، و مانند قبل درخت جستجوی گسترده ای را که در v ریشه دارد ، در نظر بگیرید. این درخت باید یک راس در سطح 0 داشته باشد ( v خودش) و حداقل d رئوس در سطح 1 باشد. در سطح 2 (برای k > 1) ، حداقل باید d ( d باشد)-1) رئوس ، زیرا هر راس در سطح 1 حداقل d -1 مجاورت باقیمانده برای پر کردن دارد ، و هیچ دو راس در سطح 1 نمی تواند مجاور یکدیگر باشد یا یک راس مشترک در سطح 2 باشد زیرا این یک چرخه کوتاه تر ایجاد می کند از حد فرض به طور کلی ، یک استدلال مشابه نشان می دهد که در هر سطح 1 ≤ i ≤ k ، باید حداقل d ( d -1) i رئوس وجود داشته باشد. بنابراین ، تعداد کل رئوس باید حداقل باشد

در نمودار مور ، این محدوده به تعداد رئوس دقیقاً برآورده می شود. هر نمودار مور دور دقیقا 2 K 1: آن رئوس به اندازه کافی نیست که به دور بالاتر و چرخه های کوتاه تر باعث می شود بیش از حد چند راس در اول وجود دارد ک سطح برخی از اولین درخت جستجوی سطح. بنابراین ، هر نمودار مور دارای حداقل رئوس ممکن در میان تمام نمودارهای دارای حداقل درجه d و قطر k است : این یک قفس است .

حتی برای مسافت 2 کیلو، می توان به طور مشابه یک درخت جستجو در اولین عرض از نقطه میانی یک لبه ایجاد کرد. در نتیجه در حداقل تعداد رئوس در یک نمودار از این دور که با حداقل درجه D است

(سمت راست فرمول بجای آن تعداد رئوس درخت جستجوی گسترده ای را که از یک راس واحد شروع می شود ، محاسبه می کند ، این احتمال را دارد که یک راس در آخرین سطح درخت مجاور d رئوس سطح قبلی باشد .) بنابراین ، نمودارهای مور گاهی اوقات به عنوان نمودارهایی تعریف می شوند که دقیقاً با این حد مطابقت دارند. باز هم ، هر نمودار چنین باید قفس باشد.

مثالها [ ویرایش ]

در قضیه هافمن - سینگلتون بیان شده است كه هر نمودار مور با گوزن 5 باید دارای درجه 2 ، 3 ، 7 یا 57 باشد. نمودارهای مور عبارتند از: [3]

• گرافهای کامل  در n> 2 گره (قطر 1 ، گوزن 3 ، درجه n-1 ، سفارش n)
• چرخه های عجیب و غریب  (قطر n ، محفظه 2n + 1 ، درجه 2 ، سفارش 2n + 1)
• گراف پترسن (قطر 2، دور 5، درجه 3، سفارش 10)
• نمودار هافمن - سینگلتون (قطر 2 ، دور 5 ، درجه 7 ، سفارش 50)
• یک نمودار فرضی با قطر 2 ، گوزن 5 ، درجه 57 و نظم 3250 ، که وجود آن ناشناخته است [4]

اگرچه تمام نمودارهای شناخته شده مور نمودارهای انتقالی-راس هستند ، اما ناشناخته (در صورت وجود) نمی تواند راس-انتقالی باشد ، زیرا گروه اتومورفیسم آن می تواند حداکثر 375 نظم داشته باشد ، کمتر از تعداد رئوس آن. [5]

اگر از تعریف کلی نمودارهای مور استفاده شود که نمودارهای مساحت را نیز امکان پذیر می سازد ، نمودارهای مور یکنواخت مربوط به نمودارهای بروز چند ضلعی های تعمیم یافته (احتمالی) است . برخی از نمونه ها چرخه های زوج هستند، نمودارهای کامل با محوطه چهار ، نمودار Heoodood با درجه 3 و اندازه 6 و نمودار Tutte-Coxeter با درجه 3 و محدوده 8. به طور کلی ، شناخته شده است که ، به غیر از نمودارهای ذکر شده در بالا ، تمام نمودارهای مور باید دارای محدوده 5 باشند ، 6 ، 8 یا 12. [6] قضیه زوج همسان نیز از قضیه Feit-Higman در مورد مقادیر احتمالی n برای یک n-gon تعمیم یافته پیروی می کند.

منبع

https://en.wikipedia.org/wiki/Moore_graph