نظرية الرسم البياني الطوبولوجية
في الرياضيات ، تُعدّ نظرية المخططات الطوبولوجية فرعًا من فروع نظرية المخططات . وهي تدرس تضمين المخططات في الأسطح ، والتضمينات المكانية للمخططات ، والمخططات كفضاءات طوبولوجية . [ 1 ] كما تدرس أيضًا غمر المخططات.
يعني تضمين رسم بياني في سطح ما رسم هذا الرسم على سطح، ككرة مثلاً، دون أن يتقاطع ضلعان منه . ومن مسائل التضمين الأساسية التي تُطرح غالباً كلغز رياضي مسألة المرافق الثلاث . ويمكن إيجاد تطبيقات أخرى في طباعة الدوائر الإلكترونية، حيث يهدف التضمين إلى طباعة (تضمين) دائرة (الرسم البياني) على لوحة دوائر (السطح) دون أن يتقاطع وصلان ويتسببا في حدوث دارة قصر .
الرسوم البيانية كفضاءات طوبولوجية
يمكننا ربط مُركّب تبسيطي مجرد C بالرسم البياني غير الموجه ، حيث يتكون كل رأس من مجموعة أحادية العنصر، وكل ضلع من مجموعتين. ويتكون التمثيل الهندسي | C | لهذا المُركّب من نسخة من الفترة [0,1] لكل ضلع، مع ربط نهايتي هاتين الفترتين عند الرؤوس. وبناءً على هذا، فإن تضمين الرسوم البيانية في سطح أو تقسيمها إلى رسوم بيانية أخرى يُعدّ مثالًا على التضمين الطوبولوجي، وتماثل الرسوم البيانية هو مجرد تخصيص للتماثل الطوبولوجي ، ومفهوم الرسم البياني المتصل يتطابق مع الاتصال الطوبولوجي ، ويكون الرسم البياني المتصل شجرة إذا وفقط إذا كانت مجموعته الأساسية تافهة.
تشمل المجمعات التبسيطية الأخرى المرتبطة بالرسوم البيانية مجمع ويتني أو مجمع الزمر ، حيث توجد مجموعة لكل زمرة في الرسم البياني، ومجمع المطابقة ، حيث توجد مجموعة لكل مطابقة في الرسم البياني (أو ما يعادله، مجمع الزمر لمكمل الرسم البياني الخطي ). يُطلق على مجمع المطابقة للرسم البياني الثنائي الكامل اسم مجمع رقعة الشطرنج ، حيث يمكن وصفه أيضًا بأنه مجمع مجموعات الرخ غير المهاجم على رقعة الشطرنج. [ 2 ]
دراسات نموذجية
ابتكر جون هوبكروفت وروبرت تارجان [ 3 ] طريقة لاختبار استواء الرسم البياني في زمن خطي يتناسب مع عدد الحواف. وتقوم خوارزميتهم بذلك عن طريق إنشاء تمثيل بياني أطلقوا عليه اسم "شجرة النخيل". ويُعدّ اختبار الاستواء الفعال أساسيًا لرسم الرسوم البيانية .
درس فان تشونغ وآخرون [ 4 ] مشكلة تضمين رسم بياني في كتاب، بحيث تقع رؤوس الرسم البياني على خط مستقيم على طول غلاف الكتاب. رُسمت حواف الرسم البياني على صفحات منفصلة بحيث لا تتقاطع الحواف الموجودة على الصفحة نفسها. تُجرّد هذه المشكلة مشاكل التخطيط التي تظهر في توجيه لوحات الدوائر المطبوعة متعددة الطبقات.
تُستخدم تضمينات الرسوم البيانية أيضًا لإثبات النتائج الهيكلية المتعلقة بالرسوم البيانية، من خلال نظرية الرسم البياني الجزئي ونظرية بنية الرسم البياني .
انظر أيضاً
ملحوظات
- ↑ غروس، جيه إل؛ تاكر، تي دبليو (2012) [1987]. نظرية الرسم البياني الطوبولوجية . دوفر. ISBN 978-0-486-41741-7.
- ↑ شارشيان، جون؛ واكس، ميشيل ل. (2007) [2004]. "الالتواء في مُركّب المطابقة ومُركّب رقعة الشطرنج" . التقدم في الرياضيات . 212 (2): 525-570 . arXiv : math.CO/0409054 . CiteSeerX 10.1.1.499.1516 . doi : 10.1016/j.aim.2006.10.014 .
- ↑ هوبكروفت، جون ؛ تارجان، روبرت إي. (1974). "اختبار التسطيح الفعال" (ملف PDF) . مجلة ACM . 21 (4): 549-568 . doi : 10.1145/321850.321852 . hdl : 1813/6011 . S2CID 6279825 .
- ↑ تشونغ، إف آر كيه ؛ لايتون، إف تي ؛ روزنبرغ، إيه إل (1987). "تضمين الرسوم البيانية في الكتب: مشكلة تخطيط مع تطبيقات في تصميم الدوائر المتكاملة واسعة النطاق" (ملف PDF) . مجلة SIAM للطرق الجبرية والمنفصلة . 8 (1): 33-58 . doi : 10.1137/0608002 .
- نظرية الرسم البياني الطوبولوجية