گراف مور
طول کوتاهترین دور در یک گراف، کمر گراف نامیده میشود که با نماد (γ(G نشان داده میشود. به عنوان مثال مکعب کمر به طول ۴ دارد. برای گرافهای kمنظم و با طول کمر ثابت معمولاً ویژگیهای جالبی دارند. به عنوان مثال گراف G را یک گراف k منتظم با طول کمر ۴ چهار باشد اگرهر کدام از رأسهای u گراف G را در نظر بگیریم k راس با فاصله یک از آن راس وجود دارد. از آنجا که گراف G هیچ مثلثی ندارد حداقل k-۱ راس با فاصله دو از u وجود دارند.
بنابراین داریم، G|≥۱+k+(k-۱)=۲k| و (|G| برابر با تعداد رئوس گراف است) فقط یک گراف با ویژگی G|=۲k| وجود دارد و این و این همان گراف کامل دو بخشی Kk,k است. و حال اگر G گراف k منتظم با کمر پنج باشد و u هر یک از رئوس گراف باشد، k راس با فاصله یک از u وجود دارد بهطوری که؛ G|≥۱+k+k(k-۱)=1+K۲|
تعریف گراف مور ویرایش
گرافی است k منتظم با طول کمر پنج، بهطوریکه G|=K۲+۱| . فرض کنیم |n = |G . یک گراف ۱ منتظم نمیتواند کمر به طول ۵ داشته باشد. پس باید k≥۲ . اگر k =۲ پس n=۲۲+۱ = ۵ یعنی G یک دور به طول پنج دارد پس این تنها گراف مور با درجه ۲.
اگر k=۳ پس n=۳۲+۱=۱۰.
پس ۳ راس با فاصله یک از هر راس u وجود دارد و ۶ راس با فاصله ۲ وجود دارد که در شکل زیر نشان داده شدهاست.
تعریف تعمیم یافته گراف مور ویرایش
به بیان دیگر گراف مور، یک گراف با درجه k و قطر d است که تعداد رئوس آن با حد بالای
برابر باشد.
قضیههای در مورد گراف مور ویرایش
گراف پترسون ویرایش
گراف پترسون تنها گراف مور با درجه ۳ است.
قضیه هافمن-سینگلتون ویرایش
یک گراف مور فقط با درجه k=۲, ۳, ۷ , ۵۷ است.
اثبات : در مرجع ۱
لازم به توضیح است که گراف مور با درجه ۳ همان گراف پترسون است و گراف با درجه ۷ همان گراف هافمن-سینگلتون (Hoffman-Singleton Graph) است. البته وجود گراف مور با درجه ۵ با قضیه ثابت نشدهاست و حدسهایی در مورد وجود آن زده است. در هر حال پیدا کردن گراف مور با درجه ۵ و ۵۷ از مسائل حل نشده نظریه گراف است. محدود کردن تعداد رئوس با درجه و قطر: فرض کنیم گراف G و فرض کنیم درجه آن k و قطر آن d و درخت جستجوی نخستین پهنا (BFS Breadth First Search)آن را در نظر میگیریم که از هر کدام از رئوس دلخواه v آن را آغاز میکنیم . این درخت یک راس با درجه ۰ (راس آغازی شروع گراف) دارد و حداکثر k راس با درجه ۱ دارد (رئوس مجاور راس مبدا). در سطح بعد حداکثر (k(k-۱ راس داریم. هر راس مجاور v از یکی از همسایههای v برای اتصال به v استفاده میکنند بنابراین حداکثر k-۱ همسایه در سطح ۲ داریم. در کل برای هر سطح i بین ۱ تا k حداکثر k(k-۱)i راس وجود دارد. پس تعداد کل رئوس در کل
است.
استفاده از گراف مور به عنوان قفس ویرایش
به جای حد بالا تعداد رئوس درون گراف در قابل جملات ماکزیمم درجه و قطر آن، ما میتوانیم با روشی مشابه حد پایینی برای برای تعداد رئوس در قالب جملاتی از درجه و کمر گراف به دست آورد. فرض کنیم گراف G دارای حداقل درجه k و کمر ۲d+۱ باشد. حال بهطور دلخواه یک راس v را انتخاب میکنیم و طبق همان روشی که در بالا توضیح داده شد درخت BFS که راس v ریشه آن است تشکیل میدهیم. این درخت یک راس در سطح ۰ دارد و حداقل k راس در سطح ۱ و حداقل (k(k-۱ راس در سطح ۲ و در کل برای هر سطح i بین ۱ تا k حداقل d(d-۱)i راس دارد. پس مجموعاً تعداد رئوس حداقل باید
باشد.
در گراف مور این حد به دست آمده برای تعداد رئوس دقیقاً دیده شدهاست. هر گراف مور کمر ۲k+۱ دارد چون برای داشتن کمر بزرگتر به اندازه کافی راس ندارد و یک دور کوتاهتر باعث میشود که تعداد خیلی کمی راس در k سطح اولیه از درخت BFS وجود خواهد داشت. بنابراین یک گراف مور تعداد رئوس ممکن در بین همهٔ گرافهایی دارد که درجه k دارند و قطر d دارند؛ بنابراین یک قفس است.
منابع ویرایش
کتاب Graphs, Algorithms, and optimization
نوشتهWilliam kocay, Donal L Kreher