الاختزال المتعدي

الاختزال المتعدي للرسم البياني الموجه المحدود G هو رسم بياني بأقل عدد ممكن من الحواف، وله نفس علاقة الوصول للرسم البياني الأصلي. أي، إذا كان هناك مسار من الرأس x إلى الرأس y في الرسم البياني G ، فلا بد من وجود مسار من x إلى y في الاختزال المتعدي لـ G ، والعكس صحيح. تحديدًا، إذا كان هناك مسار من x إلى y، وآخر من y إلى z، فقد لا توجد حافة مباشرة من x إلى z في الاختزال المتعدي. تعني خاصية التعدي لـ x و y و z أنه إذا كان x < y و y < z، فإن x < z. إذا كان هناك مسار من x إلى y لأي مسار من y إلى z، فإنه يوجد مسار من x إلى z. مع ذلك، ليس صحيحًا أنه لكل مسارين x إلى y و x إلى z يوجد مسار y إلى z، وبالتالي تُستبعد أي حافة بين الرأسين x و z في عملية الاختزال المتعدي، لأنها تمثل مسارات غير متعدية. تُظهر الصورة التالية رسومات بيانية تُقابل علاقة ثنائية غير متعدية (على اليسار) واختزالها المتعدي (على اليمين).

يُعدّ الاختزال المتعدي للرسم البياني الموجه غير الدوري المحدود G فريدًا، ويتألف من حواف G التي تُشكّل المسار الوحيد بين طرفيها. وبالتحديد، هو دائمًا رسم بياني جزئي شامل للرسم البياني المُعطى. لهذا السبب، يتطابق الاختزال المتعدي مع الرسم البياني المكافئ الأدنى في هذه الحالة.

في النظرية الرياضية للعلاقات الثنائية ، يمكن اعتبار أي علاقة R على مجموعة X بمثابة رسم بياني موجه ، حيث تمثل المجموعة X مجموعة رؤوسه، ويحتوي على قوس xy لكل زوج مرتب من العناصر المرتبطة في R. وبالتحديد، تتيح هذه الطريقة إعادة تفسير المجموعات المرتبة جزئيًا كرسوم بيانية موجهة غير دورية، حيث يوجد قوس xy في الرسم البياني كلما وُجدت علاقة ترتيب x < y بين زوج معين من عناصر الترتيب الجزئي. عند تطبيق عملية الاختزال المتعدي على رسم بياني موجه غير دوري تم إنشاؤه بهذه الطريقة، فإنه يُولّد علاقة التغطية للترتيب الجزئي، والتي غالبًا ما تُعبّر عنها بصريًا باستخدام مخطط هاس .  

تم استخدام الاختزال المتعدي على الشبكات التي يمكن تمثيلها كرسوم بيانية موجهة غير دورية (مثل رسوم بيانية للاستشهاد أو شبكات الاستشهاد ) للكشف عن الاختلافات الهيكلية بين الشبكات. ^{[ 2 ]}

في رسم بياني محدود يحتوي على دورات، قد لا يكون الاختزال المتعدي فريدًا: فقد يوجد أكثر من رسم بياني على نفس مجموعة الرؤوس يحتوي على الحد الأدنى من الحواف وله نفس علاقة الوصول مع الرسم البياني المعطى. بالإضافة إلى ذلك، قد لا يكون أي من هذه الرسوم البيانية الدنيا رسمًا بيانيًا فرعيًا من الرسم البياني المعطى.

^{مع ذلك ،} من السهل تحديد الرسوم البيانية الدنيا التي لها نفس علاقة الوصول للرسم البياني المعطى G. [ ^{3 ]} إذا كان G رسمًا بيانيًا موجهًا عشوائيًا، وكان H رسمًا بيانيًا بأقل عدد ممكن من الحواف التي لها نفس علاقة الوصول لـ G ، فإن H يتكون من

• دورة موجهة لكل مكون متصل بقوة من G ، تربط الرؤوس في هذا المكون معًا
• يُعرَّف الاختزال المتعدي لتكثيف G بأنه ضلع xy لكل ضلع XY ، حيث X و Y مكونان متصلان بقوة في G ويربطهما ضلع في التكثيف، و x أي رأس في المكون X ، و y أي رأس في المكون Y. تكثيف G هو رسم بياني موجه غير دوري، يحتوي على رأس لكل مكون متصل بقوة في G وضلع لكل مكونين متصلين بضلع في G. وبالتحديد، ولأنه غير دوري، يمكن تعريف اختزاله المتعدي كما في القسم السابق.

