عاملبندی گراف
 | این مقاله به هیچ منبع و مرجعی استناد نمیکند. |
در نظریه گراف، یک عامل از یک گراف G یک زیرگراف فراگیر است، برای مثال یک زیرگرافی که مجموعه رئوس برابری با G دارد. یک k-عامل از یک گراف یک زیرگراف فراگیر k-منتظم است و یک k-عاملبندی یال‌های گراف را به k-عامل‌های مستقل افراز می‌کند. گراف G را k-عاملپذیر می‌گویند هرگاه قابل k-عاملبندی شدن باشد. به طور کلی، یک ۱-عامل یک تطابق کامل است، و یک ۱-عاملبندی یک گراف k-منتظم یک رنگ‌آمیزی یالی با k رنگ است. یک ۲-عامل مجموعه‌ای از دور‌ها است که تمام رئوس گراف را پوشش می‌دهند.
۱-عاملبندی[ویرایش]
اگر یک گراف ۱-عاملپذیر باشد، بنابراین باید یک گراف منتظم باشد. اما تمام گراف‌های منظم ۱-عاملپذیر نیستند. یک گراف k-منتظم ۱-عاملپذیر است اگر عدد رنگی k داشته باشد. به عنوان مثال:
- هر گراف دو بخشی منتظم. با استفاده از قضیه هال می‌توان نشان داد که یک گراف دو بخشی k-منتظم شامل یک تطابق کامل است. می‌توان با حذف تطابق کامل یک گراف دو بخشی (k-۱)-منتظم به دست‌آورد، و همین کار را تکرار کرد.
- هر گراف کامل با زوج راس (زیر را ببینید)
اما گراف‌های k-منتظمی وجود دارد که عدد رنگی آن‌ها k+۱ است و این گراف‌ها ۱-عاملپذیر نیستند. به عنوان مثال:
- هر گراف با فرد راس
- گراف پترسن
گراف‌های کامل[ویرایش]
یک ۱-عاملبندی از یک گراف کامل متناظر است با جفت‌ها در رقابت‌های دورهای. ۱-عاملبندی یک گراف کامل یک حالت خاص از قضیه بارانیای که به ۱-عاملبندی یک ابرگراف کامل مربوط است. یکی از روش‌های ساختن یک ۱-عاملبندی از یک گراف کامل این است که تمام رئوس به جز یکی را دور یک دایره بچینیم که یک چند ضلعی منتظم تشکیل بدهد، و راس باقیمانده را در وسط دایره قرار دهیم. اگر با این چیدمان رئوس، یک راه برای ساختن ۱-عامل گراف انتخاب یک یال e از مرکز به یکی از رئوس چند ضلعی و انتخاب تمام یال‌های عمود بر آن. ۱-عامل‌هایی که با این روش ساخته می‌شوند ۱-عاملبندی گراف را تشکیل می‌دهند.
حدس 1-عاملبندی[ویرایش]
فرض کنید G یک گراف ,k-منتظم با 2n راس باشد. اگر k به مقدار کافی بزرگ باشد، فهمیده می‌شود که G باید 1-عاملپذیر باشد:
- اگر k = 2n – 1، آنگاه G یک گراف کامل K2n است و در نتیجه 1-عاملپذیر.
- اگر k = 2n – 2، آنگاه G را می‌توان با حذف کردن یک تطابق کامل از K2n به دست‌آورد. G باز هم 1-عاملپذیر است.
- (Chetwyn & Hilton (1985 نشان دادند که اگر k ≥ 12n/7 باشد آنگاه G گرافی 1-عاملپذیر است.
حدس 1-عاملبندی یک حدس قدیمی است که بیان می‌کند k≈n کافی است. در بیانی دقیق‌تر حدس می‌گوید: اگر n فرد باشد و k ≥ n باشد آنگاه G گرافی 1-عاملپذیر است. همین‌طور اگر n زوج باشد و 1 - k ≥ n آنگاه G گرافی 1-عاملپذیر است. حدس overfull حدس 1-عاملبندی را نتیجه می‌دهد.
۲-عاملبندی[ویرایش]
اگر یک گراف ۲-عاملپذیر باشد، آنگاه آن باید برای یک k صحیح ۲k-منتظم باشد. جولیوس پترسون در سال ۱۸۹۱ نشان داد که شرط لازم کافی هم است: هر ۲k-منتظم ۲-عاملپذیر است. اگر یک گراف همبند ۲k-منتظم باشد و تعداد زوجی یال داشته باشد، شاید k-عامل بشود، به این ترتیب که هر کدام از دو عامل‌های یک زیر مجموعهٔ متفاوت از یال‌های تور اویلری است. این قضیه فقط بر روی گراف‌های همبند صادق است. مثال نقض‌های گراف‌های ناهمبند، اجتماع تعدادی دورهای فرد یا K۲k+۱ مستقل است.