گراف دوگان

در رشتهٔ ریاضی، گراف دوگان گراف G گرافی است که در هر ناحیه از گراف G یک راس دارد. بین دو راس در گراف دوگان یال وجود دارد، هرگاه دوناحیه از گراف G با یک یال از یکدیگر جدا شده باشند؛ بنابراین، متناظر با هر یال e ازگراف G یالی درگراف دوگان وجود دارد که نواحی طرفین یال e را به هم وصل می کند.
گراف دوگان یک تعمیم توپولوژیک مفاهیم هندسی چندوجهی ها و موزائیک کاری های دوبعدی است.
در گراف دوگان واژهٔ "دوگان" از آن جهت مورد استفاده قرار می گیرد که گراف دوگان بودن یک رابطهٔ متقارن و دوطرفه است یعنی اگر گراف G گراف دوگان H باشد گراف H نیز گراف دوگان G خواهد بود. هنگامی که در مورد گراف دوگان گراف G بحث می شود گراف G ممکن است یک گراف اولیه " primal graph" باشد.
بسته به نوع و خواص گراف G گراف دوگان آن متفاوت است. گراف های چند وجهی و دوبعدی گراف دوگان یکتایی دارند درحالی که بعضی گراف ها گراف دوگان یکتایی ندارند.
دوگانگی گراف های مسطح با مفهوم یک جسم چندوجهی دوگان بسیار مرتبط است. برای یک جسم چندوجهی سه بعدی، گراف این چندوجهی ( مجموعه رئوس و یال ها ) دوگان گراف آن چندوجهی دوگان است. به این علت گراف های اجسام افلاطونی به صورت جفت های دوگان می آیند. گراف K2, 2، 2 از یک ۸ وجهی منتظم، دوگان گراف مکعب است و غیره. ۴ وجهی منتظم خوددوگان است، بنابراین گراف آن یک K4 نیز هست.
یک گراف مسطح را خود دوگان گویند، اگر با گراف دوگان خود یک ریخت باشد. گراف های چرخ مجموعه ای نامحدود از گراف های خود دوگان پدیدمی آورند که از چندوجهی های خود دوگان ( هرم ها ) پدید می آیند. با این حال، گراف های خود دوگانی وجود دارند که چندوجهی نیستند، همانند گرافی که نمایش داده شده. Servatius و Christopher دو عملگر توصیف کردند، اتصال و افتراق، که می توانند برای ساخت یک گراف دوگان که یک گراف مسطح داده شده ای در بردارد به کار رود؛ به طور مثال، گراف خود دوگان نشان داده شده می توانند به عنوان adhesion از یک چهاروجهی با دوگانش ساخته شود.
با توجه با توجه به فرمول اویلر، هر گراف خود دوگان با n گره، دقیقاً 2n – ۲ یال دارد. هر گراف خود دوگان محاط شده حداقل ۴ وجه مثلثی دارد.
در یک گراف جهت دار گراف دوگان ممکن است به خوبی جهت دار شود به طوری که با چرخش هر یک از یال های گراف دوگان به اندازهٔ ۹۰ درجه در جهت ساعتگرد باعث شود که آن یال بر یال گراف اولیه منطبق شود. صرف سخن باید گفت که این حرکت ( ساختن گراف جهت دار با استفاده از چرخش۹۰ درجه ) یک رابطهٔ متقارن نیست یعنی اگر گراف G را دو بار به اندازهٔ ۹۰ درجه در راستای ساعت گرد بچرخانیم خودش تشکیل نمی شود، بلکه اگر این عمل را ۴ بار روی گراف G تکرار کنیم باعث می شود خودش تشکیل شود.