دانلود مقاله ترجمه شده پوشش های مسیر مجزا در مکعب هایی از گراف متصل

گراف ارائه شده G و دو مجموعه راس S و T هر یک با اندازه k ، پوشش با k  مسیر مجزای متنوع برای اتصال G به S و T ، مجموعه ای از k مسیر مجزا بین S و T را پوشش می دهد. این مجموعه به شکل زوج مرتب طبقه بندی می شود البته هر راس S باید به راس تعیین شده از T اتصال داشته یا در صورت عدم وجود هیچ محدودیتی ، باید به صورت زوج نباشد. در این مقاله ما ابتدا شرط لازم و کافی را برای مکعبی از گراف متصل و برای داشتن پوشش تزویج شده از 2 مسیر مجزا را ارائه می دهیم. سپس شرطی متناظر برای نوع تزویج نشده از مسئله پوشش دو مسیر مجزا فورا استنتاج می گردد. همچنین نشان داده می شود که این نتایج می توانند به آسانی برای تعیین مکعبی از گراف متصل با مسیر همیلتونی از راس ارائه شده تا راسی دیگر که از طریق یال تعیین شده ، تعمیم داده شوند.

1-مقدمه

مشخصات مسئله

   گراف غیر مستقیم G ارائه شده ، یک پوشش مسیری ، مجموعه ای از مسیرها در G است که در آن هر راس در V(G) از طریق حداقل یک مسیر پوشش داده می شود. البته با تمرکزی خاص ، این حالت ، یک پوشش مسیری مجزا از رئوس یا به طور ساده تر پوشش مسیر مجزا است که نوعی با محدودیت افزون بوده و هر راس در آن ( احتمالا به جز برای رئوس پایانی ) باید متعلق به یک و تنها یک مسیر باشد...