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