دوستعلی مژده

ر این پروژه می خواهیم دسته ای از خواص گراف بدون جهت، از جمله احاطه گر چندتایی، بسته بندب های محدود، احاطه گر چندتای کلی و بسته بندی های محدود کلی را برای حالت گراف های جهت دار تعمیم بدهیم، اگرچه بیشتر دراین پروژه به $2$-تایی ها می پردازیم. فرض کنید $ D $ یک گراف جهت دار باشد. زیرمجموعه ی $ S $ از رئوس یک گراف جهت دار $ D $ را یک مجموعه ی $2$-احاطه کننده ی کلی گوییم هرگاه هر رأس خارج از $ S $ مجاور از حداقل دو رأس از $ S $ بوده و زیرگراف القایی توسط $ S $ رأس تنها نداشته باشد. گوییم $ D^{-1} $ گرافی جهت دار حاصل از برعکس کردن جهت هر کمان در $ D $ باشد. در کار پیش رو مفهوم مذکور را که می توان آن را به عنوان توسیعی از احاطه دوتایی در گراف ها به گراف های جهت دار در نظر گرفت، به همراه عدد $2$-بسته بندی محدود کلّی ($ L_2^t(D) $) از گراف های جهت دار $ D $ که رابطه ی نزدیکی با مفهوم فوق الذکر دارد، مورد تحقیق قرار می دهیم. ثابت می کنیم که مسائل محاسبه ی این پارامترها حتّی برای گراف های جهت دار دوبخشی $ NP $-دشوار است. همچنین چندین کران بالا و پایین برای آن ها ارائه خواهیم کرد. در مواجهه با این دو پارامتر تاکید اصلی ما بر درخت های جهت دار است که به وسیله ی آن ها ثابت می کنیم برای هر گراف جهت دار $ D $ با $ n $ رأس $ L_2^t(D) + L_2^t(D^{-1}) $ را می توان از بالا به وسیله ی $ \frac{16 n}{9} $ کراندار کرد. بعلاوه عدد $2$-احاطه کلّی یک درخت جهت دار را از پایین کراندار کرده و درخت های جهت داری که برای آن ها تساوی در کران حاصل برقرار است را مشخص سازی خواهیم نمود.