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

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

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

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

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

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

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

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

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

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

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