از ویکیپدیا، دانشنامه آزاد
در ریاضی منطقه از نظریه گراف ، یک قفس است گراف به طور منظم که به عنوان چند است راس که ممکن است برای آن دور .
به طور رسمی ، نمودار ( r ، g ) به شکلی تعریف می شود که در آن هر راس دقیقاً r همسایه داشته باشد و کوتاه ترین چرخه طول آن دقیقاً g باشد. مشخص شده است که یک ( R ، G ) -گراف برای هر ترکیبی از وجود دارد R ≥ 2 وG≥ 3. ( R ، G ) -cage یک IS ( R ، G ) -گراف با کمترین تعداد ممکن از رئوس، در میان همه ( r ، g ) - گرافها.
اگر گراف مور با درجه r و اندازه g وجود داشته باشد ، باید یک قفس باشد. علاوه بر این ، محدوده اندازه های نمودارهای مور به قفس تعمیم می یابد: هر قفس با محکم بودن g g باید حداقل
رأس ، و هر قفس با حتی مساحت g باید حداقل داشته باشد
رگه ها. هر نمودار ( r ، g ) دقیقاً با این تعداد رئوس با تعریف یک گراف مور است و بنابراین به طور خودکار یک قفس است.
برای ترکیب مشخص r و g ممکن است چندین قفس وجود داشته باشد . به عنوان مثال سه قفس غیر هم شکل (3،10) وجود دارد که هر کدام 70 راس دارند: قفس 10 Balaban ، نمودار Harries و نمودار Harries – Wong . اما فقط یک قفس ( 3،11) وجود دارد: قفس Balaban 11 (با 112 راس).
فهرست
قفس های شناخته شده [ ویرایش ]
درجه یک گراف است چرخه، و یک متصل درجه دو گراف دور به تعداد آن از راس برابر است، بنابراین قفس تنها از علاقه برای می R ≥ 3. ( R ، 3) -cage است گراف کامل K R 1 + در r +1 رئوس ، و ( r ، 4) -cage یک نمودار دوتایی کامل K r ، r روی رئوس 2 r است .
قفس های دیگر قابل توجه عبارتند از:
- (3،5) قفس: گراف پترسن ، 10 رئوس
- (3،6) - قفس: نمودار هیود ، 14 رئوس
- (3،8) قفس: گراف تات -کاکستر ، 30 رئوس
- (3،10) - قفس : بلابان 10-قفس ، 70 رئوس
- (3،11) - قفس : بلابان 11-قفس ، 112 رئوس
- (4،5) قفس: نمودار رابرتسون ، 19 رئوس
- (7،5) قفس: نمودار هافمن-سینگلتون ، 50 رئوس.
- وقتی r - 1 یک قدرت اصلی است ، قفسهای ( r ، 6) نمودارهای بروز فضاهای تصویری هستند .
- وقتی r - 1 یک قدرت اصلی است ، قفس های ( r ، 8) و ( r ، 12) چند ضلعی های تعمیم یافته هستند .
تعداد رئوس در قفسهای شناخته شده ( r ، g ) ، برای مقادیر r > 2 و g > 2 ، غیر از صفحات تصویری و چند ضلعی های تعمیم یافته ، عبارتند از:
g ر | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
| 4 | 5 | 8 | 19 | 26 | 67 | 80 | 728 | |||
| 5 | 6 | 10 | 30 | 42 | 170 | 2730 | ||||
| 6 | 7 | 12 | 40 | 62 | 312 | 7812 | ||||
| 7 | 8 | 14 | 50 | 90 |
علائم تجزیه ای [ ویرایش ]
برای مقادیر بزرگ g ، محدوده مور نشان می دهد که تعداد n رئوس باید حداقل به صورت نمایی به عنوان تابعی از g رشد کند . بدین ترتیب در گرم می توان در بسیاری متناسب با لگاریتم از N . دقیق تر،
اعتقاد بر این است که این بند محکم یا نزدیک به محکم است ( Bollobás & Szemerédi 2002 ). بهترین مرزهای شناخته شده پایین در g نیز لگاریتمی است ، اما با یک فاکتور ثابت کوچکتر (به این معنی است که n به صورت نمایی رشد می کند اما با سرعتی بالاتر از حد مور). به طور خاص ، ساخت نمودار Ramanujan تعریف شده توسط Lubotzky ، Phillips & Sarnak (1988) محدودیت
این محدودیت توسط Lazebnik ، Ustimenko & Woldar (1995) کمی بهبود یافت .
بعید است که این نمودارها خود قفس باشند ، اما وجود آنها حد بالایی به تعداد رئوس مورد نیاز در قفس می دهد.
منبع
https://en.wikipedia.org/wiki/Cage_(graph_theory)
در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.