نظرية المخططات الطبولوجية
في الرياضيات، نظرية المخططات الطبولوجية (topological graph theory)، هو أحد فروع نظرية المخططات. تُعنى نظرية المخططات الطبولوجية بدراسة تضمين المخططات في السطوح، التضمين البياني للمخططات، والمخططات باعتبارها فضاء طبولوجي.[1] كما يدرس انغماس المخططات.
تضمين مخطط في سطح ما يعني أننا نريد رسم المخطط على سطح، كرة على سبيل المثال، دون تقاطع اثنين من الحواف. مشكلة التضمين الأساسية التي غالباً ما طُرحت كأحجية رياضي هي مسألة الخدمات الثلاثة. يمكن العثور على تطبيقات أخرى في طباعة الدوائر الإلكترونية حيث يكون الهدف هو طباعة (تضمين) دائرة (مخطط) على لوحة الدائرة (السطح) دون تقاطع وصلتين مع بعضهما البعض مما يؤدي إلى دائرة القصر.
المخططات كفضاءات طبولوجية
إلى مخطط غير موجه قد نربط المجمع البسيط المجرد C بمجموعة مكونة من عنصر واحد لكل رأس ومجموعة مكونة من عنصرين لكل حافة. الإدراك الهندسي |C| يتكون المجمع من نسخة من فترة الوحدة [0,1] لكل حافة، مع نقاط نهاية هذه الفترات ملتصقة معاً عند الرؤوس. في هذا الرأي، يعد تضمين المخططات في سطح ما أو تقسيمات فرعية من المخططات الأخرى مثالاً على التضمين الطبولوجي، التماثل الشكلي للمخططات هو مجرد تخصص في التماثل الشكلي الطبولجي، وفكرة المخطط المتصل تتزامن مع التتواصل الطبولوجي، والمخحطط المتصل هو شجرة إذا وفقط إذا مجموعتها الأساسية عديمة الأهمية.
تشمل المجمعات البسيطة الأخرى المرتبطة بالمخططات مجمع ويتني أو مجمع الزمرة، مع مجموعة لكل زمرة من المخطط، ومجمع المطابقة، مع مجموعة لكل مطابقة من المخطط (أي ما يعادل مجمع الزمرة لمكمل المخطط الخطي). يُطلق على المجمع المطابق للمخطط الثنائي الكامل اسم مجمع رقعة الشطرنج، حيث يمكن وصفه أيضاً بأنه مجمع مجموعات من الغربان غير المهاجمة على رقعة الشطرنج.[2]
دراسات نموذجية
ابتكر جون هوپكروفت وروبرت تارجان[3] طريق لاختبار استواء المخطط في زمن يتناسب خطياً مع عدد الحواف. وتقوم خوارزميتهم بذلك من خلال تضمين مخطط أطلقوا عليه اسم "شجرة النخيل". ويُعد اختبار الاستواء الفعال أساسياً لرسم المخطط.
درس فان تشونگ وزملائه[4] مشكلة تضمين مخطط في كتاب بحيث تكون رؤوس المخطط في خط على امتداد ظهر الكتاب. تُرسم حواف المخطط على صفحات منفصلة بحيث لا تتقاطع الحواف الموجودة في نفس الصفحة. تلخص هذه المشكلة مشكلات التخطيط الناشئة في توجيه لوحات الدوائر المطبوعة متعددة الطبقات.
كما يُستخدم تضمين المخطط في إثبات النتائج الهيكلية حول المخططات، عبر نظرية المخطط الثانوي ومبرهنة بنية المخطط.
انظر أيضاً
الهوامش
- ^ Gross, J.L.; Tucker, T.W. (2012) [1987]. Topological Graph Theory. Dover. ISBN 978-0-486-41741-7.
- ^ Shareshian, John; Wachs, Michelle L. (2007) [2004]. "Torsion in the matching complex and chessboard complex". Advances in Mathematics. 212 (2): 525–570. arXiv:math.CO/0409054. CiteSeerX 10.1.1.499.1516. doi:10.1016/j.aim.2006.10.014.
- ^ Hopcroft, John; Tarjan, Robert E. (1974). "Efficient planarity testing" (PDF). Journal of the ACM. 21 (4): 549–568. doi:10.1145/321850.321852. hdl:1813/6011. S2CID 6279825.
- ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. (1987). "Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design" (PDF). SIAM Journal on Algebraic and Discrete Methods. 8 (1): 33–58. doi:10.1137/0608002.