گراف مور

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

گراف مور[ویرایش]

طول کوتاه‌ترین دور در یک گراف، کمر گراف نامیده می‌شود که با نماد (γ(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 است که تعداد رئوس آن با حد بالای

1+d\sum_{i=0}^{k-1}(d-1)^i .

برابر باشد.

قضیه‌های در مورد گراف مور[ویرایش]

گراف پترسون[ویرایش]

گراف پترسون تنها گراف مور با درجه ۳ است.

قضیه هافمن-سینگلتون[ویرایش]

یک گراف مور فقط با درجه k=۲, ۳, ۷ , ۵۷ است.

اثبات : در مرجع ۱

لازم به توضیح است که گراف مور با درجه ۳ همان گراف پترسون است و گراف با درجه ۷ همان گراف هافمن-سینگلتون (Hoffman-Singleton Graph) است. البته وجود گراف مور با درجه ۵ با قضیه ثابت نشده است و حدس هایی در مورد وجود آن زده است. در هر حال پیدا کردن گراف مور با درجه ۵ و ۵۷ از مسائل حل نشده نظریه گراف است. محدود کردن تعداد رئوس با درجه و قطر: فرض کنیم گراف G و فرض کنیم درجه آن k و قطر آن d و درخت جستجوی نخستین پهنا (BFS Breadth First Search)آن را در نظر می گیریم که از هر کدام از رئوس دلخواه v آن را آغاز می کنیم . این درخت یک راس با درجه ۰ (راس آغازی شروع گراف) دارد و حداکثر k راس با درجه ۱ دارد (رئوس مجاور راس مبدا). در سطح بعد حداکثر (k(k-۱ راس داریم. هر راس مجاور v از یکی از همسایه‌های v برای اتصال به v استفاده می کنند بنا براین حداکثر k-۱ همسایه در سطح ۲ داریم. در کل برای هر سطح i بین ۱ تا k حداکثر k(k-۱)i راس وجود دارد. پس تعداد کل رئوس در کل

1+d\sum_{i=0}^{k-1}(d-1)^i.

است.

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

به جای حد بالا تعداد رئوس درون گراف در قابل جملات ماکزیمم درجه و قطر آن، ما می توانیم با روشی مشابه حد پایینی برای برای تعداد رئوس در قالب جملاتی از درجه و کمر گراف به دست آورد. فرض کنیم گراف G دارای حداقل درجه k و کمر ۲d+۱ باشد. حال به طور دلخواه یک راس v را انتخاب می کنیم و طبق همان روشی که در بالا توضیح داده شد درخت BFS که راس v ریشه آن است تشکیل می دهیم. این درخت یک راس در سطح ۰ دارد و حداقل k راس در سطح ۱ و حداقل (k(k-۱ راس در سطح ۲ و در کل برای هر سطح i بین ۱ تا k حداقل d(d-۱)i راس دارد. پس مجموعاً تعداد رئوس حداقل باید

1+d\sum_{i=0}^{k-1}(d-1)^i.

باشد.

در گراف مور این حد به دست آمده برای تعداد رئوس دقیقاً دیده شده است.هر گراف مور کمر ۲k+۱ دارد چون برای داشتن کمر بزرگتر به اندازه کافی راس ندارد و یک دور کوتاه تر باعث می‌شود که تعداد خیلی کمی راس در k سطح اولیه از درخت BFS وجود خواهد داشت. بنا براین یک گراف مور تعداد رئوس ممکن در بین همهٔ گراف هایی دارد که درجه k دارند و قطر d دارند؛ بنابراین یک قفس است.

منابع[ویرایش]

کتاب Graphs, Algorithms, and optimization

نوشتهWilliam kocay, Donal L Kreher

صفحهٔ مربوط به گراف مور در ویکی‌پدیای انگلیسی