رسم زائدي

مثال لمخطط زائدي مجموعة الرؤوس هنا هي $X=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$ ومجموعة الأضلاع هي $E=\{e_1,e_2,e_3,e_4\}$ حيث $e_1=\{v_1,v_2,v_3\},e_2=\{v_2,v_3\},e_3=\{v_3,v_5,v_6\},e_4=\{v_4\}$. هذا الرسم الزائدي من الرتبه 7 وسعته 4. بعض الأضلاع الزائدية هنا تحتوي على أكثر من رأسين. الأضلاع تم توضيحها بالألوان.

في الرياضيات، المخطط الزائدي أو الرسم الزائدي (بالإنجليزية: Hypergraph)‏ هو تعميم لمفهوم الرسم البياني أو المخطط والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، الرسم الزائدي $H$ هو الزوج المرتب $H=(X,E)$ حيث $X$ هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة $E$ هي مجموعة غير خاليه جزئيه من $X$. عناصر المجموعة $E$ تسمى أضلاع زائديه أو أضلاع. بالتالي $E$ هي مجموعة غير خاليه من مجموعة القوه $\mathcal{P}(X)\setminus \{\mathrm{\varnothing }\}$. حجم مجموعة الرؤوس يسمى رتبة الرسم الزائدي بينما حجم مجموعة الاضلاع يسمى حجم الرسم الزائدي.

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