ثم يكون العدد الإجمالي للحواف في هذا النوع من الاختزال المتعدي مساوياً لعدد الحواف في الاختزال المتعدي للتكثيف، بالإضافة إلى عدد الرؤوس في المكونات المتصلة بقوة غير التافهة (المكونات التي تحتوي على أكثر من رأس واحد).

يمكن دائمًا اختيار حواف الاختزال المتعدي التي تُقابل حواف التكثيف لتكون رسمًا بيانيًا فرعيًا من الرسم البياني المُعطى G. مع ذلك، لا يمكن اختيار الدورة داخل كل مُكوّن مُتصل بقوة لتكون رسمًا بيانيًا فرعيًا من G إلا إذا كان لهذا المُكوّن دورة هاميلتونية ، وهو أمر ليس صحيحًا دائمًا ويصعب التحقق منه. بسبب هذه الصعوبة، يُعدّ إيجاد أصغر رسم بياني فرعي من رسم بياني مُعطى G بنفس إمكانية الوصول (أصغر رسم بياني مُكافئ له) مسألة صعبة من نوع NP . ^{[ 3 ]}

يقدم أهو وزملاؤه المثال المضاد التالي لتوضيح أنه في الرسوم البيانية اللانهائية ، يصعب تعريف شرط الحد الأدنى الذي يوسع مفهوم الاختزال المتعدي من الرسوم البيانية المنتهية بشكل واضح. ويصعب ذلك حتى عندما يكون الرسم البياني غير دوري. وباختيار تعريف الحد الأدنى على أنه "لا توجد مجموعة جزئية فعلية تمثل اختزالًا متعديًا"، يقدمون المثال المضاد التالي.

قم بتكوين رسم بياني برأس لكل عدد حقيقي ، مع حافة${\displaystyle x\to y}$حينما${\displaystyle x<y}$كأعداد حقيقية. عندئذٍ يكون هذا الرسم البياني لانهائيًا، وغير دوري، ومغلقًا بشكل متعدٍ. ومع ذلك، في أي رسم بياني فرعي له نفس الإغلاق المتعدي، كل حافة متبقية${\displaystyle x\to y}$يمكن إزالة ذلك دون تغيير الإغلاق المتعدي، لأنه لا يزال يجب أن يبقى مسار من${\displaystyle x}$ل${\displaystyle y}$من خلال أي رأس بينهما. لذلك، من بين الرسوم البيانية الفرعية التي لها نفس الإغلاق المتعدي، لا يوجد أي من هذه الرسوم البيانية الفرعية أصغر (بحسب تعريف المجموعة الفرعية الصحيح): لا يوجد اختزال متعدٍ. ^{[ 3 ]}

لإثبات أن الاختزال المتعدي سهلٌ كالإغلاق المتعدي، اعتمد أهو وزملاؤه على التكافؤ المعروف مسبقًا مع ضرب المصفوفات المنطقية. ليكن A مصفوفة التجاور للرسم البياني الموجه غير الدوري المعطى، و B مصفوفة التجاور لإغلاقه المتعدي (المحسوب باستخدام أي خوارزمية إغلاق متعدٍ قياسية). عندئذٍ، ينتمي الضلع uv إلى الاختزال المتعدي إذا وفقط إذا كان هناك عنصر غير صفري في الصف u والعمود v من المصفوفة A ، وكان هناك عنصر صفري في الموضع نفسه من حاصل ضرب المصفوفات AB . في هذا البناء، تمثل العناصر غير الصفرية في المصفوفة AB أزواجًا من الرؤوس المتصلة بمسارات طولها اثنان أو أكثر. ^{[ 3 ]}

