معرفی گراف

یک گراف متشکل است از مجموعه ای از نقاط و مجموعه ای از پاره خط‌ها. که به هر یک از نقاط رأس و به هر یک از پاره خط‌ها یال می‌گوییم.

یال‌ها می‌توانند به صورت منحنی نیز رسم شوند و در هر سر یک یال باید رأسی قرار داشته باشد.

برای نمایش گراف از رسم نمودار آن و نمادهای ریاضی استفاده میکنیم.

مجموعه رأس‌های گراف \(G\): \(V(G)=\left\{v_1,v_2,\cdots,v_n\right\}\ \)

مجموعه یال‌های گراف \(G\): \(V(G)=\left\{v_nv_u,\cdots\right\}\)

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

مثال

\[V=\left\{a,b,c,d\right\}\ E\left\{(a,b),(a,c),(c,a),(d,b)\right\}\]