الرسومات الزائدية يمكن اعتبارها كهياكل الوقوع (incidence structures). وبصورة خاصة، يوجد مخطط وقوع ثنائي التجزئة (incidence graph" or Levi graph ) مقابل كل رسم زائدي. بالمقابل، ليس كل الرسومات البيانية الثنائية التجزئة يمكن اعتبارها كرسومات وقوع لرسومات زائدية.

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

يوجد أنواع خاصة من الرسومات الزائدية والمصنفه حسب سعة الأضلاع الزائديه بها. فمثلا الرسم الزائدي من السعة $k$ كما وضح أعلاه. ورسم زائدي اخر يسمى clutters والذي به كل ضلع زائدي ليس محتوى بأي ضلع زائدي آخر بنفس الرسم الزائدي. بالمقابل، الرسومات الزائديه التي تحتوي على كل المجموعات الجزئية من أي ضلع زائدي بها تسمى بـ abstract simplicial complexes.

مصطلحات

تعاريف

يوجد أنواع مختلفه من الرسوم الزائديه، منها

• الرسم الزائدي الخالي: والذي لايحتوي على أي ضلع زائدي.
• الرسم الزائدي المتعدد أو الغير بسيط: وهو الرسم الزائدي الذي ممكن ان يحتوي على عروة أو اضلاع مكرره وهو عباره عن ضلعين يحتويان على نفس مجموعة الرؤوس.
• الرسم الزائدي البسيط وهو رسم زائدي لايحتوي على عروات ولا أضلاع مكررة.
• الرسم الزائدي المنتظم ذو الدرجة $d$ (regular hypergraph-$d$): هو رسم زائدي الذي كل كل رأس به له نفس الدرجة $d$ .

يوجد عدة مصطلحات للمصطلح المقابل لـ الرسم الجزئي في الرسم الزائدي لأن أضلاع الرسم الزائدي ممكن أن تحتوي على أي عدد من الرؤوس. من هذه المسميات يعرف بالرسم الزائدي الثانوي (subhypergraphs) والرسم الزائدي الجزئي (partial hypergraphs) و section hypergraphs وسيتم تعرف كل من هذه المصطلحات كما موضح أدناه.

ليكن $H=(X,E)$ رسم زائدي مكون من الرؤوس $X=\{x_i|i\in I_v\}$ولديه مجموعة الأضلاع

$E=\{e_i:i\in I_e\wedge e_i\subseteq X\wedge e_i\ne \mathrm{\varnothing }\},$

حيث $I_v$ و $I_e$ هما مجموعتي الترميز index sets للرؤوس والأضلاع على التوالي.

الرسم الزائدي الثانوي (subhypergraphs) من الرسم الزائدي $H$ هو رسم زائدي مأخوذ من $H$ مع حذف بعض الرؤوس. بصيغة رياضية، الرسم الزائدي الجزئي $H_A$ المولد بواسطة $A\subseteq X$ معرف كالآتي:

$H_A=(A,\{e\cap A|e\in E\wedge e\cap A\ne \mathrm{\varnothing }\}.$

توسعة (extension) الرسم الزائدي الثانوي هو رسم زائدي حيث كل ضلع من $H$ هو محتوى جزئيا بالرسم الزائدي الثانوي $H_A$ ومحتوى كليا في التوسعة $Ex(H_A)$ . رياضيا:

$Ex(H_A)=(A\cup A^{\prime },E^{\prime })$ حيث $A^{\prime }={\bigcup }_{e\in E}e\setminus A$ و $E^{\prime }=\{e\in E|e\subseteq (A\cup A^{\prime })\}$ .

الرسم الزائدي الجزئي هو رسم زائدي من مع حذف بعض الآضلاع الزائديه. بصيغه رياضية، ليكن $J\subset I_e$ مجموعة جزئية من مجموعة ترميز الآضلاع٫ الرسم الزائدي الجزئي المولد بالمجموعة $J$ هو رسم زائدي $(X,\{e_i|i\in J\})$.

لتكن $A\subset X$ مجموعة معطاه، يعرف section hypergraph بآنه رسم زائدي جزئي معرف كالتالي:

$H\times A=(A,\{e_i|i\in I_e\wedge e_i\subseteq A\})$.

الرسم الزائدي المزدوج (dual hypergraph) $H^{*}$ للرسم الزائدي $H$ هو رسم زائدي مجموعة رؤوسه هي $\{e_i\}$ وآضلاعه معطى بالمجموعة $\{X_m\}$ حيث $X_m=\{e_i|x_m\in e_i\}$.

لاحظ آن الرسم الزائدي المزدوج لـ $H^{*}$ هو $H$ ٫ آي آن $(H^{*}{)}^{*}=H$.

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

يمكن تمثيل آي رسم زائدي $H$ برسم ثنائي التجزئة $BG$ كما يلي: المجموعات $X$ و $E$ تمثل تجزئات لـ $BG$ و $\{x_i,e_i\}$ هو ضلع في $BG$إذا وفقط إذا كان كل رأس $x_i$ينتمي للضلع الزائدي $e_i$ في $H$ . بالمقابل ليس كل رسم ثنائي تجزئة تمثل رسم زائدي. يسمى هـذا الرسم الثنائي برسم الوقوع .

بدون دورة (Acyclicity)

يوجد عدة مصطلحات غير متكافئة للرسومات الزائديه بدون دورات ٫ بعكس الرسم الغير موجه والذي به تعريف موحد للدورات وللرسومات بدون دورات.

عرف العالم بيرج (Claude Berge) آول تعريف للرسومات الزائديه بدون دورات: يكون الرسم الزائدي هو رسم خالي من الدورات إذا كان رسم الوقوع المقابل له لايحتوي على أي دورة. هذا التعريف يعتبر محدود جداً٫ فعلى سبيل المثال إذا كان الرسم الزائدي يحتوي على زوج من الرؤوس المختلفة $v\ne v^{\prime }$ وزوج من الآضلاع الزائديه المختلفة $f\ne f^{\prime }$ بحيث آن $v,v^{\prime }\in f$ و $v,v^{\prime }\in f^{\prime }$ فإنه يمكن اختبار انه لايحتوي على دوره بزمن خطي بواسطة رسم الوقوع له.يوجد تعريف آخر المسمى ب α-acyclicity آضعف ومختلف من تعريف بيرج.

يمكن بزمن خطي تحديد ماإذا كان أي رسم زائدي هو α-acyclicity.

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

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

الرسم الزائدي $H=(X,E)$ هو تشاكل احادي للرسم الزائدي $G=(Y,F)$ ونكتب $H\simeq G$ إذا كان يوجد تقابل $\varphi :X\to Y$ وتبديله $\pi$ لـ $I$ بحيث آن $\varphi (e_i)=f_{\pi (i)}$ . بالتالي تسمى دالة التقابل $\varphi$ في هذه الحالة بتشاكل احادي للرسومات. لاحظ ان $H\simeq G$ إذا وفقط إذا كان $H^{*}\simeq G^{*}$.

أمثلة

ليكن لدينا الرسم الزائدي $H$ والذي مجموعة أضلاعه $H=\{e_1,e_2,e_3,e_4,e_5,e_6\}$حيث

$e_1=\{a,b\},e_2=\{b,c\},e_3=\{c,d\},e_4=\{d,a\},e_5=\{b,d\},e_6=\{a,c\}$.
والرسم الزائدي $G$ والمعرف بمجموعة أضلاعه $G=\{f_1,f_2,f_3,f_4,f_5,f_6\}$ حيث

$f_1=\{\alpha ,\beta \},f_2=\{\beta ,\gamma \},f_3=\{\gamma ,\delta \},f_4=\{\delta ,\alpha \},f_5=\{\alpha ,\gamma \},f_6=\{\beta ,\gamma \}$.

بالتالي فإن الرسمين الزائدين $H$ و $G$ متشاكلان حيث الدالة $\varphi$ معرفه كالتالي:

$\varphi (a)=\alpha ,\varphi (b)=\beta ,\varphi (c)=\gamma ,\varphi (d)=\delta$.

هذين الرسمين متشاكلان لكن ليس تشاكل قوي (strongly isomorphic) لأنه يوجد رأس $a$ في $H$ ينتمي للأضلاع $1,3,6$ أي أن $e_1\cap e_4\cap e_6=\{a\}$

لكن لايوجد رأس في $G$بحيث ينتمي للأضلاع $1,3,6$ لأن $f_1\cap f_4\cap f_6=\mathrm{\varnothing }$.

في هذا المثال الرسمين الزائدين $H$ و $G$ متكافئين ونكتب في هذه الحالة $H\equiv G$ . أيضا رسومهم المزدوجه متشاكله٫ أي أن $H^{*}\cong G^{*}$.

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

رتبة (rank) رسم زائدي $H$ ويرمز له بالرمز $r(H)$ هو أكبر سعة لآي من اضلاع الرسم الزائدي. يسمى الرسم الزائدي الذي كل ضلع فيه يحتوي على نفس العدد من الرؤوس مساوي للعدد $k$ بالرسم الزائدي الموحد السعه $k$٫ ويسمى أيضا hypergraph-$k$. بالتالي فإن الرسم هو عباره عن رسم زائدي من السعه $2$ .

درجة الرآس $v$ ويرمز له بالرمز $d(v)$ هي عدد الاضلاع التي تحتوي على هذا الرآس. يسمى الرسم الزائدي بمنتظم من الدرجة $k$ (regular-$k$) إذا كان درجة كل رآس فيه تساوي $k$ .

الرسم الزائدي المزدوج لرسم زائدي موحد السعه هو منتظم والعكس صحيح.

القواطع (Transversals)

يٍُعرف قاطع رسم زائدي $H=(X,E)$ بالمجموعة $T\subseteq X$ التي تتقاطع مع كل ضلع في $H$ بمجموعه غير خالية من الرؤوس. يطلق على $T$ بآنه القاطع الآصغر إذا كان لايوجد أي مجموعه جزئيه فعليه من $T$وتمثل قاطع. الرسم الزائدي القاطع (transversal hypergraph) للرسم الزائدي $H$هو رسم زائدي $(X,F)$ والذي مجموعة آضلاعه $F$ تحتوي على كل القواطع الصغرى لـ $H$.

يوجد تطبيقات لحساب الرسم الزائدي القاطع في امثلة التراكيب وفي نظرية الألعاب وفي عدة فروع من علوم الحاسب على سبيل المثال في التعلم الألي وفهرسة قواعد البيانات وتنقيب البيانات وأمثلية البرمجيات وsatisfiability problem.

مصفوفة الوقوع (Incidence matrix)

لتكن $V=\{v_1,v_2,\dots ,v_n\}$ مجموعة الرؤوس و $E=\{e_1,e_2,\dots ,e_m\}$ مجموعة الآضلاع الزائديه. كل رسم زائدي له مصفوفة وقوع $A=(a_{ij})$ من النوع $n\times m$ حيث:

$a_{ij}=\{\begin{array}{cc}1& \mathrm{i}\mathrm{f}{v}_i\in e_j\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}$

يمثل منقول مصفوفة الوقوع $A^t$ الرسم الزائدي المزدوج $H^{*}=(V^{*},E^{*})$ لـ $H$.

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

في تلوين الرسم الزائدي التقليدي٫ يتم تعيين لون واحد من ألوان المجموعة لكل رأس بالرسم الزائدي بحيث أن أي ضلع زائدي يحتوي على الأقل رأسين بألوان مختلفه. بمعنى آخر، لايمكن الحصول على ضلع بلون واحد فقط وبه على الأقل رأسين. هذا التعريف هو تعميم مباشر لتلوين الرسومات. يسمى أصغر عدد من الألوان المختلفه والممكن استخدامها بتلوين رسم زائدي يسمى بـ chromatic number للرسم الزائدي.

الرسومات الزائديه التي يوجد بها عالأكثر $k$من الألوان تُلقب بـ k-colorable. الرسومات الزائديه ثنائي التلوين (2-colorable) هي رسوم زائديه ثنائية التجزئة.

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

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

يمكن تمثيل هذه الدوره الإلكترونيه برسم زائدي بأربع رؤوس والملونه باللون الأبيض بالشكل المعطى والمرتبطة بواسطة ثلاث أضلاع زائديه على شكل أشجار.

Hypergraph grammars