مالتيغراف

في الرياضيات ، وتحديداً في نظرية المخططات ، يُعرف المخطط المتعدد بأنه مخطط يُسمح له بوجود حواف متعددة (تُسمى أيضاً الحواف المتوازية ^{[ 1 ]} )، أي الحواف التي لها نفس العقد الطرفية . وبالتالي، قد يكون رأسان متصلين بأكثر من حافة واحدة.

هناك مفهومان متميزان للحواف المتعددة:

• الحواف التي لا تحمل هوية خاصة بها : تُحدد هوية الحافة فقط من خلال العقدتين اللتين تربطهما. في هذه الحالة، يعني مصطلح "الحواف المتعددة" أن الحافة نفسها يمكن أن تظهر عدة مرات بين هاتين العقدتين.
• الحواف ذات الهوية الخاصة : الحواف هي كيانات أولية تمامًا مثل العقد. عندما تربط عدة حواف عقدتين، فإن هذه الحواف مختلفة.

يختلف الرسم البياني المتعدد عن الرسم البياني الفائق ، وهو رسم بياني يمكن فيه للحافة أن تربط أي عدد من العقد، وليس عقدتين فقط.

بالنسبة لبعض المؤلفين، يُعتبر مصطلحا "الرسم البياني الزائف" و "الرسم البياني المتعدد " مترادفين. أما بالنسبة لآخرين، فالرسم البياني الزائف هو رسم بياني متعدد يُسمح له باحتواء حلقات .

الرسم البياني المتعدد G هو زوج مرتب G  := ( V , E ) حيث

• V مجموعة من الرؤوس أو العقد ،​
• E مجموعة متعددة من أزواج الرؤوس غير المرتبة، تسمى الحواف أو الخطوط .

الرسم البياني المتعدد G هو ثلاثية مرتبة G  := ( V , E , r ) حيث

• V مجموعة من الرؤوس أو العقد ،​
• مجموعة من الحواف أو الخطوط ،​​
• r  : E → { { x , y }  : x , y ∈ V }, تعيين لكل حافة زوج غير مرتب من عقد النهاية.

يسمح بعض المؤلفين بوجود حلقات في الرسوم البيانية المتعددة ، أي حافة تربط رأسًا بنفسه، ^{[ 2 ]} بينما يسميها آخرون الرسوم البيانية الزائفة ، ويحتفظون بمصطلح الرسم البياني المتعدد للحالة التي لا تحتوي على حلقات. ^{[ 3 ]}

الرسم البياني متعدد التوجيهات هو رسم بياني موجه يُسمح له بامتلاك أقواس متعددة، أي أقواس لها نفس عقدة المصدر والهدف. الرسم البياني متعدد التوجيهات G هو زوج مرتب G  := ( V , A ) حيث

• V مجموعة من الرؤوس أو العقد ،
• مجموعة متعددة من أزواج الرؤوس المرتبة تسمى الحواف الموجهة أو الأقواس أو الأسهم .

يمكن تعريف الرسم البياني المختلط G  := ( V , E , A ) بنفس طريقة تعريف الرسم البياني المختلط .

الرسم البياني المتعدد أو السهم G هو رباعي مرتب G  := ( V , A , s , t ) مع

• V مجموعة من الرؤوس أو العقد ،​
• مجموعة من الحواف أو الخطوط ،​​
• ${\displaystyle s:A\rightarrow V}$، مع تعيين عقدة المصدر لكل حافة،
• ${\displaystyle t:A\rightarrow V}$، مع تعيين العقدة المستهدفة لكل حافة.

يمكن استخدام هذا المفهوم لنمذجة رحلات الطيران الممكنة التي توفرها شركة طيران. في هذه الحالة، سيكون الرسم البياني المتعدد عبارة عن رسم بياني موجه يحتوي على أزواج من الحواف الموجهة المتوازية التي تربط المدن لإظهار إمكانية السفر جواً من وإلى هذه المواقع.

في نظرية الفئات، يمكن تعريف الفئة الصغيرة بأنها رسم بياني متعدد (بحواف ذات هوية خاصة بها) مزود بقانون تركيب ترابطي وحلقة ذاتية مميزة عند كل رأس تعمل كهوية يسارية ويمينية للتركيب. لهذا السبب، في نظرية الفئات، يُستخدم مصطلح " الرسم البياني " عادةً بمعنى "الرسم البياني المتعدد"، ويُطلق على الرسم البياني المتعدد الأساسي لفئة ما اسم " الرسم البياني الأساسي ".

