الجسر (نظرية الرسم البياني)

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

ينبغي التمييز بين هذا النوع من الجسور وبين المعنى غير ذي الصلة لكلمة "جسر" في نظرية الرسم البياني، وهو رسم بياني فرعي منفصل عن بقية الرسم البياني بواسطة مجموعة فرعية محددة من الرؤوس؛ انظر الجسر في مسرد نظرية الرسم البياني .

رسم بياني مع${\displaystyle n}$يمكن أن تحتوي العقد على أكثر من${\displaystyle n-1}$الجسور، لأن إضافة حواف إضافية يجب أن تُنشئ دورة. الرسوم البيانية التي تحتوي بالضبط على${\displaystyle n-1}$الجسور هي بالضبط الأشجار ، والرسوم البيانية التي يكون فيها كل ضلع جسراً هي بالضبط الغابات .

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

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

في الرسم البياني المكعب ، كل رأس مقطوع هو نقطة نهاية لجسر واحد على الأقل.

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

من المسائل المفتوحة المهمة المتعلقة بالجسور، حدسية التغطية المزدوجة للدورة ، التي وضعها سيمور وسيكيريس (1978 و 1979 ، بشكل مستقل)، والتي تنص على أن كل رسم بياني بدون جسور يقبل مجموعة متعددة من الدورات البسيطة التي تحتوي على كل حافة مرتين بالضبط. ^{[ 4 ]}

وصف روبرت تارجان في عام 1974 أول خوارزمية زمنية خطية (خطية بالنسبة لعدد الحواف) لإيجاد الجسور في الرسم البياني. ^{[ 5 ]} وهي تقوم بالخطوات التالية:

• ابحث عن غابة ممتدة من${\displaystyle G}$
• أنشئ غابة متجذرة${\displaystyle F}$من الغابة الممتدة
• اجتياز الغابة${\displaystyle F}$في الترتيب المسبق ، قم بترقيم العقد. الآن، تحمل العقد الأبوية في الغابة أرقامًا أقل من أرقام العقد الفرعية.
• لكل عقدة${\displaystyle v}$في الترتيب المسبق (مع الإشارة إلى كل عقدة باستخدام رقم الترتيب المسبق الخاص بها)، قم بما يلي:
  • احسب عدد أحفاد الغابة${\displaystyle ND(v)}$بالنسبة لهذه العقدة، يتم ذلك بإضافة واحد إلى مجموع أحفاد أبنائها.
  • الحوسبة${\displaystyle L(v)}$، وهو أدنى سعر متاح للطلب المسبق من${\displaystyle v}$عن طريق مسار تبقى فيه جميع الحواف باستثناء الحافة الأخيرة داخل الشجرة الفرعية التي جذرها عند${\displaystyle v}$هذا هو الحد الأدنى للمجموعة التي تتكون من تسمية الترتيب المسبق لـ${\displaystyle v}$، من قيم${\displaystyle L(w)}$في العقد الفرعية لـ${\displaystyle v}$وعلامات الترتيب المسبق للعقد التي يمكن الوصول إليها من${\displaystyle v}$بواسطة حواف لا تنتمي إلى${\displaystyle F}$.
  • وبالمثل، احسب${\displaystyle H(v)}$، أعلى تصنيف ترتيب مسبق يمكن الوصول إليه بواسطة مسار تبقى فيه جميع الحواف باستثناء الحافة الأخيرة داخل الشجرة الفرعية المتجذرة في${\displaystyle v}$هذا هو الحد الأقصى للمجموعة التي تتكون من تسمية الترتيب المسبق لـ${\displaystyle v}$، من قيم${\displaystyle H(w)}$في العقد الفرعية لـ${\displaystyle v}$وعلامات الترتيب المسبق للعقد التي يمكن الوصول إليها من${\displaystyle v}$بواسطة حواف لا تنتمي إلى${\displaystyle F}$.
  • لكل عقدة${\displaystyle w}$مع العقدة الأصلية${\displaystyle v}$، لو${\displaystyle L(w)=w}$و${\displaystyle H(w)<w+ND(w)}$ثم الحافة من${\displaystyle v}$ل${\displaystyle w}$هو جسر.

