هندسة

نظرية الرسوم البيانية

كتب الفيلسوف وعالم الرياضيات الشهير «جوتفريد دبليو لايبنيز-Gottfried W. Leibniz» رسالة بعثها إلى «كريستيان هويجنز-Christian Huygens» يقول فيها: “أنا لا أكتفي بالجبر، لأنه لا يقدم أقصى البراهين ولا أجمل التركيبات الهندسية. نحن بحاجة إلى نوع آخر من التحليل الهندسي أو الخطي يتعامل مباشرة مع الموضع، إذ يتعامل الجبر مع المقدار”.

كانت هندسة المواقع لـ لايبنيز -المعروفة اليوم باسم مجال الطوبولوجيا- بطيئة في التطور، ومن بعد ذلك أتى «ليونارد بول أويلر-Leonhard Paul Euler» بورقته البحثية التي مثلت نقطة البداية لنظرية الرسوم البيانية أو المخططات والطبولوجيا. كانت تلك الورقة تتحدث عن حل مشكلة جسور كونيجسبيرج الشهيرة وتُّعد تلك الورقة الأولى في تاريخ الرسوم البيانية.

لقد أنشأ أويلر الرسم البياني لمحاكاة مكان وحالة معينة وهي حل مشكلة كونيجسبيرج التي تُّعد واحدة من أصعب المشكلات. تطورت النظرية من ورقة أويلر وأصبحت نظرية قوية وعميقة ولها دور كبير في تطبيقات العلوم الفيزيائية والبيولوجية والاجتماعية. فنظرية الرسوم البيانية هي فرع من فروع الرياضيات تهتم بشبكات النقاط المتصلة بخطوط. وسنعرف معنى هذا التعريف بدقة في السطور التالية. لمعرفة مشكلة جسور كونيجسبيرج تفصيليًا؛ تابع ذلك المقال: مشكلة جسور كونيجسبرج.

محتويات المقال :

معنى الرسم البياني

الرسم البياني هو زوج من المجموعات (V ، E)، حيث V هي مجموعة الرؤوس. E هي مجموعة الحواف التي تربط أزواج الرؤوس.

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

وجب علينا معرفة أنه يوجد أنواع مختلفة من الرسوم البيانية في الرياضيات والأحصاء. لتمثيل البيانات في شكل تصويري وأكثر تلك الأنواع شيوعًا هي الرسوم البيانية:

الإحصائية.
الأسية.
اللوغاريتمية.
المثلثية.
الرسم البياني لتوزيع التردد.

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

رسوم بيانية أصعب من رسوم أويلر: الرسوم البيانية الهاميلتونية

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

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

النظرية والطوبولوجيا

أدى الارتباط بين نظرية الرسم البياني والطوبولوجيا إلى حقل فرعي وهو «نظرية الرسم البياني الطوبولوجي». هناك مشكلة مهمة في هذا المجال تتعلق بالرسوم البيانية المستوية. هذه هي الرسوم البيانية التي يمكن رسمها كمخططات نقطية وخطية على مستوى (أو على نحو مكافئ كـ كرة) بدون أي حواف متقاطعة باستثناء الرؤوس حيث تلتقي.

الرسوم البيانية الكاملة التي تحتوي على أربعة رؤوس أو أقل تكون مستوية، لكن الرسوم البيانية الكاملة ذات الخمسة رؤوس أو أكثر ليست كذلك. لا يمكن رسم الرسوم البيانية غير المستوية على مستوى أو على سطح كرة بدون حواف تتقاطع مع بعضها البعض بين الرؤوس.

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

بعض من تطبيقات النظرية

الكيمياء: نظرية الرسوم البيانية الكيميائي هي الفرع الطوبولوجي للكيمياء الرياضية الذي يُطبق النظرية على النمذجة الرياضية للظواهر الكيميائية.

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

علم الطب والأحياء: تستخدم نظرية الرسوم البيانية في الأدوية وتحديد دور البروتينات أو الجينات ذات الوظيفة غير المحددة.

الهندسة الكهربائية: تُستخدم مفاهيم نظرية الرسوم البيانية على نطاق واسع في تصميم توصيلات الدوائر يتم تسمية أنواع الاتصالات أو تنظيمها على أنها طبولوجيا.

علوم الكمبيوتر: تستخدم نظرية الرسوم البيانية لدراسة الخوارزميات، مثل:«خوارزمية كروسكال-Kruskal’s Algorithm».«خوارزمية بريم-Prim’s Algorithm».«خوارزمية ديكسترا-Dijkstra’s Algorithm».

النظرية واللغويات: تستخدم شجرة تحليل اللغة وقواعد اللغة الرسوم البيانية.

كذلك يمكن تمثيل الطرق بين المدن باستخدام الرسوم البيانية. بأمكاننا استخدام تصوير المعلومات المرتبة الهرمية مثل شجرة العائلة كنوع خاص من الرسم البياني.