شجرة زائدية (نظرية الرسومات)

شجرة زائدية برؤوس زرقاء و أضلاع زائدية ملونه بالأصفر) وشجرة المضيف (أحمر)

في الرياضيات، يُسمى الرسم الزائدي $H$ شجرة زائدية (hypertree ) إذا أمكن إيجاد رسم بياني مضيف $T$ تمثل شجرة . بمعنى آخر، $H$هو شجرة زائدية إذا كان هناك شجرة T بحيث كل hyperedge من H هو مجموعة من رؤوس الشجرة الفرعية المتصلة T. يطلق على الأشجار الزائدية أيضًا مسمى رسوم زائديه شجريه( arboreal hypergraphs \tree hypergraphs).

كل شجرة $T$ هي أيضا شجرة زائدية ويكن أيضا استخدامها كرسم بياني مضيف، وكل ضلع في T يشكل شجرة فرعية من هذا الرسم البياني المضيف. لذلك، يمكن اعتبار الشجرة الزائدية في الرسوم الزائدية كتعميم لمفهوم شجرة في الرسم البياني . هذا التعريف للرسم الزائدي يشمل الرسوم الزائدية المتصلة بدون دورات بيرغ ( Berge-acyclic)، والتي تم استخدامها أيضًا كتعميم (ربما مختلف) للأشجار للرسومات الزائدية.

الخصائص

كل شجرة زائدية لها خاصية Helly (2-Helly property ) والتي تنص على أنه إذا كانت S مجموعة جزئية من الأضلاع الزائدية بحيث أن كل تقاطع أي ضلعين زائديين فيها هي مجموعة غير خالية فإن المجموعة فإن S نفسها بها تقاطع غير خالي (يوجد رأس ينتمي إلى كل ضلع زائدي في S ).

من خلال نتائج Duchet و Flament و Slater يمكن تعريف أي شجرة زائدية بشكل مكافئ بأحد الخصائص التالية:

• نقول أن الرسم الزائدي $H$ هو شجرة زائدية إذا وفقط إذا كان لديه خاصية Helly والرسم البياني الخطي هو رسم بياني وتري .
• الرسم الزائدي $H$ يكون شجرة زائدية إذا وفقط إذا كان لها الرسم الزائدي المزدوج له $H^{*}$هو متواز (conformal ) و الرسم البياني بقسمين للرسم الزائدي المزدود $H^{*}$ هو وتري (chordal) .
• يكون الرسم الزائدي شجرة زائدية إذا وفقط إذا كانت الرسم الزائدي المزدوج له لايحتوي على دورة ألفا ( alpha-acyclic) تبعا لتعريف الباحث Fagin.

من الممكن التعرف على الرسم الزائدي (كمزدوج لرسم زائدي بدون دورة ألفا ) في زمن خطي . مسألة الغطاء الدقيق (وهي العثور على مجموعة من الأضلاع الزائدية غير المتقاطعة التي تغطي جميع الرؤوس) قابلة للحل في وقت متعدد الحدود للأشجار الزائدية لكنها تظل مسألة كثيرة حدود غير قطعية كاملة للرسومات الزائدية بدون دورة ألفا.

انظر أيضا

• رسم بياني وتري مزدوج وهو رسم بياني الذي به أكبر عصبة به يمثل شجرة زائدية.

المراجع

• Berge، Claude (1989)، Hypergraphs: Combinatorics of Finite Sets، North-Holland Mathematical Library، Amsterdam: North Holland، ج. 45، ISBN:0-444-87489-5، MR:1013569.
• Brandstädt، Andreas؛ Dragan، Feodor؛ Chepoi، Victor؛ Voloshin، Vitaly (1998)، "Dually chordal graphs" (PDF)، SIAM Journal on Discrete Mathematics، ج. 11، ص. 437–455، DOI:10.1137/s0895480193253415، MR:1628114، مؤرشف من الأصل (PDF) في 2023-01-26.
• Brandstädt، Andreas؛ Le، Van Bang؛ Spinrad، Jeremy (1999)، Graph Classes: A Survey، SIAM Monographs on Discrete Mathematics and Applications، ISBN:0-89871-432-X، MR:1686154.
• Brandstädt، Andreas؛ Leitert، Arne؛ Rautenbach، Dieter (2012)، "Efficient dominating and edge dominating sets for graphs and hypergraphs"، Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012, Proceedings، Lecture Notes in Computer Science، ج. 7676، ص. 267–277، arXiv:1207.0953، DOI:10.1007/978-3-642-35261-4_30، MR:3065639.
• Fagin، Ronald (1983)، "Degrees of acyclicity for hypergraphs and relational database schemes"، Journal of the ACM، ج. 30، ص. 514–550، DOI:10.1145/2402.322390، MR:0709831.
• McKee، T.A.؛ McMorris، F.R. (1999)، Topics in Intersection Graph Theory، SIAM Monographs on Discrete Mathematics and Applications، Philadelphia, PA: Society for Industrial and Applied Mathematics، ISBN:0-89871-430-3، MR:1672910.
• Tarjan، Robert E.؛ Yannakakis، Mihalis (1984)، "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs"، SIAM Journal on Computing، ج. 13، ص. 566–579، DOI:10.1137/0213035، MR:0749707.
• Voloshin، Vitaly (2002)، Coloring Mixed Hypergraphs: Theory, Algorithms and Applications، Fields Institute Monographs، Providence, RI: American Mathematical Society، ج. 17، ISBN:0-8218-2812-6، MR:1912135.