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