نمایش مبدأ برای گراف مور

طول کوتاه‌ترین دور در یک [[گراف]]، [[کمر گراف]] نامیده می‌شود که با نماد (γ(G نشان داده می‌شود.
به عنوان مثال مکعب کمر به طول ۴ دارد. برای گراف‌های [[گراف منتظم|kمنظم]] و با طول کمر ثابت معمولاً ویژگی‌های جالبی دارند.
به عنوان مثال گراف G را یک گراف  k منتظم با طول کمر ۴ چهار باشد اگرهر کدام از رأس‌های u گراف G را در نظر بگیریم
k راس با فاصله یک از آن راس وجود دارد. از آنجا که گراف G هیچ مثلثی ندارد حداقل k-۱ راس با فاصله دو از u وجود دارند.

بنابراین داریم، G|≥۱+k+(k-۱)=۲k|  و (|G| برابر با تعداد رئوس گراف است) فقط یک گراف با ویژگی G|=۲k| وجود دارد
و این و این همان [[گراف کامل دوبخشی|گراف کامل دو بخشی]] K<sub>k,k</sub> است. و حال اگر G  گراف k منتظم با کمر پنج باشد و  u هر یک از رئوس گراف باشد،
k راس با فاصله یک از u وجود دارد به‌طوری که؛ G|≥۱+k+k(k-۱)=1+K<sup>۲</sup>|

== تعریف گراف مور ==

گرافی است k  منتظم با طول کمر پنج، به‌طوری‌که G|=K<sup>۲</sup>+۱| .
فرض کنیم |n = |G . یک گراف ۱ منتظم نمی‌تواند کمر به طول ۵ داشته باشد. پس باید k≥۲ .
اگر k =۲ پس n=۲<sup>۲</sup>+۱ = ۵ یعنی G یک دور به طول پنج دارد پس این تنها گراف مور با درجه ۲.

اگر k=۳ پس n=۳<sup>۲</sup>+۱=۱۰.

پس ۳ راس با فاصله یک از هر راس u وجود دارد و ۶ راس با فاصله ۲ وجود دارد که در شکل زیر نشان داده شده‌است.

== تعریف تعمیم یافته گراف مور ==

به بیان دیگر گراف مور، یک گراف با درجه k و قطر d است که تعداد رئوس آن با
حد بالای

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i .</math>

برابر باشد.

=== قضیه‌های در مورد گراف مور ===

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

==== قضیه هافمن-سینگلتون ====

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

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

لازم به توضیح است که گراف مور با درجه ۳ همان گراف پترسون است و گراف با درجه ۷ همان
[http://en.wikipedia.org/wiki/Hoffman–Singleton_graph گراف هافمن-سینگلتون] (Hoffman-Singleton Graph) است. 
البته وجود گراف مور با درجه ۵ با قضیه ثابت نشده‌است و حدس‌هایی در مورد وجود آن زده است.
در هر حال پیدا کردن گراف مور با درجه ۵ و ۵۷ از مسائل حل نشده [[نظریه گراف]] است. 
محدود کردن تعداد رئوس با درجه و قطر:
فرض کنیم گراف G و فرض کنیم درجه آن k و قطر آن d و [[پیمایش گراف|درخت جستجوی نخستین پهنا]] 
(BFS Breadth First Search)آن را  در  نظر می‌گیریم که از هر کدام از رئوس دلخواه v آن را آغاز می‌کنیم . این درخت یک راس با درجه ۰
(راس آغازی شروع گراف) دارد و حداکثر k راس با درجه ۱ دارد (رئوس مجاور راس مبدا). در سطح بعد حداکثر (k(k-۱ راس داریم.
هر راس مجاور v از یکی از همسایه‌های v برای اتصال به v استفاده می‌کنند بنابراین حداکثر k-۱ همسایه در سطح ۲ داریم.
در کل برای هر سطح i بین ۱  تا k حداکثر k(k-۱)<sup>i</sup> راس وجود دارد. پس تعداد کل رئوس در کل

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>

است.

=== استفاده از گراف مور به عنوان [[قفس (نظریه گراف)|قفس]] ===

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

:<math>1+d\sum_{i=0}^{k-1}(d-1)^i.</math>

باشد.

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

== منابع ==
{{پانویس}}

کتاب Graphs, Algorithms, and optimization

نوشتهWilliam kocay, Donal L Kreher

[http://en.wikipedia.org/wiki/Moore_graph صفحهٔ مربوط به گراف مور در ویکی‌پدیای انگلیسی]

[[رده:گراف‌های منتظم]]
[[رده:نظریه گراف]]