گراف های دوبخشی مسطح (Bipartite Planar Graphs)، در ریاضیات (Mathematics)
انواع گراف دو بخشی (Bipartite Graph) را در آموزش زیر شرح دادیم :
گراف های دوبخشی مسطح (Bipartite Planar Graphs) :
این دسته شامل گراف های دوبخشی است که خاصیت مسطح بودن (Planarity) را نیز دارند؛ یعنی می توان آنها را روی صفحه چنان رسم کرد که یال ها تنها در رئوس یکدیگر را قطع کنند. شرط لازم و کافی برای مسطح بودن یک گراف دوبخشی این است که شامل زیرگراف هایی هم ریخت با
\[ K_{3,3} \]یا
\[ K_5 \]نباشد (طبق قضیه کوراتوسکی)، و خود گراف نیز فاقد دور فرد باشد .
نمونه های بارز این گراف ها، گراف های مشبک (Grid Graphs) هستند. گراف های شبکه ای که در آنها هر وجه داخلی (Face) از چهار یال تشکیل شده باشد (مانند صفحه شطرنجی)، دو بخشی و مسطح هستند . این گراف ها در طراحی مدارهای الکترونیکی (Printed Circuit Boards)، مسائل بهینه سازی در شهرسازی (شبکه خیابان ها) و گرافیک کامپیوتری کاربرد فراوانی دارند.
نویسنده علیرضا گلمکانی
شماره کلید 5493
گزینه ها 
نظرات 0 0 0