گراف (ریاضی)
تعریف

گراف ساده: یک گراف از مجموعه‌ای غیر خالی از اشیاء به نام رأس تشکیل شده، که آن را با  V نشان می‌دهیم، و مجموعه‌ای شامل یال‌ها، که رأس‌ها را به هم وصل می‌کنند و با  E نمایش می‌دهیم. یک چنین گرافی را با  G=(V,E) نشان می‌دهیم. اگر یال  y دو رأس  v_{1} و  v_{2} را به هم وصل کند می‌نویسیم  y=\lbrace v_{1},v_{2}\rbrace .
گراف جهت‌دار: منظور از گراف جهت دار گرافی است که یال‌ها در آن دارای جهت هستند. گراف جهت دار G زوج مرتب (V,E) است که V مجموعه‌ای ناتهی و اعضای E زوجهای مرتب از اعضای V هستند.
همانند گرافهای ساده، به اعضایV، راسهای G و به اعضای E، یال‌های G می‌گوییم. همچنین به هر گراف جهت‌دار نموداری در صفحه نسبت می‌دهیم. به این صورت که به ازای هر راس G نقطه‌ای در صفحه در نظر می‌گیریم و به ازای هر یال مانند (u,v) کمانی بین u و v رسم می‌کنیم و روی این کمان فلشی از u به v می‌گذاریم.
گراف مخلوط: گرافی است که در آن ممکن است برخی یال‌ها جهت داشته باشند و برخی بدون جهت باشند. گراف مخلوط G، سه‌تایی مرتب G = (V, E, A) است که در آن V مجموعهٔ رئوس، E یال‌های بدون جهت و A یال‌های جهت دارمی‌باشند. گراف ساده و گراف جهت‌دار حالت خاصی از گراف جهت دار می‌باشند.
گراف وزن‌دار: گراف وزن‌دار، گرافی است که به هر یک از یال‌ها یا به هریک از راس‌های آن عددی نسبت داده شده است که وزن آن یال یا راس می‌باشد. وزن یال می‌تواند نشان دهندهٔ هزینه، مسافت، زمان یا هر مشخصه دیگری از یال باشد. بعضی از نویسنده‌ها به گراف وزن‌دار گراف شبکه‌ای می‌گویند.
قراردادها:
مرتبه و اندازهٔ یک گراف: تعداد رأس‌های گراف G یعنی |V(G)| را مرتبهٔ آن گراف می‌گوییم و باp(G) نمایش می‌دهیم و تعداد یال‌های گراف یعنی |E(G)| را اندازهٔ گراف G می‌گوییم و با q(G) نمایش می‌دهیم. معمولاً برای راحتی کار به جای p(G) از p و به جای q(G) از q استفاده می‌کنیم.
درجهٔ یک رأس: درجهٔ رأس v در گراف G برابر است با تعداد یال‌هایی از گراف G که به رأس v متصل اند و آن را با degG (v) یا به‌طور ساده‌تر با deg (v) یا d (v) نمایش می‌دهیم. اگر درجهٔ یک رأس فرد باشد آن را رأس فرد و اگر زوج باشد آن را رأس زوج می‌نامیم.
گراف K ـ منتظم: گرافی را که درجهٔ تمام رئوس آن با هم مساوی و برابر با عدد k باشند، گراف k - منتظم می‌نامیم.
رأس تنها: به رأسی که درجهٔ آن صفر باشد؛ یعنی هیچ یالی به آن متصل نباشد، رأس تنها (یا ایزوله) می‌گوییم.
گراف تهی: گرافی را که تمام رئوس آن رأس تنها باشند، یعنی هیچ یالی نداشته باشد، گراف تهی می‌نامیم؛ بنابراین منظور از گراف تهیِ n رأسی، گرافی شامل n رأسِ تنها و بدون یال است.
دو رأس مجاور (همسایه): دو رأس u و v را دو رأسِ همسایه یا مجاور گوییم هرگاه توسط یالی به هم وصل شده باشند، یعنیuv ∈ E(G).
مجموعهٔ همسایه‌های یک رأس: فرض کنیم v ∈ V(G)، به مجموعهٔ رأس‌هایی از گراف G که به رأس v متصل هستند، "همسایگی باز رأسv " می‌گوییم و با NG(v) نمایش می‌دهیم. اضافه کردنِ خودِ رأسِ v به NG(v) "همسایگی بستهٔ رأسv " را به دست می‌دهد که آن را با NG[v] نمایش می‌دهیم. می‌توان این دو مجموعه را به صورت زیر نمایش داد:
NG (v) = {u ∈ V (G)∶ uv ∈ E (G)}
NG[v] =NG (v) ∪{v}
دو یال مجاور: دو یال را مجاور گوییم هرگاه رأسی وجود داشته باشد که هر دوی آنها به آن متصل باشند.
بزرگ‌ترین و کوچک‌ترین درجهٔ یک گراف: بزرگ‌ترین عدد در بین درجات رئوس گراف G را با∆ (G) و کوچک ترینِ آنها را با δ (G) نمایش می‌دهیم و به ترتیب آنها را ماکزیمم و مینیمم درجهٔ گراف می‌نامیم.
زیرگراف: یک زیرگراف از گراف G گرافی است که مجموعهٔ رئوس آن زیرمجموعه ای از مجموعهٔ رئوس گراف G، و مجموعهٔ یال‌های آن زیرمجموعه ای از مجموعهٔ یال‌های G باشد.
مکمل یک گراف: مکمل گرافی مانند G که آن را با G^c یا G ̅ نمایش می‌دهیم گرافی است که مجموعهٔ رئوس آن همان مجموعهٔ رئوس گراف G است و بین دو رأس از G^cیک یال است اگر و تنها اگر بین همان دو رأس درG یالی وجود نداشته باشد.
گراف کامل: گرافی را که هر رأس آن با تمام رئوسِ دیگرِ، مجاور باشد گراف کامل می‌نامیم. گراف کاملِ n رأسی را با Kn نمایش می‌دهیم. می‌توان گفت Kn یک گراف n رأسی وn-1 ــ منتظم است.
مسیر: اگر u و v دو رأس از گراف G باشند، یک مسیر از u به v (یک v ــ u مسیر) در G دنباله ای از رئوس دوبه دو متمایز در G است که از u شروع و به v ختم می‌شود به طوری که هر دو رأس متوالی این دنباله در G مجاور هم باشند. طول یک مسیر برابر است با تعداد یال‌های موجود در آن مسیر (یکی کمتر از تعداد رئوس موجود در آن مسیر). قرارداد می‌کنیم که دنبالهٔ متشکل از تنها یک رأسِv، یک مسیر است با طول صفر از رأس v به خودش.
(گرافی را که تنها از یک مسیرِ n رأسی تشکیل شده باشد با Pn نمایش می‌دهیم).
دور: دنبالهٔ (n ≥ 3) v1 v2 v3 … vn v1 از رئوس دو به دو متمایز که در آن هر رأس با رأس بعدی مجاور است را یک دور به طول n می‌نامیم. (گرافی را که تنها از یک دورِ n رأسی تشکیل شده باشد را با Cn نمایش می‌دهیم)
همبندی و ناهمبندی یک گراف: گراف G را همبند می‌نامیم هرگاه بین هر دو رأسِ آن حداقل یک مسیر وجود داشته باشد، در غیر این صورت آن را ناهمبند می‌نامیم.