ضخامت (نظریه گراف)

در نظریه گراف ضخامت گراف G، به حداقل تعداد گراف مسطحی که با یال‌های گراف G می‌توان ساخت گویند. به طوری که اگر k گراف مسطح وجود داشته باشد که همه شامل رئوس یکسانی باشد و حاصل اجتماع این گراف‌ها برابر G شود، آنگاه حداکثر عدد ضخامت این گراف k می‌باشد. به عبارت دیگر ضخامت گراف کمترین تعداد زیرگراف‌های مسطحی است که اجتماعشان برابر خود گراف باشد.

بنابر این ضخامت یک گراف مسطح برابر ۱ است. گراف‌هایی با ضخامت ۲ دو سطحی نامیده می‌شود. مفهوم ضخامت گراف از تخمین Frank Harary در سال ۱۹۶۲۲ نشات می‌گیرد: برای هر گرافی با درجه ۹ یا خودش یا مکملش غیر مسطح است. این مسیله معادل این است: تعیین این که ایا گراف کامل k9 دو سطحی است یا خیر (دو سطحی است و تخمین درست است)بررسی دقیقی در ۱۹۹۸ توسط Petra Mutzel ,Thomas odenthal وMark scharbrodr در این این زمینه صورت گرفته‌است.

گراف‌های خاص

ضخامت گراف کامل در n راس K_nاست

$\left\lfloor {\frac {n+7}{6}}\right\rfloor ,$

به جز زمانی که n = ۹, ۱۰ که در این صورت ضخامت ۳ است.

با چند استثنا ضخامت کامل گراف دوبخشی K_a,b به‌طور کلی برابر:

$\left\lceil {\frac {ab}{2(a+b-2)}}\right\rceil .$

مسا‍ئل مرتبط

هر جنگلی یک گراف مسطح است و هر گراف مسطحی حداکثر می‌تواند به سه جنگل تقسیم شود؛ بنابراین ضخامت هر گراف G حداکثر برابر arboricity گراف است. (کمترین تعداد جنگلی که یک گراف می‌تواند به آن تقسیم شود) و حداقل برابر با arboricity گراف تقسیم بر ۳ است. ضخامت گراف G همچنین در فاکتور ثابت دیگری از مشخصه‌های گراف، degeneracy، مشهود است. این مشخصه همان بیشینهٔ کمترین درجهٔ زیر گراف‌های G است. اگر یک گراف با n راس ضخامتی با مقدار t داشته باشد، آنگاه حد اکثر (t(3n-6 یال دارد که از آن نتیجه می‌شود که degeneracy آن حد اکثر 6t-۱ است. از سویی دیگر می‌توان گفت که اگر degeneracy گرافی برابر با D باشد آنگاه arboricity و ضخامت آن حد اکثر D خواهد بود.

ضخامت رابطهٔ نزدیکی با مسئلهٔ تعبیهٔ همزمان دارد. اگر به تعداد دو یا بیشتر گراف مسطح داشته باشیم که همگی دارای چینش یکسانی از رئوس باشند آنگاه امکان‌پذیر است که همهٔ این گراف‌ها را در صفحه‌ای جاسازی کنیم به طوری که یال‌های آن به صورت مجموعه‌ای از خم‌ها نمایش داده شده باشند. در نتیجه هر راس در همهٔ حالات مکان مشخصی خواهد داشت. حال آنکه اگر این یال‌ها را به خط‌های صاف نمایش دهیم، این امر ممکن نخواهد بود.

یکی دیگر از ویژگی‌های گراف ضخامت آن در مسیر راست یا Geometric thikness است که نشان دهندهٔ کمترین تعداد گراف‌های مسطحی است که گراف G می‌تواند به آن‌ها تقسیم شود به شرطی که همهٔ این گراف‌ها بتوانند به صورت همزمان به وسیلهٔ خطوط راست رسم شوند. «ضخامت کتابی» شرط دیگری را اضافه می‌کند و آن این است که، همهٔ رئوس باید با یک دیگر تشکیل شکلی محدب بدهند. با این وجود با در نظر گرفتن arboricity و degeneracy همیشه دو تا از این سه ویژگی مطرح شده برای ضخامت گراف در مشخصه‌های ثابت یکدیگر وجود ندارند.

پیچیدگی محاسباتی

محاسبهٔ ضخامت یک گراف داده شده یک مسئلهٔ NP- سخت و نتیجه‌گیری اینکه ضخامت آن حد اکثر ۲ است، یک مسئلهٔ NP-کامل است. با این وجود arboricity به ما امکان تخمین عدد ضخامت را با تقریب ۳ برابر در زمان چند جمله‌ای فراهم می‌کند.