نظرية المخططات الهندسية

نظرية المخططات الهندسية (Geometric graph theory)، بالمعنى الأوسع هو مجال فرعي كبير وغير متبلور من نظرية المخططات، يُعنى بالمخططات المحددة بواسطة وسائل هندسية. بمعنى أكثر تحديداً، تدرس نظرية المخططات الهندسية الخصائص التوافقية والهندسية للمخططات الهندسية، مما يعني المخططات المرسومة في المستوى الإقليدي مع احتمال تقاطع الحواف على الخطوط المستقيمة، والمخططات الطبولوجية، حيث يُسمح للحواف بأن تكون منحنيات مستمرة عشوائية تربط الرؤوس؛ وبالتالي يمكن وصفها بأنها "نظرية المخططات الهندسية والطوبولوجية". تُعرف المخططات الهندسية أيضاً بالشبكات المكانية.

 الأنواع المختلفة للمخططات الهندسية

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

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

المخطط الإقليدي (Euclidean graph) هو مخطط تمثل فيه الرؤوس نقاطاً في المستوى، ويُعين طول لكل حافة يساوي المسافة الإقليدية بين نقاط النهاية. الشجرة الممتدة الإقليدية الدنيا هي الشجرة الممتدة الدنيا في للمخطط الكامل الإقليدي. من الممكن أيضاً تحديد المخططات حسب شروط المسافات؛ على وجه الخصوص، يُشكل المخطط لمسافة الوحدة عن طريق ربط أزواج من النقاط التي تفصل بينها مسافة وحدة في المستوى. تتعلق مشكلة هادويگر-نلسون بالعدد اللوني لهذه المخططات.

مخطط التقاطع (intersection graph) هو مخطط يرتبط فيه كل رأس بمجموعة وتكون فيه الرؤوس متصلة بحواف عندما يكون للمجموعات المقابلة تقاطع غير فارغ. عندما تكون المجموعات أدوات هندسية، فإن النتيجة هي مخطط هندسي. على سبيل المثال، مخطط تقاطع المقاطع الخطية في بعد واحد هو مخطط فاصل؛ مخطط تقاطع أقراص الوحدة في المستوى هو مخطط قرص الوحدة. تنص مبرهنة تعبئة الدائرة على أن مخططات تقاطع الدوائر غير المتقاطعة هي بالضبط مخططات مستوية. مبرهنة شاينرمان (أثبتت عام 2009) تنص على أنه يمكن تمثيل كل مخطط مستوي على أنه مخطط لتقاطع المقاطع الخطية في المستوى.

يحتوي مخطط لـِڤي (Levi graph) لمجموعة من النقاط والخطوط على رأس لكل من هذه الأدوات وحافة لكل زوج من الخطوط النقطية الواردة. تؤدي مخططات لـِڤي للتكوينات الإسقاطية إلى العديد من المخططات المتماثلة والأقفاص.

يربط مخطط الرؤية (visibility graph) للمضلع المغلق كل زوج من الرؤوس بحافة عندما يقع الجزء الخطي الذي يربط الرؤوس بالكامل في المضلع. ليس من المعروف كيفية اختبار ما إذا كان من الممكن تمثيل المخطط غير الموجه كمخطط رؤية بكفاءة.

المكعب الجزئي (partial cube) هو مخطط يمكن ربط رؤوسه برؤوس المكعب الفائق، بحيث تساوي المسافة في المخطط مسافة هامينگ بين رؤوس المكعب الزائد المقابلة. يمكن تمثيل العديد من العائلات الهامة من الهياكل التوافقية، مثل التوجهات غير الحلقية للمخطط أو التقارب بين المناطق في ترتيب المستوى الزائد، على هيئة مخططات مكعبة جزئية. إحدى الحالات الخاصة المهمة للمكعب الجزئي هي المخططات الهيكلية لتبادلي السطوح، وهو مخطط تمثل فيه الرؤوس التباديل لمجموعة من الأدوات المرتبة وتمثل الحواف مبادلات للأشياء المتجاورة بالترتيب. العديد من الفئات الهامة الأخرى من المخططات بما في ذلك المخططات المتوسطة لها تعريفات ذات صلة تتضمن تضمينات مترية(Bandelt & Chepoi 2008).

المخطط الانعكاسي أو التبادلي (flip graph) هو مخطط يتكون من تثليثات مجموعة نقطية، حيث يمثل كل رأس تثليثاً ويتصل المثلثان بحافة إذا اختلفا باستبدال حافة بأخرى. من الممكن أيضاً تحديد المخططات ذات الصلة للأقسام إلى أشكال رباعية أو مثلثات زائفة، وللمثلثات ذات الأبعاد الأعلى. يشكل المخطط الوجهي لتثليثات المضلع المحدب المخططات الهيكلية لمتعدد السطوح المحدب أو كثير الجوانب ستاشف. يمكن أيضاً تمثيل المخطط الانعكاسي للتثليثات المنتظمة لمجموعة النقاط (إسقاطات لأجسام محدبة ذات أبعاد أعلى) كمخطط هيكلي، لما يسمى بكثير الجوانب الثانوي.

 انظر أيضاً

• نظرية المخططات الطبولوجية
• مخطط كيميائي
• شبكة مكانية

 المصادر

• Bandelt, Hans-Jürgen; Chepoi, Victor (2008). "Metric graph theory and geometry: a survey" (PDF). Surveys on Discrete and Computational Geometry - Twenty Years Later. Contemporary Mathematics. Vol. 453. American Mathematical Society. pp. 49–86.
• Pach, János, ed. (2004). Towards a Theory of Geometric Graphs. Contemporary Mathematics. Vol. 342. American Mathematical Society.
• Pach, János (2013). "The beginnings of geometric graph theory". Erdös centennial. Bolyai Soc. Math. Stud. Vol. 25. Budapest: János Bolyai Math. Soc. pp. 465–484. doi:10.1007/978-3-642-39286-3_17. MR 3203608.
• (2000) "Bridges between geometry and graph theory". Gorini, C. A.: 174–194, Washington, DC: Mathematical Association of America. 

 وصلات خارجية

• Media related to نظرية المخططات الهندسية at Wikimedia Commons