گراف چندگانه

در نظریه گراف گراف چندگانه یا شبه گراف به گرافی گفته می شود که مجاز است یالهای چندگانه داشته باشد که به آنها یالهای موازی هم گفته می شود.
V مجموعهٔ گره ها یا رأس های گراف است.
E مجموعهٔ چندگانه ای از زوج نامرتب یال ها که لبه ها یا خط نامیده می شوند.
بنابراین دو راس ممکن است با بیش از یک یال بهم متصل شوند. گراف چندگانه را می توان بازوج مرتب(G=(V, E معرفی کرد که در آن
یال های چندگانه یال هایی هستند که بین دو راس معین و مشترک قرار می گیرند. یال های چندگانه با درجهٔ dij بین راسهای i و j برابرند بایک عدد صحیح dij که 1 <dij به عنوان درایه ی (i,j)ماتریس مجاورت گراف چندگانه نوشته می شود. درایهٔ 0<dkk که مربوط به قطر ماتریس مجاورت گراف است بیانگر وجود حلقه روی آن راس است. شکل ۲ بیانگر مثالی از گراف چندگانه وماتریس مجاورت آن است. توجه داریم که این گراف همچنان متقارن است. اما ممکن است درایه های غیر از قطر اصلی آن هر عددی بزرگترمساوی از ۰ باشد و درایه های قطر اصلی آن ۱ نیز باشد.
در بعضی منابع به گراف چندگانه اجازهٔ داشتن حلقه که عبارتست از یالی که راسی را به خودش وصل می کند می دهند که گراف چندگانهٔ دارای حلقه را شبه گراف می نامند. در حالی که واژهٔ گراف چندگانه فاقد حلقه است.