انواع گراف

گراف ساده: هر گراف g زوج مرتبی مانند (v,e) است که در آن v مجموعه‌ای متناهی و ناتهی است و e زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی v میباشد. اعضای v را رأسهای g و اعضای e را یالهای g مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.

گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.

گراف جهت دار: هر گراف g زوج مرتبی مانند (v,e) است که در آن v مجموعه‌ای متناهی و ناتهی است و e زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای v است.

گراف مسطح: گراف مسطح گرافی است که می توان آن را در یک صفحه محاط کرد به گونه ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.