گراف دوگان (Dual Graph)، در ریاضیات (Mathematics)

انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :

گراف دوگان (Dual Graph) :

اگر یک گراف صفحه ای (رسم شده) داشته باشیم، می توانیم گراف دوگان آن را بسازیم. برای ساخت گراف دوگان، داخل هر وجه (Face) از گراف اصلی، یک رأس جدید قرار می دهیم. سپس به ازای هر یال مشترک بین دو وجه، دو رأس مربوط به آن وجوه را توسط یک یال به هم وصل می کنیم. گراف دوگان نیز خود یک گراف صفحه ای است. اگر گراف اصلی همبند باشد، دوگان دوبار (Double Dual) آن با خود گراف اصلی یکریخت است. این مفهوم در نقشه های جغرافیایی و یافتن مسیرهای بهینه کاربرد دارد.