عبد العزيز: بوت:صيانة المراجع

2023-01-29T02:08:43Z

بوت:صيانة المراجع

صفحة جديدة

{{يتيمة|تاريخ=أغسطس 2019}}
[[ملف:Hypergraph-wikipedia.svg|يسار|إطار|مثال لمخطط زائدي مجموعة الرؤوس هنا هي <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. بعض الأضلاع الزائدية هنا تحتوي على أكثر من رأسين. الأضلاع تم توضيحها بالألوان.]]
في [[رياضيات|الرياضيات]]، '''المخطط الزائدي''' أو '''الرسم الزائدي''' {{إنج|Hypergraph}} هو تعميم لمفهوم [[رسم بياني|الرسم البياني أو المخطط]] والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، الرسم الزائدي <math>H </math> هو الزوج المرتب <math>H = (X,E)</math> حيث <math>X </math> هي مجموعة من العناصر التي تسمى '''رؤوس'''، والمجموعة <math>E </math> هي مجموعة غير خاليه جزئيه من <math>X</math>. عناصر المجموعة <math>E</math> تسمى '''أضلاع زائديه''' أو أضلاع. بالتالي <math>E </math> هي مجموعة غير خاليه من مجموعة القوه <math>\mathcal{P}(X) \setminus\{\emptyset\}</math>. حجم مجموعة الرؤوس يسمى '''رتبة''' الرسم الزائدي بينما حجم مجموعة الاضلاع يسمى '''حجم''' الرسم الزائدي.

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

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

المخططات الزائدية لها مسميات عديدة. ففي [[هندسة رياضية حاسوبية|الهندسة الحاسوبية]] يسمى المخطط الزائدي في بعض الاحيان بـ '''range space''' وبالتالي أضلاعه الزائدية تسمى ''ranges''.<ref>{{استشهاد|الأخير1=Haussler|الأول1=David|مؤلف1-وصلة=David Haussler|الأخير2=Welzl|الأول2=Emo|مؤلف2-وصلة=Emo Welzl|doi=10.1007/BF02187876|العدد=2|صحيفة=[[Discrete and Computational Geometry]]|mr=884223|صفحات=127–151|عنوان=ε-nets and simplex range queries|المجلد=2|سنة=1987}}</ref> تسمى الرسوم الزائديه في [[لعبة تعاونية|نظرية اللعب التعاوني]] ب'''الألعاب البسيطة''' وينطبق نفس المسمى لحل المشاكل في [[نظرية الخيار الاجتماعي|نظرية الإختيار الإجتماعي]]. تسمى الأضلاع الزائدية في بعض الدراسات بالروابط الزائدية ('''hyperlinks''') أو موصلات ('''connectors''').<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

يوجد أنواع خاصة من الرسومات الزائدية والمصنفه حسب سعة الأضلاع الزائديه بها. فمثلا الرسم الزائدي من السعة <math>k </math> كما وضح أعلاه. ورسم زائدي اخر يسمى [[:en:Sperner family|clutters]] والذي به كل ضلع زائدي ليس محتوى بأي ضلع زائدي آخر بنفس الرسم الزائدي. بالمقابل، الرسومات الزائديه التي تحتوي على كل المجموعات الجزئية من أي ضلع زائدي بها تسمى بـ [[:en:Abstract simplicial complex|abstract simplicial complexes]].

== مصطلحات ==

=== تعاريف ===

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

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

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

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

<math>E=\{e_i: i \in I_e \land e_i \subseteq X \land e_i \neq \emptyset \},</math>

حيث <math>I_v</math> و <math>I_e</math> هما مجموعتي الترميز [[:en:Index set|index sets]] للرؤوس والأضلاع على التوالي.

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

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

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

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

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

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

<math>H \times A =(A,\{e_i| i \in I_e \land e_i \subseteq A \})</math>.

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

لاحظ آن الرسم الزائدي المزدوج لـ <math>H^*</math> هو <math>H</math> ٫ آي آن <math>(H^*)^* =H</math>.
== نمذجة المخطط ثنائي التجزئة ==
يمكن تمثيل آي رسم زائدي <math>H</math> برسم ثنائي التجزئة <math>BG</math> كما يلي: المجموعات <math>X</math> و <math>E</math> تمثل تجزئات لـ <math>BG</math> و <math>\{x_i , e_i \}</math> هو ضلع في <math>BG</math>[[إذا وفقط إذا]] كان كل رأس <math>x_i</math>ينتمي للضلع الزائدي <math>e_i</math> في <math>H</math> . بالمقابل ليس كل رسم ثنائي تجزئة تمثل رسم زائدي. يسمى هـذا الرسم الثنائي ب<nowiki/>[[:en:Levi graph|رسم الوقوع]] .