تدعم الرسوم البيانية المتعددة والرسوم البيانية الموجهة المتعددة مفهوم تسمية الرسوم البيانية ، بطريقة مماثلة. ومع ذلك، لا يوجد توحيد في المصطلحات في هذه الحالة.

إن تعريفات الرسوم البيانية المتعددة المصنفة والرسوم البيانية المتعددة الموجهة المصنفة متشابهة، ونحن هنا نحدد الأخيرة فقط.

التعريف 1 : الرسم البياني متعدد الاتجاهات المسمى هو رسم بياني مسمى بأقواس مسماة .

بصورة رسمية: الرسم البياني المتعدد الموجه المسمى G هو رسم بياني متعدد ذو رؤوس وأقواس مُسماة . وهو في الواقع ثماني مجموعات.${\displaystyle G=(\Sigma _{V},\Sigma _{A},V,A,s,t,\ell _{V},\ell _{A})}$أين

• ${\displaystyle V}$هي مجموعة من الرؤوس و${\displaystyle A}$هي مجموعة من الأقواس.
• ${\displaystyle \Sigma _{V}}$و${\displaystyle \Sigma _{A}}$هي أبجديات محدودة من تسميات الرؤوس والأقواس المتاحة،
• ${\displaystyle s\colon A\rightarrow \ V}$و${\displaystyle t\colon A\rightarrow \ V}$هما خريطتان تشيران إلى رأس نقطة البداية ورأس نقطة النهاية لقوس،
• ${\displaystyle \ell _{V}\colon V\rightarrow \Sigma _{V}}$و${\displaystyle \ell _{A}\colon A\rightarrow \Sigma _{A}}$هما خريطتان تصفان تسمية الرؤوس والأقواس.

التعريف 2 : الرسم البياني متعدد الاتجاهات المسمى هو رسم بياني مسمى يحتوي على أقواس متعددة مسماة ، أي أقواس لها نفس رؤوس النهاية ونفس تسمية القوس (لاحظ أن هذا المفهوم للرسم البياني المسمى يختلف عن المفهوم الذي قدمته مقالة تسمية الرسم البياني ).

• شبكة متعددة الأبعاد
• مسرد مصطلحات نظرية الرسم البياني
• نظرية الرسم البياني

• بالاكريشنان، في كي (1997). نظرية الرسم البياني . ماكجرو هيل. ISBN 0-07-005489-4.
• بولوباس، بيلا (2002). نظرية الرسم البياني الحديثة . نصوص الدراسات العليا في الرياضيات . المجلد  184. سبرينغر. ISBN 0-387-98488-7.
• شارتراند، غاري ؛ تشانغ، بينغ (2012). مدخل إلى نظرية الرسوم البيانية . دوفر. ISBN 978-0-486-48368-9.
• ديستل، راينهارد (2010). نظرية الرسم البياني . نصوص الدراسات العليا في الرياضيات. المجلد  173 (  الطبعة الرابعة). سبرينغر. ISBN 978-3-642-14278-9.
• جروس، جوناثان ل.؛ يلين، جاي (1998). نظرية الرسم البياني وتطبيقاتها . مطبعة سي آر سي. رقم ISBN 0-8493-3982-0.
• جروس، جوناثان ل.؛ يلين، جاي، محرران. (2003). دليل نظرية الرسم البياني . سي آر سي. رقم ISBN 1-58488-090-2.
• هاراري، فرانك (1995). نظرية الرسم البياني . أديسون ويسلي. ISBN 0-201-41033-8.
• جانسون، سفانتي ؛ كنوت، دونالد إي .؛ لوتشاك، توماش؛ بيتيل، بوريس (1993). "نشأة المكون العملاق". الهياكل والخوارزميات العشوائية . 4 (3): 231-358 . arXiv : math/9310236 . Bibcode : 1993math.....10236J . doi : 10.1002/rsa.3240040303 . ISSN 1042-9832 . MR 1220220. S2CID 206454812 .   
• ويلسون، روبرت أ. (2002). الرسوم البيانية، والتلوين، ونظرية الألوان الأربعة . منشورات أكسفورد للعلوم. ISBN 0-19-851062-4.
• زويلينجر، دانيال (2002). جداول وصيغ الرياضيات القياسية من سي آر سي (الطبعة 31  ). تشابمان آند هول/سي آر سي. رقم ISBN 1-58488-291-3.

•  تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "الرسم البياني المتعدد" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .