الرسم البياني المنقول

في الدراسة الرياضية والخوارزمية لنظرية المخططات ، يُعرف معكوس ^{[ 1 ]} أو منقول ^{[ 2 ]} أو عكس ^{[ 3 ]} المخطط الموجه G بأنه مخطط موجه آخر على نفس مجموعة الرؤوس، ولكن مع عكس جميع الحواف مقارنةً باتجاه الحواف المقابلة في G. أي، إذا احتوى G على الحافة ( u , v )، فإن معكوسه/منقوله/عكسه يحتوي على الحافة ( v , u ) ، والعكس صحيح.

يُطلق على هذه العملية اسم "العكس" لأن عكس اتجاه الأسهم يُقابل عكس الاستلزام في المنطق. أما اسم " المُبدَّل" فيُطلق عليه اسم "المُبدَّل " لأن مصفوفة التجاور للرسم البياني الموجه المُبدَّل هي مُبدَّل مصفوفة التجاور للرسم البياني الموجه الأصلي.

لا يوجد اتفاق عام على المصطلحات المفضلة.

يتم الإشارة إلى العكس بشكل رمزي على أنه G' أو G ^T أو G ^R أو رموز أخرى، اعتمادًا على المصطلحات المستخدمة والكتاب أو المقالة التي تمثل مصدر الرمز.

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

الرسم البياني المتماثل المائل هو رسم بياني متماثل مع الرسم البياني المنقول الخاص به، من خلال نوع خاص من التماثل الذي يقرن جميع الرؤوس.

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

• العلاقة العكسية – عكس ترتيب عناصر العلاقة الثنائية