گراف های پوشش دوگانه دوبخشی (Bipartite Double Covers)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های پوشش دوگانه دوبخشی (Bipartite Double Covers) :
گراف پوشش دوگانه دوبخشی (Bipartite Double Cover) یک گراف است که از یک گراف دلخواه (نه الزاما دوبخشی) ساخته می شود. روش ساخت به این صورت است: از هر رأس گراف اصلی، دو کپی (نسخه) به نام های
\[ v_0 \]و
\[ v_1 \]ساخته می شود. سپس برای هر یال
\[ uv \]در گراف اصلی، یال های
\[ u_0v_1 \]و
\[ u_1v_0 \]را به گراف جدید اضافه می کنیم .
گراف حاصل همیشه یک گراف دوبخشی است، زیرا می توان تمام رئوس با اندیس 0 را در یک بخش و تمام رئوس با اندیس 1 را در بخش دیگر قرار داد. این مفهوم در نظریه طیفی گراف و در برخی مسائل فیزیک ریاضی کاربرد دارد و روشی برای تبدیل هر گراف به یک گراف دوبخشی با خواص مرتبط است.
نویسنده علیرضا گلمکانی
شماره کلید 5496
گزینه ها 
نظرات 0 0 0