شجرة SPQR

في نظرية المخططات ، وهي فرع من الرياضيات، تُمثل المكونات ثلاثية الاتصال للمخطط ثنائي الاتصال نظامًا من المخططات الأصغر التي تصف جميع القطوعات الثنائية الرؤوس في المخطط. شجرة SPQR هي بنية بيانات شجرية تُستخدم في علوم الحاسوب ، وتحديدًا في خوارزميات المخططات ، لتمثيل المكونات ثلاثية الاتصال للمخطط. يمكن إنشاء شجرة SPQR للمخطط في زمن خطي ^{[ 1 ]} ولها تطبيقات عديدة في خوارزميات المخططات الديناميكية ورسم المخططات .

تم التحقيق لأول مرة في الهياكل الأساسية التي تقوم عليها شجرة SPQR، والمكونات ثلاثية الاتصال للرسم البياني، والعلاقة بين هذا التفكيك والتضمينات المستوية للرسم البياني المستوي ، بواسطة سوندرز ماك لين ( 1937 ) ؛ وقد تم استخدام هذه الهياكل في خوارزميات فعالة من قبل العديد من الباحثين الآخرين ^{[ 2 ]} قبل صياغتها رسميًا كشجرة SPQR بواسطة دي باتيستا وتاماسيا ( 1989 ، 1990 ، 1996 ) .  

تتخذ شجرة SPQR شكل شجرة غير جذرية، حيث يرتبط بكل عقدة x رسم بياني غير موجه أو رسم بياني متعدد G _x . قد يكون للعقدة، والرسم البياني المرتبط بها، أحد الأنواع الأربعة، بالنظر إلى الأحرف الأولى SPQR:

• في عقدة S، يكون الرسم البياني المرتبط بها عبارة عن رسم بياني دوري بثلاثة رؤوس أو أكثر وحواف. هذه الحالة مماثلة لتركيب السلاسل في الرسوم البيانية المتسلسلة المتوازية ؛ حيث يرمز الحرف S إلى "سلسلة". ^{[ 3 ]}
• في عقدة P، يكون الرسم البياني المرتبط بها رسمًا بيانيًا ثنائي القطب ، وهو رسم بياني متعدد الرؤوس يتكون من رأسين وثلاثة حواف أو أكثر، وهو الرسم البياني الثنائي المستوي للرسم البياني الدوري. هذه الحالة مماثلة للتركيب المتوازي في الرسوم البيانية المتسلسلة المتوازية ؛ حيث يرمز الحرف P إلى "التوازي". ^{[ 3 ]}
• في عقدة Q، يحتوي الرسم البياني المرتبط بها على حافة حقيقية واحدة. هذه الحالة البسيطة ضرورية للتعامل مع الرسم البياني الذي يحتوي على حافة واحدة فقط. في بعض الدراسات حول أشجار SPQR، لا يظهر هذا النوع من العقد في أشجار SPQR للرسوم البيانية التي تحتوي على أكثر من حافة واحدة؛ بينما في دراسات أخرى، يُشترط تمثيل جميع الحواف غير الافتراضية بعقد Q ذات حافة حقيقية واحدة وحافة افتراضية واحدة، ويجب أن تكون جميع الحواف في أنواع العقد الأخرى افتراضية.
• في عقدة R، يكون الرسم البياني المرتبط بها رسمًا بيانيًا ثلاثي الاتصال، وليس دورة أو ثنائي قطب. يشير الحرف R إلى "صلب": في تطبيق أشجار SPQR في تضمين الرسم البياني المستوي، يكون للرسم البياني المرتبط بعقدة R تضمين مستوٍ فريد. ^{[ 3 ]}

يرتبط كل ضلع xy بين عقدتين في شجرة SPQR بضلعين افتراضيين موجهين ، أحدهما ضلع في G _x والآخر ضلع في G _y . ويمكن أن يكون كل ضلع في الرسم البياني G _x ضلعًا افتراضيًا لضلع واحد على الأكثر في شجرة SPQR.

