گراف

تعریف

گراف ساده $G$ را با زوج مرتب $G=(V,E)$ نمایش می‌دهند و عبارت است از:

$V=\left\{v_1,v_2,\mathrm{...},v_p\right\}$

مجموعه فوق مجموعه‌ای ناتهی و متناهی است که عناصر آن را  گره یا رأس می‌نامیم و مجموعه راس‌های گراف $G$ را با $V\left(G\right)$ نمایش می‌دهند.

$E=\left\{e_1,e_2,\mathrm{...},e_q\right\}$

مجموعه فوق زیرمجموعه‌های دوعضوی $V$ است که آنها را یال‌های $G$ می‌نامیم و مجموعه یال‌های گراف $G$ را با $E\left(G\right)$ نمایش می‌دهند.   

در این‌صورت برای هر راس $v_i$ و $v_j$ که $(i\ne j)$ توسط یال $e_k$ به‌هم متصل شده باشند، داریم:

$e_k=\left\{v_i{v}_j\right\}=v_i{v}_j;(i\ne j)$

دو راس مجاور یا دو راس همسایه

دو راس $v_i$ و $v_j$ از یک گراف که به‌وسیله یک یال $v_i{v}_j$ به‌هم متصل شده باشد را دو راس مجاور (یا همسایه) می‌گویند.

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

راس $v_1$ با رئوس $v_2$ و $v_5$ همسایه است.

راس $v_2$ با رئوس $v_1$ و $v_3$ و $v_4$ همسایه است.  

همسایگی باز راس$v$

به مجموعه راس‌هایی از گراف $G$ که به راس $v$ متصل هستند، همسایگی باز راس $v$ می‌گوییم و با $N_G\left(v\right)$ نمایش می‌دهیم.

همسایگی بسته راس$v$

اضافه کردنِ خودِ راسِ $v$ به $N_G\left(v\right)$ را همسایگی بسته راس $v$ می‌گوییم و با $N_G\left[v\right]$ نمایش می‌دهیم.   

دو یال مجاور

دو یال را مجاور گوییم هرگاه راسی وجود داشته باشد که هردوی آنها به آن راس متصل باشند.

به‌عنوان نمونه، گراف زیر در نظر بگیرید:

یال‌های $bc$ و $cd$ مجاورند.

نمودار گراف ساده

این شاخه از علم ریاضیات را گراف می‌گویند زیر می‌توان آن‌را به‌صورت تصویری معرفی نمود.

این نمایش تصویری بسیاری از خواص و ویژگی‌های گراف‌ها را به‌طور مشهودی به ما معرفی می‌کند.

برای نمایش نمودار یک گراف ساده، عضوهای مجموعه راس $V\left(G\right)$ (راس‌های گراف) را با نقاطی متمایز در صفحه مشخص می‌کنیم .

سپس از آن به‌ازای هر یال موجود در مجموعه یالی دو سر یال را با قطعه خط یا منحنی به‌هم وصل می‌نماییم.

ضمنا چگونگی رسم یال‌ها فعلا چندان اهمیتی ندارد چرا که هیچ راه منحصر به‌فردی برای رسم نمودار یک گراف موجود نمی‌باشد.

به‌عبارت دیگر برای رسم نمودار یک گراف، روش یکتایی مد نظر نیست و آن‌چه مهم است این است که باید مشخص باشد که گراف مورد نظر چند راس و چند یال دارد و کدام یال به‌کدام رئوس متصل است.

شکل‌های زیر هر دو یک گراف را نمایش می‌دهند: