تعریف گراف

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

1. مجموعه‌ی $E$ می‌تواند تهی باشد.
2. مجموعه‌ی $V$ یا $E$ می‌تواند نامتناهی باشد که در آن صورت به گراف حاصل گراف نامتناهی می‌گویند.(ما در این مقاله تنها به گراف‌های متناهی می‌پردازیم که هر دو مجموعه‌ی $V$ و $E$ متناهی هستند.)

حال فرض کنید یک شبکه کامپیوتری از مراکز داده و پیوندهای ارتباطی بین آن ها داریم. می‌توانیم برای نشان دادن این شبکه‌ی کامپیوتری به جای هر مرکز داده از نقطه و به جای هر پیوند ارتباطی از یک خط استفاده کنیم.(شکل ۱) این شبکه می‌تواند به وسیله‌ی یک گراف هم مدل شود که در آن گراف هر رأس، نمایان گر یک مرکز داده و هر یال نشان دهنده‌ی یک پیوند ارتباطی باشد. در کل می‌توانیم یک گراف را با استفاده از نقطه ها و خط(خم)ها به تصویر بکشیم که در آن یال ها با استفاده از اتصال نقاط شکل می‌گیرند.

همانطور که در شکل ۱ می‌بینیم هیج یالی رئوس رأس ابتدایی و انتهایی آن یکی نیست(حلقه نیست) و بین هر دو رأس تنها یک یال وجود دارد. با این مقدمه می‌توانیم بگوییم به گرافی که هر یال آن به دو رأس مختلف متصل باشد و هر دو یال متفاوت آن دارای یک جفت رأس مشترک نباشند گراف ساده می‌گوییم.

در یک شبکه‌ی کامپیوتری بعضی اوقات لازم است که بین دو مرکز داده بیشتر از یک پیوند ارتباطی موجود باشد.(شکل ۲) برای مدل کردن از این قبیل شبکه ها ما به گرافی نیاز داریم که که بین دو رأس آن بیشتر از یک اتصال یال موجود باشد. به گرافی که ممکن است که در بین دو رأس آن چندین یال وجود داشته باشد گراف چندگانه می‌گوییم.

بعضی اوقات در یک شبکه‌ی کامپیوتری برای گرفتن بازخورد ما نیاز داریم تا یک پیوند ارتباطی بین یک مرکز ارتباطی و خودش ایجاد کنیم.(شکل ۳) برای مدل کردن این شبکه نیاز داریم تا گرافمان شامل یالی از یک رأس به خودش باشد که به آن طوقه‌یا حلقه می‌گوییم و بعضی اوقات ما نیاز داریم تا یک رأس بیش از یک حلقه داشته باشد. به گرافی که ممکن است شامل حلقه ها باشد و همچنین امکان دارا بودن چند یال بین دو یا یک رأس را داراست شبه گراف می‌گوییم.

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

گاهی اوقات ما نیاز داریم تا به‌یال‌های یک گراف جهت بدهیم به عنوان مثال در یک شبکه‌ی کامپیوتری بعضی از پیوند‌های ارتباطی ممکن است فقط در یک جهت کار بکند.(شکل ۴) برای مدل کردن این نوع شبکه‌های کامپیوتری از گراف جهت دار استفاده می‌کنیم. هر یال از یک گراف جهت دار به‌یک جفت رأس مرتب وابسته می‌باشد. یک گراف جهت دار $G = (V, E)$ شامل یک مجموعه ناتهی از رئوس $(V)$ و یک مجموعه از یال‌های (خم ها) جهت دار است.

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

در بعضی از شبکه‌های کامپیوتری پیوند‌های ارتباطی چندگانه بین دو مرکز داده وجود دارد که هر کدام فقط در یک جهت عمل می‌کنند.(شکل ۵) برای مدل کردن این نوع شبکه ها، می‌توانیم از گراف‌های جهت داری استفاده کنیم که دارای یال‌های جهت دار چندگانه بین دو رأس هستند. به گراف جهت داری که دارای یال‌های جهت دار چندگانه باشند، گراف جهت دار چندگانه می‌گوییم.

به گراف هایی که شامل هر دو نوع یال‌های جهت دار و بی جهت باشد گراف ترکیبی می‌گوییم.