رسم زائدي

في الرياضيات، المخطط الزائدي أو الرسم الزائدي (بالإنجليزية: Hypergraph) هو تعميم لمفهوم الرسم البياني أو المخطط والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، الرسم الزائدي   هو الزوج المرتب  حيث  هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة  هي مجموعة غير خاليه جزئيه من . عناصر المجموعة   تسمى أضلاع زائديه او أضلاع. بالتالي    هي مجموعة غير خاليه من مجموعة القوه .  حجم مجموعة الرؤوس يسمى رتبة الرسم الزائدي بينما حجم مجموعة الاضلاع يسمى حجم الرسم الزائدي.
في حين أن أضلاع الرسم البياني يحتوي على عنصرين فقط من مجموعة الرؤوس،  الأضلاع الزائدية هي مجموعات مختارة من الرؤوس، ومن الممكن أن تحتوي على أي عدد من الرؤوس. لكن الغالب يرغب بدراسة الرسوم الزائديه التي كل أضلاعها تحتوي على نفس العدد من الرؤوس. الرسم الزائدي ذو أضلاع موحدة السعة   (k-uniform hypergraph  ) هو الرسم الزائدي الذي كل ضلع زائدي به   من الرؤوس، أو بمعنى آخر هو الرسم الزائدي الذي أضلاعه الزائدية هي مجموعات بها   من الرؤوس. فبالتالي، الرسم الزائدي ذو اضلاع سعتها 2 هو الرسم البياني المعروف، والرسم الزائدي ذو الاضلاع الموحدة بسعة 3 هو مجموعة من المجموعات الثلاثية، أي بها 3 عناصر.  الرسم الزائدي يسمى أيضاً بنظام المجموعة أو عائلة من المجموعات والمستوحاة من مجموعة شاملة.
الرسومات الزائدية يمكن اعتبارها كهياكل الوقوع (incidence structures). وبصورة خاصة، يوجد  مخطط وقوع ثنائي التجزئة ( incidence graph" or Levi graph ) مقابل كل رسم زائدي. بالمقابل،  ليس كل الرسومات البيانية الثنائية التجزئة يمكن إعتبارها كرسومات وقوع لرسومات زائدية.

المخططات الزائدية لها مسميات عديدة. ففي الهندسة الحاسوبية يسمى المخطط الزائدي في بعض الاحيان بـ  range space  وبالتالي أضلاعه الزائدية تسمى ranges . تسمى الرسوم الزائديه في نظرية اللعب التعاوني بالألعاب البسيطة وينطبق نفس المسمى لحل المشاكل في نظرية الإختيار الإجتماعي. تسمى الأضلاع الزائدية في بعض الدراسات بالروابط الزائدية ( hyperlinks ) أو موصلات ( connectors ).
يوجد أنواع خاصة من الرسومات الزائدية والمصنفه حسب سعة الأضلاع الزائديه بها. فمثلا الرسم الزائدي من السعة  كما وضح أعلاه. ورسم زائدي اخر يسمى clutters والذي به كل ضلع زائدي ليس محتوى بأي ضلع زائدي آخر بنفس الرسم الزائدي.  بالمقابل، الرسومات الزائديه التي تحتوي على كل المجموعات الجزئية من أي ضلع زائدي بها تسمى بـ abstract simplicial complexes.

نمذجة المخطط ثنائي التجزئة

يمكن تمثيل آي رسم زائدي   برسم ثنائي التجزئه  كما يلي: المجموعات  و  تمثل تجزئات لـ  و   هو ضلع في إذا وفقط إذا كان كل رأس  ينتمي للضلع الزائدي   في  . بالمقابل ليس كل رسم ثنائي تجزئة  تمثل رسم زائدي . يسمى هـذا الرسم الثنائي برسم الوقوع .

بدون دورة (Acyclicity)

يوجد عدة مصطلحات غير متكافئة للرسومات الزائديه بدون دورات ٫ بعكس الرسم الغير موجه والذي به تعريف موحد للدورات وللرسومات بدون دورات. 
عرف العالم بيرج ( Claude Berge) آول تعريف للرسومات الزائديه بدون دورات  : يكون الرسم الزائدي هو رسم خالي من الدورات  إذا كان رسم الوقوع المقابل له لايحتوي على اي دورة. هذا التعريف يعتبر محدود جداً٫ فعلى سبيل المثال إذا كان الرسم الزائدي يحتوي على زوج من الرؤوس المختلفة   و زوج من الآضلاع الزائديه المختلفة  بحيث آن    و  فإنه يمكن اختبار انه لايحتوي على دوره بزمن خطي بواسطة رسم الوقوع له.يوجد تعريف آخر المسمى ب  α-acyclicity آضعف ومختلف من  تعريف بيرج .
يمكن بزمن خطي تحديد ماإذا كان اي رسم زائدي هو α-acyclicity .

التشاكل والمساواه

تشاكل  رسوم زائدي هو داله من مجموعة رؤوس رسم زائدي إلى مجموعة رؤوس رسم زائدي آخر بحيث كل ضلع هو صوره لضلع بالرسم الزائدي المقابل.
الرسم الزائدي  هو تشاكل احادي للرسم الزائدي  ونكتب   إذا كان يوجد تقابل    وتبديله   لـ  بحيث آن  . بالتالي تسمى دالة التقابل  في هذه الحاله بتشاكل احادي للرسومات. لاحظ ان   إذا وفقط اذا كان  .

أمثلة

ليكن لدينا الرسم الزائدي  والذي مجموعة أضلاعه حيث
.
والرسم الزائدي  والمعرف بمجموعة أضلاعه    حيث  
.
بالتالي فإن الرسمين  الزائدين   و  متشاكلان حيث الداله   معرفه كالتالي:
.
هذين الرسمين متشاكلان لكن ليس تشاكل قوي ( strongly isomorphic ) لأنه يوجد رأس  في   ينتمي للأضلاع  أي أن 
لكن لايوجد رأس في   بحيث ينتمي للأضلاع  لأن .
في هذا المثال الرسمين الزائدين  و  متكافئين  ونكتب في هذه الحاله  .  أيضا رسومهم المزدوجه متشاكله٫ أي أن .

الرسوم الزائديه المتماثله

رتبة ( rank )  رسم زائدي  ويرمز له بالرمز   هو أكبر سعة لآي من اضلاع الرسم الزائدي. يسمى الرسم الزائدي الذي كل ضلع فيه يحتوي على نفس العدد من الرؤوس مساوي للعدد   بالرسم الزائدي الموحد السعه ٫ ويسمى ايضا hypergraph-. بالتالي فإن الرسم  هو عباره عن  رسم زائدي من السعه  .
درجة الرآس   ويرمز له بالرمز  هي عدد الاضلاع التي تحتوي على هذا الرآس. يسمى الرسم الزائدي بمنتظم من الدرجه  (   regular- ) اذا كان درجة كل رآس فيه تساوي  .
الرسم الزائدي المزدوج لرسم زائدي موحد السعه هو منتظم والعكس صحيح.

القواطع ( Transversals)

يٍُعرف قاطع رسم زائدي   بالمجموعة   التي تتقاطع مع كل ضلع في  بمجموعه غير خالية من الرؤوس. يطلق على  بآنه القاطع الآصغر اذا كان لايوجد اي مجموعه جزئيه فعليه من وتمثل قاطع. الرسم الزائدي القاطع ( transversal hypergraph ) للرسم الزائدي هو رسم زائدي  والذي مجموعة آضلاعه  تحتوي على كل القواطع الصغرى لـ .
يوجد تطبيقات لحساب الرسم الزائدي القاطع في امثلة التراكيب و في نظرية الالعاب وفي عدة فروع من علوم الحاسب على سبيل المثال في التعلم الألي   و فهرسة قواعد البيانات  و  تنقيب البيانات  وأمثلية البرمجيات و satisfiability problem.

مسألة تلوين الرسوم الزائدية ( Hypergraph coloring)

في تلوين الرسم الزائدي التقليدي٫ يتم تعيين لون واحد من ألوان المجموعة   لكل رأس بالرسم الزائدي بحيث أن أي ضلع زائدي يحتوي على الأقل رأسين بألوان مختلفه. بمعنى آخر، لايمكن الحصول على ضلع  بلون واحد فقط وبه على الأقل رأسين. هذا التعريف هو تعميم مباشر لتلوين الرسومات. يسمى أصغر عدد من الألوان المختلفه والممكن استخدامها بتلوين رسم زائدي يسمى بـ chromatic number للرسم الزائدي. 
الرسومات الزائديه التي يوجد بها عالأكثر من الألوان تُلقب بـ k-colorable. الرسومات الزائديه ثنائي التلوين ( 2-colorable )  هي رسوم زائديه ثنائية التجزئه.
يوجد العديد من التعاريف والتي تعمم مسألة تلوين الرسوم الزائديه. أحد هذه التعاريف التي تسمى بمسألة تلوين مختلط للرسم الزائدي (mixed hypergraph coloring) والتي تسمح بوجود أضلاع موحدة اللون. يوجد رسوم زائديه غير قابله للتلوين لأي عدد من الألوان. بمسألة التلوين المختلط وعندما يكون الرسم الزائدي قابل للتلوين فإن أصغر وأكبر عدد مستخدم من الألوان تُعتبر على التوالي حد سفلي وعلوي لـ chromatic number .