بيان فوقي
المحتويات
على سبيل التعريف، في الرياضيات، البيان الفائق هو تعميم لمفهوم البيان والذي كل ضلع فيه يحتوي على عدد من الرؤوس. بصيغة رياضية، البيان الفائق هو الزوج المرتب حيث هي مجموعة من العناصر التي تسمى رؤوس، والمجموعة هي مجموعة غير خاليه جزئيه من . عناصر المجموعة تسمى وصلات فائقة أو أضلاع. بالتالي هي مجموعة غير خاليه من مجموعة القوه . حجم مجموعة الرؤوس يسمى رتبة البيان الفائق بينما حجم مجموعة الاضلاع يسمى حجم البيان الفائق. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
تعاريف
إضافةً إلى ذلك، في حين أن أضلاع البيان البياني يحتوي على عنصرين فقط من مجموعة الرؤوس، الأضلاع الفائقة هي مجموعات مختارة من الرؤوس، ومن الممكن أن تحتوي على أي عدد من الرؤوس. لكن الغالب يرغب بدراسة الرسوم الفائقة التي كل أضلاعها تحتوي على نفس العدد من الرؤوس. البيان الفائق ذو أضلاع موحدة السعة (k-uniform hypergraph) هو البيان الفائق الذي كل ضلع فائق به من الرؤوس، أو بمعنى آخر هو البيان الفائق الذي أضلاعه الفائقة هي مجموعات بها من الرؤوس. فبالتالي، البيان الفائق ذو اضلاع سعتها 2 هو البيان البياني المعروف، والبيان الفائق ذو الاضلاع الموحدة بسعة 3 هو مجموعة من المجموعات الثلاثية، أي بها 3 عناصر. البيان الفائق يسمى كذلك بنظام المجموعة أو عائلة من المجموعات والمستوحاة من مجموعة شاملة.
مصطلحات
وفي هذا الصدد، يوجد أنواع خاصة من الرسومات الفائقة والمصنفه حسب سعة الأضلاع الفائقة بها. فمثلا البيان الفائق من السعة كما وضح أعلاه. وبيان فائق اخر يسمى clutters والذي به كل ضلع فائق ليس محتوى بأي ضلع فائق آخر بنفس البيان الفائق. بالمقابل، الرسومات الفائقة التي تحتوي على كل المجموعات الجزئية من أي ضلع فائق بها تسمى بـ abstract simplicial complexes.
وفي السياق ذاته، الرسومات الفائقة يمكن اعتبارها كهياكل الوقوع (incidence structures). وبصورة خاصة، يوجد بيان وقوع ثنائي التجزئة (incidence graph" or Levi graph ) مقابل كل بيان فائق . بالمقابل، ليس كل الرسومات البيانية الثنائية التجزئة يمكن اعتبارها كرسومات وقوع لرسومات فائقة.
وفي هذا السياق، البيانات الفائقة لها مسميات عديدة. ففي الهندسة الحاسوبية يسمى البيان الفائق في بعض الاحيان بـ range space وبالتالي أضلاعه الفائقة تسمى ranges. تسمى الرسوم الفائقة في نظرية اللعب التعاوني بالألعاب البسيطة وينطبق نفس المسمى لحل المشاكل في نظرية الإختيار الإجتماعي. تسمى الأضلاع الفائقة في بعض الدراسات بالروابط الفائقة (hyperlinks) أو موصلات (connectors).
الرسوم الفائقة المتماثله
علاوةً على ذلك، درجة الرآس ويرمز له بالرمز هي عدد الاضلاع التي تحتوي على هذا الرآس. يسمى البيان الفائق بمنتظم من الدرجة (regular-) إذا كان درجة كل رآس فيه تساوي .
ومن جهة أخرى، في تلوين البيان الفائق التقليدي٫ يتم تعيين لون واحد من ألوان المجموعة لكل رأس بالبيان الفائق بحيث أن أي ضلع فائق يحتوي على الأقل رأسين بألوان مختلفه. بمعنى آخر، لايمكن الحصول على ضلع بلون واحد فقط وبه على الأقل رأسين. هذا التعريف هو تعميم مباشر لتلوين الرسومات. يسمى أصغر عدد من الألوان المختلفه والممكن استخدامها بتلوين بيان فائق يسمى بـ chromatic number للبيان الفائق .
كذلك، يوجد الكثير من التعاريف والتي تعمم مسألة تلوين الرسوم الفائقة. أحد هذه التعاريف التي تسمى بمسألة تلوين مختلط للبيان الفائق (mixed hypergraph coloring) والتي تسمح بوجود أضلاع موحدة اللون. يوجد رسوم فائقة غير قابله للتلوين لأي عدد من الألوان. بمسألة التلوين المختلط وعندما يكون البيان الفائق قابل للتلوين فإن أصغر وأكبر عدد مستعمل من الألوان تُعتبر على التوالي حد سفلي وعلوي لـ chromatic number .
إضافةً إلى ذلك، البيان الفائق المزدوج لبيان فائق موحد السعه هو منتظم والعكس صحيح.
وعلى صعيد آخر، لتكن مجموعة الرؤوس و مجموعة الآضلاع الفائقة. كل بيان فائق له مصفوفة وقوع من النوع حيث:
يمثل منقول مصفوفة الوقوع البيان الفائق المزدوج لـ .
وفي هذا السياق، يوجد تطبيقات لحساب البيان الفائق القاطع في امثلة التراكيب وفي نظرية الألعاب وفي عدة فروع من علوم الحاسب مثلًا في التعلم الألي وفهرسة قواعد البيانات وتنقيب البيانات وأمثلية البرمجيات وsatisfiability problem.
ومن جهة أخرى، يٍُعرف قاطع بيان فائق بالمجموعة التي تتقاطع مع كل ضلع في بمجموعه غير خالية من الرؤوس. يطلق على بآنه القاطع الآصغر إذا كان لايوجد أي مجموعه جزئيه فعليه من وتمثل قاطع. البيان الفائق القاطع (transversal hypergraph) للبيان الفائق هو بيان فائق والذي مجموعة آضلاعه تحتوي على كل القواطع الصغرى لـ .
- التجزئات (Partitions)
- نظريات
- تمثيل البيان الفائق
- Hypergraph grammars
- تعميمات
- تدريس البيان الفائق
- المزيد
إضافةً إلى ذلك، الرسومات الفائقة التي يوجد بها عالأكثر من الألوان تُلقب بـ k-colorable. الرسومات الفائقة ثنائي التلوين (2-colorable) هي رسوم فائقة ثنائية التجزئة.
مصفوفة الوقوع (Incidence matrix)
وفي السياق ذاته، رتبة (rank) بيان فائق ويرمز له بالرمز هو أكبر سعة لآي من اضلاع البيان الفائق. يسمى البيان الفائق الذي كل ضلع فيه يحتوي على نفس العدد من الرؤوس مساوي للعدد بالبيان الفائق الموحد السعه ٫ ويسمى كذلك hypergraph-. بالتالي فإن الرسم هو عباره عن بيان فائق من السعه .
القواطع (Transversals)
مسألة تلوين الرسوم الفائقة (Hypergraph coloring)
نمذجة البيان ثنائي التجزئة
من جهة ثانية، عرف العالم بيرج (Claude Berge) آول تعريف للرسومات الفائقة بدون دورات: يكون البيان الفائق هو بيان خالي من الدورات إذا كان بيان الوقوع المقابل له لايحتوي على أي دورة. هذا التعريف يعتبر محدود جداً٫ فمثلًا إذا كان البيان الفائق يحتوي على زوج من الرؤوس المختلفة وزوج من الآضلاع الفائقة المختلفة بحيث آن و فإنه يمكن اختبار انه لايحتوي على دوره بزمن خطي بواسطة بيان الوقوع له.يوجد تعريف آخر المسمى ب α-acyclicity آضعف ومختلف من تعريف بيرج.
ومن ناحية أخرى، يوجد عدة مصطلحات غير متكافئة للرسومات الفائقة بدون دورات ٫ بعكس البيان الغير موجه والذي به تعريف موحد للدورات وللرسومات بدون دورات.
وعلى صعيد آخر، يمكن بزمن خطي تحديد ما إذا كان أي بيان فائق هو α-acyclicity.
بدون دورة (Acyclicity)
وعلى صعيد آخر، يمكن تمثيل آي بيان فائق ببيان ثنائي التجزئة كما يلي: المجموعات و تمثل تجزئات لـ و هو ضلع في إذا وفقط إذا كان كل رأس ينتمي للضلع الفائق في . بالمقابل ليس كل بيان ثنائي تجزئة تمثل بيان فائق. يسمى هـذا البيان الثنائي ببيان الوقوع .
التشاكل والمساواة
وفي هذا الصدد، البيان الفائق هو تشاكل احادي للبيان الفائق ونكتب إذا كان يوجد تقابل وتبديله لـ بحيث آن . بالتالي تسمى دالة التقابل في هذه الحالة بتشاكل احادي للرسومات. لاحظ ان إذا وفقط إذا كان .
وفي السياق ذاته، تشاكل رسوم فائق هو داله من مجموعة رؤوس بيان فائق إلى مجموعة رؤوس بيان فائق آخر بحيث كل ضلع هو صوره لضلع بالبيان الفائق المقابل.
.والبيان الفائق والمعرف بمجموعة أضلاعه حيث
- .
- بالتالي فإن الرسمين الفائقين و متشاكلان حيث الدالة معرفه كالتالي:
- .
في هذا الإطار، هذين الرسمين متشاكلان لكن ليس تشاكل قوي (strongly isomorphic) لأنه يوجد رأس في ينتمي للأضلاع أي أن
لكن لايوجد رأس في بحيث ينتمي للأضلاع لأن .
وفي هذا الصدد، في هذا المثال الرسمين الفائقين و متكافئين ونكتب في هذه الحالة . كذلك رسومهم المزدوجه متشاكله٫ أي أن .
يوجد أنواع مختلفه من الرسوم الفائقة، منها
إضافةً إلى ذلك، توسعة (extension) البيان الفائق الثانوي هو بيان فائق حيث كل ضلع من هو محتوى جزئيا بالبيان الفائق الثانوي ومحتوى كليا في التوسعة . رياضيا:
ليكن بيان فائق مكون من الرؤوس ولديه مجموعة الأضلاع
البيان الفائق الخالي: والذي لايحتوي على أي ضلع فائق.
كذلك، لتكن مجموعة معطاه، يعرف section hypergraph بآنه بيان فائق جزئي معرف كالتالي:
من جهة ثانية، البيان الفائق الجزئي هو بيان فائق من مع حذف بعض الآضلاع الفائقة. بصيغه رياضية، ليكن مجموعة جزئية من مجموعة ترميز الآضلاع٫ البيان الفائق الجزئي المولد بالمجموعة هو بيان فائق .
إضافةً إلى ذلك، البيان الفائق المتعدد أو الغير بسيط: وهو البيان الفائق الذي ممكن ان يحتوي على عروة أو اضلاع مكرره وهو عباره عن ضلعين يحتويان على نفس مجموعة الرؤوس.
إضافةً إلى ذلك، البيان الفائق الثانوي (subhypergraphs) من البيان الفائق هو بيان فائق مأخوذ من مع حذف بعض الرؤوس. بصيغة رياضية، البيان الفائق الجزئي المولد بواسطة معرف كالآتي:
وفي هذا السياق، البيان الفائق البسيط وهو بيان فائق لايحتوي على عروات ولا أضلاع مكررة.
في هذا الإطار، البيان الفائق المنتظم ذو الدرجة (regular hypergraph-): هو بيان فائق الذي كل كل رأس به له نفس الدرجة .
كذلك، البيان الفائق المزدوج (dual hypergraph) للبيان الفائق هو بيان فائق مجموعة رؤوسه هي وآضلاعه معطى بالمجموعة حيث .
.
من جانب آخر، حيث و هما مجموعتي الترميز index sets للرؤوس والأضلاع على التوالي.
لاحظ آن البيان الفائق المزدوج لـ هو ٫ آي آن .
حيث و .
ومن جهة أخرى، يوجد عدة مصطلحات للمصطلح المقابل لـ البيان الجزئي في البيان الفائق لأن أضلاع البيان الفائق ممكن أن تحتوي على أي عدد من الرؤوس. من هذه المسميات يعرف بالبيان الفائق الثانوي (subhypergraphs) والبيان الفائق الجزئي (partial hypergraphs) و section hypergraphs وسيتم تعرف كل من هذه المصطلحات كما موضح أدناه.
أمثلة
ليكن لدينا البيان الفائق والذي مجموعة أضلاعه حيث
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