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

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

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

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

فهرست 1 تعاريف 2 تعاريف إضافية 2.1 الإرتباط و الجوار 2.2 مربع مخطط 2.3 سلاسل و سبل 2.4 الدرجة 2.5 البئر 2.6 المنبع 2.7 مخطط عكسي 2.8 مسار و مسار مغلق 2.9 مسار أولير 2.10 مسار هاميلتون 2.11 مخطط كامل 2.12 مخطط مستقر 2.13 مخطط مستو 3 تمثيلات 4 مسائل

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

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

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

A تسمى مجموعة توصيلات المخطط.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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