== بدون دورة (Acyclicity) ==

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

عرف العالم بيرج ([[:en:Claude Berge|Claude Berge]]) آول تعريف للرسومات الزائديه بدون دورات:<ref>Claude Berge, ''Graphs and Hypergraphs''</ref> يكون الرسم الزائدي هو رسم خالي من الدورات إذا كان رسم الوقوع المقابل له لايحتوي على أي دورة. هذا التعريف يعتبر محدود جداً٫ فعلى سبيل المثال إذا كان الرسم الزائدي يحتوي على زوج من الرؤوس المختلفة <math>v \neq v'</math> وزوج من الآضلاع الزائديه المختلفة <math>f\neq f'</math> بحيث آن <math>v,v' \in f</math> و <math>v,v' \in f'</math> فإنه يمكن اختبار انه لايحتوي على دوره بزمن خطي بواسطة رسم الوقوع له.يوجد تعريف آخر المسمى ب '''α-acyclicity''' آضعف ومختلف من تعريف بيرج.<ref>C. Beeri, R. Fagin, D. Maier, M. Yannakakis, ''On the Desirability of Acyclic Database Schemes''</ref>

يمكن بزمن خطي تحديد ماإذا كان أي رسم زائدي هو α-acyclicity.<ref>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.</ref>

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

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

الرسم الزائدي <math>H=(X,E)</math> هو [[:en:Isomorphism|تشاكل احادي]] للرسم الزائدي <math>G=(Y,F)</math> ونكتب <math>H \simeq G</math> إذا كان يوجد تقابل <math>\phi : X \rightarrow Y</math> وتبديله <math>\pi </math> لـ <math>I</math> بحيث آن <math>\phi (e_i)= f_{\pi (i)}</math> . بالتالي تسمى دالة التقابل <math>\phi</math> في هذه الحالة بتشاكل احادي للرسومات. لاحظ ان <math>H\simeq G</math> إذا وفقط إذا كان <math>H^* \simeq G^*</math>.

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

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

<math>f_1=\{ \alpha,\beta \}, f_2=\{ \beta, \gamma \}, f_3=\{\gamma, \delta \}, f_4=\{\delta, \alpha \}, f_5=\{\alpha, \gamma \}, f_6=\{\beta, \gamma \}</math>.

بالتالي فإن الرسمين الزائدين <math>H</math> و <math>G</math> متشاكلان حيث الدالة <math>\phi</math> معرفه كالتالي:

<math>\phi (a)=\alpha , \phi(b)= \beta, \phi (c)=\gamma , \phi (d)=\delta </math>.

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

لكن لايوجد رأس في <math>G</math>بحيث ينتمي للأضلاع <math>1,3,6</math> لأن <math>f_1 \cap f_4 \cap f_6 = \emptyset </math>.

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

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

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

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

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

== القواطع (Transversals) ==

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

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

== مصفوفة الوقوع (Incidence matrix) ==
لتكن <math>V=\{v_1,v_2,\ldots,v_n \}</math> مجموعة الرؤوس و <math>E=\{e_1,e_2,\ldots,e_m \}</math> مجموعة الآضلاع الزائديه. كل رسم زائدي له [[:en:Incidence matrix|مصفوفة وقوع]] <math>A=(a_{ij})</math> من النوع <math>n \times m</math> حيث:

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

<br />يمثل [[منقولة مصفوفة|منقول مصفوفة الوقوع]] <math>A^t</math> الرسم الزائدي المزدوج <math>H^* =(V^*, E^*)</math> لـ <math>H</math>.

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

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

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

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

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

== نظريات ==

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

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

== Hypergraph grammars ==
[[ملف:Venn's_four_ellipse_construction.svg|تصغير]]

== تعميمات ==

:

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

== المزيد ==

*

== مراجع ==
{{مراجع}}

== ملاحظات ==

*
{{شريط بوابات|رياضيات|الرياضيات المتقطعة=}}
{{روابط شقيقة|commons=Hypergraphs}}

{{ضبط استنادي}}

[[تصنيف:نظرية المخططات]]

رسم زائدي - تاريخ المراجعة

عبد العزيز: بوت:صيانة المراجع