گراف بیرونی مسطح (Outerplanar Graph)، در ریاضیات (Mathematics)
انواع گراف مسطح (Planar Graph) را در آموزش زیر شرح دادیم :
گراف بیرونی مسطح (Outerplanar Graph) :
گرافی است که می توان آن را در صفحه به گونه ای رسم کرد که تمام رئوس (Vertices) روی وجه بیرونی (ناحیه نامحدود) قرار بگیرند و یال ها یکدیگر را قطع نکنند. این گراف ها زیرمجموعه ای از گراف های مسطح هستند. به بیان ساده، می توان تمام گراف را درون یک دایره بزرگ رسم کرد به طوری که همه رئوس روی محیط دایره باشند و یال ها یا داخل دایره باشند یا روی محیط. یک مثال معروف، گراف **چرخ (Wheel Graph)** با ۴ رأس (
\[ W_4 \]) است. ماکسیمال حالت این گراف ها، مثلثی شدن وجه داخلی است و تعداد یال های آن حداکثر
\[ 2n - 3 \]است.
\[ \text{max edges} = 2n - 3 \] نویسنده علیرضا گلمکانی
شماره کلید 5502
گزینه ها 
نظرات 0 0 0