عامل بندی گراف

در نظریه گراف، یک عامل از یک گراف G یک زیرگراف فراگیر است، برای مثال یک زیرگرافی که مجموعه رئوس برابری با G دارد. یک k-عامل از یک گراف یک زیرگراف فراگیر k-منتظم است و یک k-عامل بندی یال های گراف را به k-عامل های مستقل افراز می کند. گراف G را k-عامل پذیر می گویند هرگاه قابل k-عامل بندی شدن باشد. به طور کلی، یک ۱-عامل یک تطابق کامل است، و یک ۱-عامل بندی یک گراف k-منتظم یک رنگ آمیزی یالی با k رنگ است. یک ۲-عامل مجموعه ای از دور ها است که تمام رئوس گراف را پوشش می دهند.
هر گراف دو بخشی منتظم. با استفاده از قضیه هال می توان نشان داد که یک گراف دو بخشی k-منتظم شامل یک تطابق کامل است. می توان با حذف تطابق کامل یک گراف دو بخشی (k-۱)-منتظم به دست آورد، و همین کار را تکرار کرد.
هر گراف کامل با زوج راس (زیر را ببینید)
اگر یک گراف ۱-عامل پذیر باشد، بنابراین باید یک گراف منتظم باشد. اما تمام گراف های منظم ۱-عامل پذیر نیستند. یک گراف k-منتظم ۱-عامل پذیر است اگر عدد رنگی k داشته باشد. به عنوان مثال:
اما گراف های k-منتظمی وجود دارد که عدد رنگی آن ها k+۱ است و این گراف ها ۱-عامل پذیر نیستند. به عنوان مثال:
یک ۱-عامل بندی از یک گراف کامل متناظر است با جفت ها در رقابت های دوره ای. ۱-عاملبندی یک گراف کامل یک حالت خاص از قضیه بارانیای که به ۱-عامل بندی یک ابرگراف کامل مربوط است.یکی از روش های ساختن یک ۱-عامل بندی از یک گراف کامل این است که تمام رئوس به جز یکی را دور یک دایره بچینیم که یک چند ضلعی منتظم تشکیل بدهد، و راس باقیمانده را در وسط دایره قرار دهیم. اگر با این چیدمان رئوس، یک راه برای ساختن ۱-عامل گراف انتخاب یک یال e از مرکز به یکی از رئوس چند ضلعی و انتخاب تمام یال های عمود بر آن. ۱-عامل هایی که با این روش ساخته می شوند ۱-عامل بندی گراف را تشکیل می دهند.