بيان فوقي

يسار|إطار|مثال لبيان فائق مجموعة الرؤوس هنا هي <math>X=\{v_1,v_2,v_3,v_4,v_5,v_6,v_7 \}</math> ومجموعة الأضلاع هي <math>E=\{e_1,e_2,e_3,e_4 \}</math> حيث <math>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 \}</math>. هذا البيان الفائق من الرتبه 7 وسعته 4. بعض الأضلاع الفائقة هنا تحتوي على أكثر من رأسين. الأضلاع تم توضيحها بالألوان.
في الرياضيات، **البيان الفائق**  هو تعميم لمفهوم البيان والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، البيان الفائق H  هو الزوج المرتب H = (X,E) حيث X  هي مجموعة من العناصر التي تسمى **رؤوس**، والمجموعة E  هي مجموعة غير خاليه جزئيه من X. عناصر المجموعة E تسمى **وصلات فائقة** أو أضلاع. بالتالي E  هي مجموعة غير خاليه من مجموعة القوه \mathcal{P}(X) \setminus\{\emptyset\}. حجم مجموعة الرؤوس يسمى **رتبة** البيان الفائق بينما حجم مجموعة الاضلاع يسمى **حجم** البيان الفائق.

في حين أن أضلاع البيان البياني يحتوي على عنصرين فقط من مجموعة الرؤوس، الأضلاع الفائقة هي مجموعات مختارة من الرؤوس، ومن الممكن أن تحتوي على أي عدد من الرؤوس. لكن الغالب يرغب بدراسة الرسوم الفائقة التي كل أضلاعها تحتوي على نفس العدد من الرؤوس. **البيان الفائق ذو أضلاع موحدة السعة** 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.

## مصطلحات

### تعاريف

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

* **البيان الفائق الخالي:** والذي لايحتوي على أي ضلع فائق.
* **البيان الفائق المتعدد أو الغير بسيط:** وهو البيان الفائق الذي ممكن ان يحتوي على عروة أو اضلاع مكرره وهو عباره عن ضلعين يحتويان على نفس مجموعة الرؤوس.
* **البيان الفائق البسيط** وهو بيان فائق لايحتوي على عروات ولا أضلاع مكررة.
* **البيان الفائق المنتظم ذو الدرجة <math>d</math>** (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 \land e_i \subseteq X \land e_i \neq \emptyset \},

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

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

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

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

Ex(H_A)=(A \cup A',E') حيث A'= \bigcup_{e \in E}e  \setminus A و E' = \{e\in E| e\subseteq (A \cup A') \} .

البيان الفائق الجزئي هو بيان فائق من مع حذف بعض الآضلاع الفائقة. بصيغه رياضية، ليكن 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 \land 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 \neq v' وزوج من الآضلاع الفائقة المختلفة f\neq f' بحيث آن v,v' \in f و v,v' \in f' فإنه يمكن اختبار انه لايحتوي على دوره بزمن خطي بواسطة بيان الوقوع له.يوجد تعريف آخر المسمى ب **α-acyclicity** آضعف ومختلف من تعريف بيرج.

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

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

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

البيان الفائق H=(X,E) هو تشاكل احادي للبيان الفائق G=(Y,F) ونكتب H \simeq G إذا كان يوجد تقابل \phi : X \rightarrow Y وتبديله \pi  لـ I بحيث آن \phi (e_i)= f_{\pi (i)} . بالتالي تسمى دالة التقابل \phi في هذه الحالة بتشاكل احادي للرسومات. لاحظ ان 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 متشاكلان حيث الدالة \phi معرفه كالتالي:

\phi (a)=\alpha , \phi(b)= \beta, \phi (c)=\gamma , \phi (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 = \emptyset .

في هذا المثال الرسمين الفائقين 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,\ldots,v_n \} مجموعة الرؤوس و E=\{e_1,e_2,\ldots,e_m \} مجموعة الآضلاع الفائقة. كل بيان فائق له مصفوفة وقوع A=(a_{ij}) من النوع n \times m حيث:

: a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.

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

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

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

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

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

## التجزئات (Partitions)

## نظريات

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

[تصغير|يمكن تمثيل هذه [:en:Circuit diagram|الدوره الإلكترونيه ببيان فائق بأربع رؤوس والملونه باللون الأبيض بالشكل المعطى والمرتبطة بواسطة ثلاث أضلاع فائقة على شكل أشجار.|250x250بك]]

## Hypergraph grammars
تصغير

## تعميمات

:

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

## المزيد

*

## مراجع

تصنيف:نظرية البيان