تمثل شجرة SPQR، T ، رسمًا بيانيًا ثنائي الاتصال، G_{_T}، يتم تشكيله كما يلي: عندما يربط ضلع شجرة SPQR، xy ، الضلع الافتراضي ab من G_{_x} بالضلع الافتراضي cd من G_{_y} ، يتم تكوين رسم بياني أكبر واحد عن طريق دمج a و c في رأس فائق واحد، ودمج b و d في رأس فائق آخر، وحذف الضلعين الافتراضيين. أي أن الرسم البياني الأكبر هو مجموع الزمرتين لـ G_{_x} و G_{_y} . ينتج عن تنفيذ خطوة اللصق هذه على كل ضلع من أضلاع شجرة SPQR الرسم البياني G_{_T}؛ ولا يؤثر ترتيب تنفيذ خطوات اللصق على النتيجة. يمكن ربط كل رأس في أحد الرسمين البيانيين G_{_x} بهذه الطريقة برأس فريد في G_{_T}، وهو الرأس الفائق الذي تم دمجه فيه.

عادةً، لا يُسمح في شجرة SPQR بوجود عقدتين من النوع S متجاورتين، ولا بعقدتين من النوع P متجاورتين، لأنه في حال حدوث مثل هذا التجاور، يمكن دمج العقدتين في عقدة واحدة أكبر. وبناءً على هذا الافتراض، تُحدد شجرة SPQR بشكل فريد من خلال رسمها البياني. عندما يُمثل الرسم البياني G بشجرة SPQR بدون عقد P متجاورة أو عقد S متجاورة، فإن الرسوم البيانية G _x المرتبطة بعقد شجرة SPQR تُعرف باسم المكونات ثلاثية الاتصال لـ G.

يمكن إنشاء شجرة SPQR لرسم بياني متصل برأسين في وقت خطي . ^{[ 1 ]}

حُلّت مشكلة بناء المكونات ثلاثية الاتصال للرسم البياني لأول مرة في زمن خطي بواسطة هوبكروفت وتارجان (1973) . واستنادًا إلى هذه الخوارزمية، اقترح دي باتيستا وتاماسيا (1996) إمكانية بناء بنية شجرة SPQR الكاملة، وليس فقط قائمة المكونات، في زمن خطي. بعد توفير تطبيق لخوارزمية أبطأ لأشجار SPQR كجزء من مكتبة GDToolkit، قدّم جوتفينجر وموتزل (2001) أول تطبيق في زمن خطي. وكجزء من عملية تطبيق هذه الخوارزمية، صحّحا أيضًا بعض الأخطاء في العمل السابق لهوبكروفت وتارجان (1973) .

تتضمن خوارزمية Gutwenger & Mutzel (2001) الخطوات العامة التالية.

1. رتب حواف الرسم البياني حسب أزواج المؤشرات العددية لنهاياتها، باستخدام صيغة معدلة من فرز الجذر تُجري عمليتي فرز دلو ، واحدة لكل نهاية. بعد هذه الخطوة، ستكون الحواف المتوازية بين نفس الرأسين متجاورة في القائمة المرتبة، ويمكن فصلها إلى عقدة P في شجرة SPQR النهائية، مما يجعل الرسم البياني المتبقي بسيطًا.
2. قسّم الرسم البياني إلى مكونات منفصلة؛ وهي رسوم بيانية يمكن تكوينها بإيجاد زوج من الرؤوس الفاصلة، ثم تقسيم الرسم البياني عند هذين الرأسين إلى رسمين بيانيين أصغر (مع زوج من الحواف الافتراضية المتصلة التي تكون الرؤوس الفاصلة نهاياتها)، وتكرار عملية التقسيم هذه حتى لا يتبقى المزيد من أزواج الرؤوس الفاصلة. لا يُعدّ التقسيم الناتج بهذه الطريقة مُحددًا بشكل فريد، لأن أجزاء الرسم البياني التي ينبغي أن تُصبح عقدًا فرعية (S-nodes) لشجرة SPQR ستُقسّم إلى مثلثات متعددة.
3. صنّف كل مكون منقسم بـ P (مكون منقسم ذو رأسين وحواف متعددة)، أو S (مكون منقسم على شكل مثلث)، أو R (أي مكون منقسم آخر). إذا وُجد مكونان منقسمان يشتركان في زوج من الحواف الافتراضية، وكان كلا المكونين من النوع S أو من النوع P، فادمجهما في مكون واحد أكبر من النوع نفسه.