لإثبات أن الاختزال المتعدي لا يقل صعوبة عن الإغلاق المتعدي، قام أهو وزملاؤه بإنشاء رسم بياني آخر H من رسم بياني موجه غير دوري G ، حيث استُبدل كل رأس في G بمسار مكون من ثلاثة رؤوس، وتقابل كل حافة في G حافة في H تربط الرؤوس الوسطى المقابلة لهذه المسارات. إضافةً إلى ذلك، أضاف أهو وزملاؤه في الرسم البياني H حافة من بداية كل مسار إلى نهايته. في الاختزال المتعدي لـ H ، توجد حافة من بداية المسار u إلى نهاية المسار v ، إذا وفقط إذا كانت الحافة uv لا تنتمي إلى الإغلاق المتعدي لـ G. بالتالي، إذا أمكن حساب الاختزال المتعدي لـ H بكفاءة، يمكن استنتاج الإغلاق المتعدي لـ G منه مباشرةً. ^{[ 3 ]}

عند قياس الاختزالات المتعدية في رسم بياني موجه غير دوري، سواءً من حيث عدد الرؤوس (n) أو عدد الحواف (m )، يمكن إيجادها في زمن O( nm )، وهو حد قد يكون أسرع من طرق ضرب المصفوفات للرسوم البيانية المتفرقة . وللقيام بذلك، يُطبَّق خوارزمية خطية لإيجاد أطول مسار في الرسم البياني الموجه غير الدوري المُعطى، لكل اختيار ممكن لرأس البداية. من أطول المسارات المحسوبة، تُحتفظ فقط بالمسارات ذات الطول واحد (حافة واحدة)؛ أي تُحتفظ بالحواف ( u , v ) التي لا يوجد لها مسار آخر من u إلى v . يتوافق حد الزمن O( nm ) مع تعقيد بناء الإغلاقات المتعدية باستخدام البحث العميق أولًا أو البحث العرضي أولًا لإيجاد الرؤوس التي يمكن الوصول إليها من كل اختيار لرأس البداية، وبالتالي، مع هذه الافتراضات، يمكن إيجاد الإغلاقات المتعدية والاختزالات المتعدية في نفس الوقت.

بالنسبة لرسم بياني يحتوي على n رأسًا و m حافة، و r حافة في الاختزال المتعدي، من الممكن إيجاد الاختزال المتعدي باستخدام خوارزمية حساسة للمخرجات في وقت يعتمد على r بدلاً من m . الخوارزمية هي: ^{[ 6 ]}

• لكل رأس v ، بترتيب عكسي للترتيب الطوبولوجي للرسم البياني المدخل:
  • قم بتهيئة مجموعة من الرؤوس التي يمكن الوصول إليها من v ، وهي في البداية مجموعة العناصر المفردة { v }.
  • لكل حافة vw ، مرتبة طوبولوجيًا حسب w ، اختبر ما إذا كانت w موجودة في المجموعة التي يمكن الوصول إليها من v ، وإذا لم تكن كذلك:
    • إخراج الحافة vw كجزء من الاختزال المتعدي.
    • استبدل مجموعة الرؤوس التي يمكن الوصول إليها من v باتحادها مع مجموعة الرؤوس التي يمكن الوصول إليها من w .

يمكن ترتيب الحواف في الحلقة الداخلية باستخدام خوارزمية فرز العد مرتين، أو خوارزمية فرز مستقرة أخرى ، لفرز الحواف أولاً حسب الترقيم الطوبولوجي لرأس النهاية، وثانياً حسب رأس البداية. إذا مُثّلت المجموعات كمصفوفات ثنائية ، فيمكن تنفيذ كل عملية اتحاد مجموعات في زمن O ( n )، أو أسرع باستخدام عمليات البت . يتناسب عدد عمليات المجموعات هذه مع عدد حواف الإخراج، مما يؤدي إلى حد زمني إجمالي قدره O ( nr ). تصف المجموعات التي يمكن الوصول إليها، والتي تم الحصول عليها أثناء الخوارزمية، الإغلاق المتعدي للمدخلات. ^{[ 6 ]}

إذا تم إعطاء الرسم البياني مع تقسيم رؤوسه إلى k سلاسل (مجموعات فرعية يمكن الوصول إليها بشكل ثنائي)، فيمكن تقليل هذا الوقت إلى O ( kr )، من خلال تمثيل كل مجموعة يمكن الوصول إليها بإيجاز كاتحاد لواحق السلاسل. ^{[ 7 ]}