نظرية المخططات

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
رسم لمخطط بستة رؤوس مرتبطة بدون اتجاهات

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

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

تاريخ[عدل]

مسألة جسور كونيغسبرغ السبعة.

يعد البحث الذي كتبه ليونهارد أويلر ونشره في عام 1736 حول موضوع جسور كونيغسبرغ السبعة أول بحث في التاريخ في نظرية المخططات[1]. هذا البحث بالإضافة إلى المقالة التي كتبها فانديرموند عن مسألة الفارس، بالإضافة إلى العمل الذي قام به غوتفريد لايبنتز في وضع علاقات لعدد الرؤوس بالأضلاع وأوجه متعددات السطوح المحدبة تعتبر بدايات لعلم الطوبولوجيا.

تعاريف[عدل]

هناك نوعان من المخططات: مخطط موجه ومخطط غير موجه، وفي الحالتين معا, المخطط هو زوج لمجموعتين (S,A)حيث S مجموعة غير فارغة تمثل قمم المخطط :

  1. إذا كان المخطط موجه فإن A جزء من الجداء الديكارتي: S \times S
    المجموعة A تسمى مجموعة أقواس المخطط
  2. إذا كان المخطط غير موجه فإن A هي مجموعة جزء من مجموعة زوج S.

A تسمى مجموعة حروف المخطط.

تعاريف إضافية[عدل]

الارتباط والجوار[عدل]

إذا كانت قمتين من مخطط مرتبطتان بحرف, نقول أنهما متجاورتان أو مرتبطتان.

مربع مخطط[عدل]

مربع مخطط هو مخطط له نفس قمم المخطط الأول وله نفس الحروف أو الأقواس بالإضافة إلى وجود حروف أو أقواس تربط بين القمم التي لها جوارات مشتركة.

سلاسل وسبل[عدل]

السلسلة أو السبيل هو جزء من مخطط يربط بين قمتين بواسطة أزواج قمم مرتبط مثنى مثنى على التوالي.

الدرجة[عدل]

في المخطط العادي درجة قمة هو عدد الحروف المرتبطة بالقمة.

في المخطط الموجه هناك نوعان درجة الدخول وهي عدد الأقواس المتجهة من قمم أخرى إلى القمة, في حين درجة الخروج هي عدد الأقواس المنطلقة من القمة.

البئر[عدل]

البئر هو قمة في مخطط موجه درجة خروجه منعدم.

المنبع[عدل]

المنبع هو قمة في مخطط موجه درجة دخوله منعدم.

مخطط مكمل[عدل]

المخطط المكمل لمخطط هو مخطط له نفس القمم مرتبطة إذا لم تكن مرتبطة في المخطط الأصلي.

مسار ومسار مغلق[عدل]

المسار هو سلسلة رؤوس مرتبطة, لها بداية ونهاية (نقطة انطلاق ونقطة وصول).

إذا كانت نقطتي الانطلاق والوصول منطبقتين, المسار يكون مغلقا.

مسار أولير[عدل]

مسار أولير لمخطط G غير موجه هو مسار يمر بكل الحروف مرة واحدة فقط.

نقول أن المخطط متصل إذا كان يحتوي على مسار أولير, وكل رؤوسه من درجة مزدوجة

مسار هاميلتون[عدل]

مسار هاميلتون لمخطط G هو مسار يمر بكل القمم مرة واحدة فقط.

مخطط كامل[عدل]

المخطط الكامل هو مخطط بسيط يكون كل زوج من رؤوسه متصلان بضلع. بحيث أن المخطط الكامل ذو n رأس يكون له n(n-1)/2 ضلع.

مخطط مستقر[عدل]

المخطط المستقر هو مخطط ليس له حروف.

مخطّط مستوي[عدل]

المخطط المستوي هو مخطط يمكن تمثيله بكيفية لا تتقاطع الحروف فيه.

مخطط قوي التوصيل[عدل]

مخطط يمكن الوصول فيه من أي عقدة إلى أي عقدة أخرى.

تمثيلات[عدل]

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

مسائل[عدل]

  1. مشكلة الرحالة التاجر
  2. مشكلة تلوين المخطط
  3. تساوي شكلي مخططين

انظر أيضا[عدل]

مراجع[عدل]

  1. ^ Biggs, N.; Lloyd, E. and Wilson, R. (1986). Graph Theory, 1736-1936. Oxford University Press.