تستخدم خوارزمية بسيطة للغاية لإيجاد الجسور ^{[ 6 ]} تفكيكات السلسلة . لا تسمح تفكيكات السلسلة بحساب جميع جسور الرسم البياني فحسب، بل تسمح أيضًا بقراءة كل رأس قطع في G ( وشجرة القطع الكتلية لـ G )، مما يوفر إطارًا عامًا لاختبار اتصال حافتين ورأسين (والذي يمتد إلى اختبارات اتصال ثلاث حواف وثلاثة رؤوس في وقت خطي).

تُعدّ تفكيكات السلاسل نوعًا خاصًا من تفكيكات السلاسل، وتعتمد على شجرة البحث العمقي أولًا T للرسم البياني G ، ويمكن حسابها ببساطة شديدة: لنفترض أن كل رأس مُعلّم بأنه غير مُزار. لكل رأس v في أرقام DFS التصاعدية من 1 إلى n ، يتم اجتياز كل حافة خلفية (أي كل حافة ليست في شجرة DFS) متصلة بـ v، واتباع مسار حواف الشجرة عائدًا إلى جذر T ، والتوقف عند أول رأس مُعلّم بأنه مُزار. خلال هذا الاجتياز، يُعلّم كل رأس تم اجتيازه بأنه مُزار. وبالتالي، يتوقف الاجتياز عند v كحد أقصى ، ويُشكّل إما مسارًا موجهًا أو دورة، بدءًا من v؛ ونُسمّي هذا المسار أو الدورة سلسلة . تُسمى السلسلة رقم i التي تم العثور عليها بهذه العملية C _{_i} . C = C _₁ , C _₂ , ... هي تفكيك سلسلة للرسم البياني G.

تسمح الخصائص التالية باستخلاص العديد من خصائص G من C بكفاءة ، بما في ذلك جميع جسور G. ^{[ 6 ]} ليكن C تفكيكًا متسلسلًا لرسم بياني متصل بسيط G=(V,E) .

1. تكون G متصلة من حافتين إذا وفقط إذا كانت السلاسل في C تقسم E.
2. الحافة e في G هي جسر إذا وفقط إذا لم تكن e موجودة في أي سلسلة في C.
3. إذا كانت G متصلة بحواف ثنائية، فإن C عبارة عن تحليل أذني .
4. تكون G متصلة برأسين إذا وفقط إذا كانت G ذات درجة دنيا 2 و C ₁ هي الدورة الوحيدة في C.
5. يكون الرأس v في الرسم البياني G المتصل بالحواف 2 رأسًا قاطعًا إذا وفقط إذا كان v هو الرأس الأول لدورة في C - C ₁ .
6. إذا كانت G متصلة برأسين، فإن C عبارة عن تحليل للأذن المفتوحة .

يُعرَّف الرسم البياني الأويلري بأنه رسم بياني يحتوي على دورة أويلرية. كل رسم بياني أويلري خالٍ من الجسور، وذلك لأن كل حافة فيه جزء من دورة أويلرية. وبالتالي، إذا حُذفت الحافة، فإن طرفيها يظلان متصلين عبر بقية الدورة. أما العكس فليس صحيحًا.

يُعرَّف الرسم البياني شبه الأويلري بأنه رسم بياني يمكن تحويله إلى رسم بياني أويلري بإضافة حافة واحدة (أو بعبارة أخرى، رسم بياني يحتوي على مسار أويلري). كل رسم بياني شبه أويلري يكون شبه خالي من الجسور، ولكن العكس غير صحيح.

تتقاطع فئتا الرسوم البيانية عديمة الجسور والرسوم البيانية شبه الأويلرية تقاطعًا غير فارغ (فالرسوم البيانية الأويلرية هي رسوم بيانية عديمة الجسور وشبه أويلرية)، لكنهما لا تحتويان بعضهما بعضًا. ^{[ 7 ] : الملحق ب}

• مكون ثنائي الاتصال
• القطع (نظرية الرسم البياني)