نظرية المخططات
في الرياضيات وفهم الحاسوب، تقوم نظرية المخططات بدراسة خواص المخططات. وهي تعبير عن بنى رياضية تستخدم لنمذجة العلاقات الثنائية بين كائنات ضمن مجموعة معينة. حيث يمكن اعتبار المخطط مجموعة كائنات objects تدعى رؤوس vertices مفردها رأس vertex ، ترتبط ببعضها بأضلاع أوحواف edge أوتدعى أحيانا أقواس arcs يمكن ان تكون موجهة أي مزودة باتجاه أوبدون اتجاه . التمثيل لهذا المخططقد يكون على الورق بمجموعة نقاط تمثل الرؤوس متصلة بخطوط هي حواف المخطط .
تعد المخططات أحد المواضيع الهامة في الرياضيات المتبترة.
يمكن بالاستعانة بالمخططات حل الكثير من المشاكل العملية ، فمثلا بنية موسوعة ويكيبيديا يمكن تمثيلها بمخطط رؤوسه هي اسماء الموضوعات ونقوم برسم خط موجه بين منطقتين من أ إلى ب اذا كانت الموضوعة أ تحوي رابط إلى الموضوعة ب . تطبيقات هذه النظرية واسعة جدا ولحل مشاكلها يستخدم الحاسوب بشكل واسع لذلك تهتم علوم الحاسوب بتصميم خوارزميات لنظرية المخططات .
تاريخ
انظر جسور كونيغسبرغ السبعة.
تعاريف
هناك نوعان من المخططات: مخطط موجه ومخطط غير موجه, وفي الحالين معا المخطط هوزوج لمجموعتين (S,A)حيث S مجموعة غير فارغة تمثل قمم المخطط :
- إذا كان المخطط موجه فإن A جزء من الجداء الديكارتي:
المجموعة A تسمى مجموعة أقواس المخطط - إذا كان المخطط غير موجه فإن A هي مجموعة جزء من مجموعة زوج S.
A تسمى مجموعة توصيلات المخطط.
تعاريف إضافية
الإرتباط والجوار
إذا كانت قمتين من مخطط مرتبطتان, نقول أنهما متجاورتان أومرتبطتان.
مربع مخطط
مربع مخطط هومخطط له نفس قمم المخطط الأول وله نفس التوصيلات أوالأقواس بالإضافة إلى وجود توصيلات أوأقواس تربط بين القمم التي لها جوارات مشهجرة.
سلاسل وسبل
السلسلة أوالسبيل هوجزء من مخطط يربط بين قمتين بواسطة أزواج قمم مرتبط مثنى مثنى على التوالي.
الدرجة
في المخطط العادي درجة قمة هوعدد التوصيلات المرتبطة بالقمة.
في المخطط الموجه هناك نوعان درجة الدخول وهي عدد الأقواس المتجهة من قمم أخرى إلى القمة, في حين درجة الخروج هي عدد الأقواس المنطلقة من القمة.
البئر
البئر هوقمة في مخطط موجه درجة خروجه منعدم.
المنبع
المنبع هوقمة في مخطط موجه درجة دخوله منعدم.
مخطط عكسي
المخطط العكسي لمخطط هومخطط له نفس القمم مرتبطة إذا لم تكن مرتبطة في المخطط الأصلي.
مسار ومسار مغلق
المسار هوسلسلة رؤوس مرتبطة, لها بداية ونهاية (نقطة انطلاق ونقطة وصول).
إذا كانت نقطتي الانطلاق والوصول منطبقتين, المسارقد يكون مغلقا.
مسار أولير
مسار أولير لمخطط G غير موجه هومسار يمر بكل الإرتباطات مرة واحدة فقط.
نقول حتى المخطط متصل إذا كان يحتوي على مسار أولير, وجميع رؤوسه من درجة مزدوجة
مسار هاميلتون
مسار هاميلتون لمخطط G هومسار يمر بكل القمم مرة واحدة فقط.
مخطط كامل
المخطط الكامل هومخطط جميع رؤوسه متصلة.
مخطط مستقر
المخطط المستقر هومخطط ليس له روابط.
مخطط مستو
المخطط المستوي هومخطط يمكن تمثيله بكيفية لا تتقاطع الروابط فيه.
تمثيلات
كل مخطط يضم مجموعة قمم يمكن تمثيلها على شكل دوائر، إذا كان المخطط موجه يتم تمتيل جميع قوس بسهم، وبخط في حالة مخطط عادي.
مسائل
- مشكلة الرحالة التاجر
- مشكلة تلوين المخطط
