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

من ويكيبيديا، الموسوعة الحرة

رسم لمخطط بستة رؤوس مرتبطة بدون اتجاهات

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

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

[تحرير] تعاريف

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

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

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

[تحرير] تعاريف إضافية

[تحرير] الارتباط و الجوار

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

[تحرير] مربع مخطط

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

[تحرير] سلاسل و سبل

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

[تحرير] الدرجة

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

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

[تحرير] البئر

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

[تحرير] المنبع

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

[تحرير] مخطط عكسي

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

[تحرير] مسار و مسار مغلق

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

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

[تحرير] مسار أولير

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

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

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

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

[تحرير] مخطط كامل

المخطط الكامل هو مخطط كل رؤوسه متصلة.

[تحرير] مخطط مستقر

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

[تحرير] مخطط مستو

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

[تحرير] مخطط قوي التوصيل

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

[تحرير] تمثيلات

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

[تحرير] مسائل