الرسم البياني المغطي

في فرع الرياضيات المعروف بنظرية المخططات ، يُقال عن المخطط C أنه مخطط تغطية للمخطط G إذا وُجدت دالة تغطية من مجموعة رؤوس C إلى مجموعة رؤوس G. دالة التغطية f هي دالة شاملة وتماثل موضعي : حيث تُسقط جوار الرأس v في C بشكل تقابلي على جوار الرأس v في C.${\displaystyle f(v)}$في جي .​

يُستخدم مصطلح الرفع غالبًا كمرادف للرسم البياني المغطي للرسم البياني المتصل .

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

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

ليكن G = ( V1 _, E1 ) و C = ( _V2 , _E2 ) _رسمين بيانيين، ولتكن f : V2 → V1 دالة شاملة . عندئذٍ، تكون f دالة تغطية من C إلى G إذا كان لكل v ∈ V2 _، يكون تقييد f على جوار v تقابلاً على جوار f ( v ) في G. بعبارة أخرى، _f تُسقط الحواف المتصلة بـ v _{تقابلاً} أحادياً على الحواف المتصلة بـ f ( v ) .

إذا وُجدت خريطة تغطية من C إلى G ، فإن C تُعتبر رسمًا بيانيًا للتغطية ، أو رفعًا ، لـ G. والرفع من الرتبة h هو رفع بحيث تتمتع خريطة التغطية f بالخاصية التالية: لكل رأس v من G ، فإن أليافه f ⁻¹ (v) تحتوي على h عنصرًا بالضبط .

في الشكل التالي، يمثل الرسم البياني C رسمًا بيانيًا يغطي الرسم البياني H.

تُشير الألوان إلى خريطة التغطية f من C إلى H. على سبيل المثال، يتم تحويل كلا الرأسين الأزرقين في C إلى الرأس الأزرق في H. الخريطة f هي خريطة شاملة: لكل رأس في H صورة عكسية في C. علاوة على ذلك، تُحوّل f بشكل تقابلي كل جوار لرأس v في C إلى جوار الرأس f ( v ) في H.

على سبيل المثال، لنفترض أن v هو أحد الرؤوس البنفسجية في C ؛ وله جاران في C ، وهما الرأس الأخضر u والرأس الأزرق t . وبالمثل، لنفترض أن v ′ هو الرأس البنفسجي في H ؛ وله جاران في H ، وهما الرأس الأخضر u ′ والرأس الأزرق t ′ . إن التطبيق f المقيد بالمجموعة { t , u , v } هو تقابل على المجموعة { t ′ , u ′ , v ′ }. يوضح الشكل التالي ذلك:

وبالمثل، يمكننا التحقق من أن جوار الرأس الأزرق في C يتم تعيينه بشكل فردي على جوار الرأس الأزرق في H :

في المثال أعلاه، لكل رأس من رؤوس H صورتان عكسيتان بالضبط في C. وبالتالي فإن C عبارة عن غطاء ثنائي أو غطاء مزدوج لـ H.

لأي رسم بياني G ، من الممكن إنشاء الغطاء المزدوج الثنائي لـ G ، وهو عبارة عن رسم بياني ثنائي وغطاء مزدوج لـ G. الغطاء المزدوج الثنائي لـ G هو حاصل الضرب الموتري للرسوم البيانية G × K ₂ .

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

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

يمكن إنشاء الرسم البياني الشامل T للرسم البياني المتصل G على النحو التالي. اختر رأسًا عشوائيًا r من G كنقطة بداية. كل رأس من رؤوس T هو مسار غير متراجع يبدأ من r ، أي سلسلة w = ( r , v1 , _{v2 ,} ..., vn ) _من رؤوس G بحيث

• vᵢ و vᵢ _{+ 1} متجاورتان في G لجميع قيم _i ، أي أن w عبارة عن مسار
• v _{i -1} ≠ v _{i +1} لجميع قيم i ، أي أن w لا يتراجع.

عندئذٍ، يكون رأسان من رؤوس الشجرة _{T متجاورين إذا كان أحدهما امتدادًا بسيطًا للآخر: فالرأس (r, v1} , v2 , ... , vn ) مجاور للرأس ₍ r , _v1 , v2 , ... , _{vn -} 1 ) _{. وبشرط} التماثل ، تُنشأ الشجرة T نفسها بغض النظر عن اختيار نقطة البداية r .

تقوم خريطة التغطية f بربط الرأس ( r ) في T بالرأس r في G ، وربط الرأس ( r ، v1 _، v2 _، ...، vn ₎ في T بالرأس vn _في G.

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

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

إحدى الطرق الشائعة لتكوين الرسوم البيانية المغطاة هي استخدام الرسوم البيانية الجهدية ، حيث تُسمى سهام الرسم البياني المعطى G (أي أزواج الحواف الموجهة المقابلة للحواف غير الموجهة في G ) بأزواج معكوسة من عناصر مجموعة ما. يحتوي الرسم البياني المشتق من الرسم البياني الجهدي على الأزواج ( v , x ) كرؤوس، حيث v رأس في G و x عنصر من المجموعة؛ السهم من v إلى w المسمى بعنصر المجموعة y في G يقابل حافة من ( v , x ) إلى ( w , xy ) في الرسم البياني المشتق.

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

• جودسيل، كريس ؛ رويل، جوردون ف. (2001). "القسم 6.8 الطيات والأغطية" . نظرية الرسم البياني الجبرية . نصوص الدراسات العليا في الرياضيات. المجلد  207. سبرينغر. الصفحات 114-116 . ISBN  978-0-387-95220-8.
• أميت، ألون؛ لينال، ناثان ؛ ماتوشيك، جيري ؛ روزينمان، إيال (2001). "الرفع العشوائي للرسوم البيانية" . وقائع الندوة السنوية الثانية عشرة لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA '01) . جمعية الرياضيات الصناعية والتطبيقية. الصفحات 883-894 . CiteSeerX 10.1.1.719.3508 . ISBN   978-0-89871-490-6.
• أنجلوين، دانا (1980). "الخصائص المحلية والعالمية في شبكات المعالجات (ملخص موسع)". وقائع الندوة السنوية الثانية عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '80) . جمعية آلات الحوسبة. الصفحات 82-93 . doi : 10.1145/800141.804655 . ISBN  978-0-89791-017-0.