بيان فائق

مثال لبيان فائق مجموعة الرؤوس هنا هي ${\displaystyle X=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}}$ ومجموعة الأضلاع هي ${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4}\}}$ حيث ${\displaystyle 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)‏ هو تعميم لمفهوم البيان والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، البيان الفائق ${\displaystyle H}$ هو الزوج المرتب ${\displaystyle H=(X,E)}$ حيث ${\displaystyle X}$ هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة ${\displaystyle E}$ هي مجموعة غير خاليه جزئيه من ${\displaystyle X}$. عناصر المجموعة ${\displaystyle E}$ تسمى وصلات فائقة أو أضلاع. بالتالي ${\displaystyle E}$ هي مجموعة غير خاليه من مجموعة القوه ${\displaystyle {\mathcal {P}}(X)\setminus \{\emptyset \}}$. حجم مجموعة الرؤوس يسمى رتبة البيان الفائق بينما حجم مجموعة الاضلاع يسمى حجم البيان الفائق.

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

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

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

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

مصطلحات

تعاريف

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

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

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

ليكن ${\displaystyle H=(X,E)}$ بيان فائق مكون من الرؤوس ${\displaystyle X=\{x_{i}|i\in I_{v}\}}$ولديه مجموعة الأضلاع

${\displaystyle E=\{e_{i}:i\in I_{e}\land e_{i}\subseteq X\land e_{i}\neq \emptyset \},}$

حيث ${\displaystyle I_{v}}$ و ${\displaystyle I_{e}}$ هما مجموعتي الترميز index sets للرؤوس والأضلاع على التوالي.

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

${\displaystyle H_{A}=(A,\{e\cap A|e\in E\land e\cap A\neq \emptyset \}.}$

توسعة (extension) البيان الفائق الثانوي هو بيان فائق حيث كل ضلع من ${\displaystyle H}$ هو محتوى جزئيا بالبيان الفائق الثانوي ${\displaystyle H_{A}}$ ومحتوى كليا في التوسعة ${\displaystyle Ex(H_{A})}$ . رياضيا:

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

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

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

${\displaystyle H\times A=(A,\{e_{i}|i\in I_{e}\land e_{i}\subseteq A\})}$.

البيان الفائق المزدوج (dual hypergraph) ${\displaystyle H^{*}}$ للبيان الفائق ${\displaystyle H}$ هو بيان فائق مجموعة رؤوسه هي ${\displaystyle \{e_{i}\}}$ وآضلاعه معطى بالمجموعة ${\displaystyle \{X_{m}\}}$ حيث ${\displaystyle X_{m}=\{e_{i}|x_{m}\in e_{i}\}}$.

لاحظ آن البيان الفائق المزدوج لـ ${\displaystyle H^{*}}$ هو ${\displaystyle H}$ ٫ آي آن ${\displaystyle (H^{*})^{*}=H}$.

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

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

بدون دورة (Acyclicity)

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

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

يمكن بزمن خطي تحديد ما إذا كان أي بيان فائق هو α-acyclicity.^[5]

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

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

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

أمثلة

ليكن لدينا البيان الفائق ${\displaystyle H}$ والذي مجموعة أضلاعه ${\displaystyle H=\{e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\}}$حيث

${\displaystyle e_{1}=\{a,b\},e_{2}=\{b,c\},e_{3}=\{c,d\},e_{4}=\{d,a\},e_{5}=\{b,d\},e_{6}=\{a,c\}}$.
والبيان الفائق ${\displaystyle G}$ والمعرف بمجموعة أضلاعه ${\displaystyle G=\{f_{1},f_{2},f_{3},f_{4},f_{5},f_{6}\}}$ حيث

${\displaystyle f_{1}=\{\alpha ,\beta \},f_{2}=\{\beta ,\gamma \},f_{3}=\{\gamma ,\delta \},f_{4}=\{\delta ,\alpha \},f_{5}=\{\alpha ,\gamma \},f_{6}=\{\beta ,\gamma \}}$.

بالتالي فإن الرسمين الفائقين ${\displaystyle H}$ و ${\displaystyle G}$ متشاكلان حيث الدالة ${\displaystyle \phi }$ معرفه كالتالي:

${\displaystyle \phi (a)=\alpha ,\phi (b)=\beta ,\phi (c)=\gamma ,\phi (d)=\delta }$.

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

لكن لايوجد رأس في ${\displaystyle G}$بحيث ينتمي للأضلاع ${\displaystyle 1,3,6}$ لأن ${\displaystyle f_{1}\cap f_{4}\cap f_{6}=\emptyset }$.

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

الرسوم الفائقة المتماثله

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

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

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

القواطع (Transversals)

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

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

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

لتكن ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}}$ مجموعة الرؤوس و ${\displaystyle E=\{e_{1},e_{2},\ldots ,e_{m}\}}$ مجموعة الآضلاع الفائقة. كل بيان فائق له مصفوفة وقوع ${\displaystyle A=(a_{ij})}$ من النوع ${\displaystyle n\times m}$ حيث:

${\displaystyle a_{ij}=\left\{{\begin{matrix}1&\mathrm {if} ~v_{i}\in e_{j}\\0&\mathrm {otherwise} .\end{matrix}}\right.}$

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

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

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

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

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

التجزئات (Partitions)

نظريات

تمثيل البيان الفائق

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

Hypergraph grammars

تعميمات

تدريس البيان الفائق

المزيد

مراجع

1. Haussler، David؛ Welzl، Emo (1987)، "ε-nets and simplex range queries"، Discrete and Computational Geometry، ج. 2، ص. 127–151، DOI:10.1007/BF02187876، MR:0884223
2. Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25.
3. Claude Berge, Graphs and Hypergraphs
4. C. Beeri, R. Fagin, D. Maier, M. Yannakakis, On the Desirability of Acyclic Database Schemes
5. R. E. Tarjan, M. Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. on Computing, 13(3):566-579, 1984.

ملاحظات