لإيجاد المكونات المنفصلة، ​​استخدم غوتفينغر وموتزل (2001) خوارزمية البحث العميق أولاً لإيجاد بنية أطلقوا عليها اسم "شجرة النخيل"؛ وهي شجرة بحث عميق أولاً، حيث تتجه حوافها بعيدًا عن جذر الشجرة بالنسبة للحواف التي تنتمي إلى الشجرة، ونحو الجذر بالنسبة لجميع الحواف الأخرى. ثم وجدوا ترقيمًا ترتيبيًا خاصًا للعقد في الشجرة، واستخدموا أنماطًا معينة في هذا الترقيم لتحديد أزواج الرؤوس التي يمكنها فصل الرسم البياني إلى مكونات أصغر. عند العثور على مكون بهذه الطريقة، تُستخدم بنية بيانات مكدس لتحديد الحواف التي يجب أن تكون جزءًا من المكون الجديد.

• شجرة القطع الكتلي ، وهي بنية شجرية مماثلة للمكونات المتصلة برأسين
• شجرة جوموري-هو ، وهي بنية شجرية مختلفة تميز اتصال الحواف في الرسم البياني
• تفكيك الشجرة ، تعميم (لم يعد فريدًا) للقطع الأكبر

• بينستوك، دانيال؛ مونما، كلايد ل. (1988)، "حول تعقيد تغطية الرؤوس بالوجوه في رسم بياني مستوٍ"، مجلة SIAM للحوسبة ، 17 (1): 53-76 ، CiteSeerX 10.1.1.542.2314 ، doi : 10.1137/0217004 .
• دي باتيستا، جوزيبي؛ تاماسيا، روبرتو (1989)، "اختبار التسطيح التدريجي"، وقائع الندوة السنوية الثلاثين حول أسس علوم الحاسوب ، الصفحات 436-441 ، doi : 10.1109/SFCS.1989.63515 ، ISBN  0-8186-1982-1.
• دي باتيستا، جوزيبي؛ تاماسيا، روبرتو (1990)، "خوارزميات الرسوم البيانية عبر الإنترنت باستخدام أشجار SPQR"، وقائع الندوة الدولية السابعة عشرة حول الأتمتة واللغات والبرمجة ، سلسلة محاضرات في علوم الحاسوب ، المجلد  443، سبرينغر-فيرلاغ، الصفحات 598-611 ، doi : 10.1007/BFb0032061 ، ISBN  978-3-540-52826-5.
• دي باتيستا، جوزيبي؛ تاماسيا، روبرتو (1996)، "اختبار التسطيح عبر الإنترنت" (ملف PDF) ، مجلة SIAM للحوسبة ، 25 (5): 956-997 ، doi : 10.1137/S0097539794280736.
• جوتفينجر، كارستن؛ موتزل، بيترا (2001)، "تنفيذ خطي لأشجار SPQR"، وقائع الندوة الدولية الثامنة حول رسم المخططات (GD 2000) ، سلسلة محاضرات في علوم الحاسوب، المجلد  1984، سبرينغر-فيرلاغ، الصفحات 77-90 ، doi : 10.1007/3-540-44541-2_8 ، ISBN  978-3-540-41554-1.
• هوبكروفت، جون ؛ تارجان، روبرت (1973)، "تقسيم الرسم البياني إلى مكونات ثلاثية الاتصال"، مجلة SIAM للحوسبة ، 2 (3): 135-158 ، doi : 10.1137/0202012 ، hdl : 1813/6037.
• ماك لين، سوندرز (1937)، "توصيف بنيوي للرسوم البيانية التوافقية المستوية"، مجلة ديوك الرياضية ، 3 (3): 460-472 ، doi : 10.1215/S0012-7094-37-00336-3.

• تنفيذ شجرة SPQR في إطار عمل الرسم البياني المفتوح.
• شجرة المكونات ثلاثية الاتصال، تطبيق جافا في مكتبة jBPT (انظر فئة TCTree).