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

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

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

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

الخصائص

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

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

• نقول أن الرسم الزائدي ${\displaystyle H}$ هو شجرة زائدية إذا وفقط إذا كان لديه خاصية Helly والرسم البياني الخطي هو رسم بياني وتري .

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

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

مقالات ذات صلة

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

ملاحظات

المراجع

• Berge, Claude (1989), Hypergraphs: Combinatorics of Finite Sets, 45, Amsterdam: North Holland,  , MR = 1013569 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 1628114 .
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications,  , MR = 1686154 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, 7676, صفحات 267–277, arXiv:, doi:10.1007/978-3-642-35261-4_30, MR = 3065639 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 0709831 .
• McKee, T.A.; McMorris, F.R. (1999), Topics in Intersection Graph Theory, Philadelphia, PA: Society for Industrial and Applied Mathematics,  , MR = 1672910 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 (3): 566–579, doi:10.1137/0213035, MR = 0749707 0749707 .
• Voloshin, Vitaly (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, 17, Providence, RI: American Mathematical Society,  , MR = 1912135 1912135 .

موسوعات ذات صلة :

• موسوعة رياضيات