موضوع مقاله: گراف فاکتور بحرانی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف فاکتور بحرانی | مقدمه: پس به‌طور مشابه یک گراف فاکتور_بحرانی گرافی است که در آن تطابق‌های کامل نزدیک وجود داشته باشد طوری که در هر کدام از یکی از راس‌ها صرف نظر شده باشد. | ## بخش 1: گراف فاکتور بحرانی | گراف‌های دوستی یا friendship graphs (گراف‌هایی که از اتصال مجموعه‌ای از مثلث‌ها به وجود آمده و در یک راس مشترک هستند) مثال دیگری از گراف فاکتور_بحرانی‌ها هستند با این تفاوت که این گراف‌ها غیر همیلتونی هستند. برای مثال گراف ۱۱ راسی که از حذف یک راس از بیست وجهی منتظم به وجود می‌آید و همبند نیز می‌باشد، یک گراف فاکتور_بحرانی می‌باشد. این نتیجه به‌طور مستقیم از یک قضیه بنیادی تر با این مضمون که هر گراف پنجه آزادِ همبند که دارای تعدادی زوج راس باشد حتماً دارای یک تطابق کامل می‌باشد، حاصل می‌شود. این نتیجه از این ویژگی که گراف باید دارای تعدادی فرد راس بوده طوری که هر تطابق حداکثر باید همه راس‌ها به جز یکی را به هم مرتبط کند، استنتاج می‌شود. لاسلو لوواس نیز ثابت کرد که گرافی فاکتور بحرانی می‌باشد اگر و تنها اگر تعدادی فرد تجزیه گوشی داشته باشد (یک دسته‌بندی از یال‌های گراف به دنباله‌ای از زیرگراف‌ها گفته می‌شود به طوری که هر یک از این زیرگراف‌های دارای دور یا مسیری به طول فرد باشند، به این ترتیب که اولین زیرگراف یک دور باشد و بعد از آن زیرگراف‌ها هرکدام مسیری باشند که دارای نقطه‌های پایانی هستند و هر راس داخلی نباید در زیرگراف قبلی وجود داشته باشد، همچنین هر دور به غیر از دور اول در دنباله دقیقاً یک راس در زیرگراف‌های قبلی داشته باشد. برای مثال گراف نمایش داده شده در شکل ممکن است با این روش به یک دور با ۵ یال و یک مسیر با ۳ یال تقسیم‌بندی شود. در مواردی که تطابق کامل نزدیک برای گراف فاکتور بحرانی داده شود، دسته‌های جدا شدنی می‌توانند به نحوی انتخاب شوند که دسته‌های جدا شدنی بین یال‌های تطبیق یافته و تطبیق نیافته متبادل شوند. یک گراف همچنین فاکتور بحرانی است اگر و تنها اگر بتوان این گراف را به وسیله دنباله‌ای از ادغام‌های دورهای به طول فرد به یک گراف ساده تبدیل کرد. | ## بخش 2: گراف فاکتور بحرانی | علاوه بر این، در این توصیف این امکان وجود دارد تا هر دور در این دنباله را طوری انتخاب کرد که شامل یک راس که از ادغام دور قبلی که به وجود آمده است، باشد. برای مثال اگر یکی, دسته‌های یک تجزیه گوشی را قطع کند، به ترتیبی که دسته‌ها تجزیه شده‌اند، سپس در هر زمان که یکی از دسته‌ها قطع می‌شود، یک دور فرد به وجود می‌آید، به همین منظور این ویژگی دسته‌های جدا شدنی می‌تواند برای یافتن دنباله‌ای از دورهای فرد برای ادغام استفاده شود. به‌طور عکس از دنباله‌ای از ادغام دورهای فرد که هر کدام شامل یک راس که از ادغام قبلی می‌باشد، می‌توان یک دسته تجزیه پذیر به وجود آورد به طوری که دسته‌ها مجموعه‌ای از یال‌های ادغام شده در هر مرحله باشند. فرض کنید که گراف G به همراه یک راس منتخب و برگزیده به نام V و یک تطابق به نام M که همه راس‌ها به غیر از V را پوشش می‌دهد داده شده‌است. پس G زمانی فاکتور بحرانی است اگر و تنها اگر مجموعه‌ای از مسیرها در G وجود داشته باشد طوری که یک در میان از بین یال‌های انطباق یافته و انطباق نیافته، راس V را به سایر راس‌ها در G وصل کنند. بر اساس این ویژگی ما می‌توانیم در زمان خطی تشخیص بدهیم که آیا گراف G با تطابق کامل نزدیک داده شده فاکتور بحرانی هست یا نه. خواص و ویژگی ها گراف‌های فاکتور_بحرانی همیشه تعداد فرد راس دارند و نیز باید همبندی دو یالی داشته باشند (به این معنی که نباید هیچ پلی داشته باشند). با این وجود ضرورتی ندارد که هر دو راس در این گراف‌ها همبند باشند، گراف‌های دوستی (friendship) می‌توانند یک نوع مثال نقض در این رابطه باشند. | ## بخش 3: گراف فاکتور بحرانی | دو بخشی بودن گراف فاکتور_بحرانی‌ها امری غیرممکن است، زیرا در گراف دوبخشی با یک تطابق کامل، تنها راس‌هایی که در قسمت بزرگتر گراف دوقسمتی هستند می‌توانند با حذف خود یک گراف دارای تطابق کامل تولید کنند. هر گراف فاکتور_بحرانی با m یال که دو راس-همبند می‌باشد، حداقل دارای m عدد تطابق کامل مختلف می‌باشد، به‌طور کلی هر گراف فاکتور_بحرانی با m یال و c بلوک (اجزای دو راس همبند) حداقل عدد تطابق نزدیک مختلف دارد. گراف‌هایی که این محدودیت‌ها و ویژگی‌ها را شامل می‌شوند، به گراف‌هایی با تعداد فرد دسته تجزیه پذیر به یک شکل خاص توصیف می‌شوند. هر گراف همبند می‌تواند با قطع کردن تعداد کافی از یال‌هایش به یک گراف فاکتور_بحرانی تبدیل شود. حداقل مجموعه‌ای از یال‌ها را که برای تبدیل گراف G به یک گراف فاکتور_بحرانی لازم است قطع کنیم اساس matroid را تشکیل می‌دهد. Matroid قضیه‌ای است که به یک الگوریتم حریصانه برای یافتن کمترین وزن مجموعه‌ای از یال‌ها که باید قطع شوند تا در زمان چند جمله‌ای یک گراف فاکتور_بحرانی را بسازند، اشاره می‌کند. در ترکیب‌های چند ضلعی، گراف‌های فاکتور-بحرانی یک نقش کلیدی در توضیح شکل‌های تطابق یا تطابق جنگل‌های چندگانهٔ از یک گراف داده شده ایفا می‌کند. یک گراف critical (بدون قید و شرط) معمولاً این گونه تفسیر می‌شود که حذف هر یک از رأس‌ها تعداد رنگ‌های لازم برای رنگ آمیزی این گراف را کاهش می‌دهد. | ## جمع‌بندی | مفهوم critical بودن به‌طور عمومی در نظریه گراف‌ها اشاره بر این دارد که حذف هر رأسِ ممکن بعضی از ویژگی‌های وابسته به گراف را تغییر می‌دهد و بعضی را تغییر نمی‌دهد.