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

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

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

محتويات 1 تاريخ 2 تعاريف 3 تعاريف إضافية 3.1 الارتباط و الجوار 3.2 مربع مخطط 3.3 سلاسل و سبل 3.4 الدرجة 3.5 البئر 3.6 المنبع 3.7 مخطط عكسي 3.8 مسار و مسار مغلق 3.9 مسار أولير 3.10 مسار هاميلتون 3.11 مخطط كامل 3.12 مخطط مستقر 3.13 مخطط مستو 3.14 مخطط قوي التوصيل 4 تمثيلات 5 مسائل 6 مراجع

[عدل] تاريخ

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

[عدل] تعاريف

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

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

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

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

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

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

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

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

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

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

[عدل] الدرجة

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

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

[عدل] البئر

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

[عدل] المنبع

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[عدل] مسائل

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

[عدل] مراجع

عرض • نقاش • تعديل الحقول الأساسية للمعلوماتية معلوماتية نظرية تحسيب  • خوارزميات  • نظرية المعلومات  • نظرية الأتمتة  • نظرية المخططات  • نظرية التعقيد  • تعمية  • لغات شكلية  • استمثال  • بناء المترجمات البرمجية  • نظرية أنظمة التشغيل  • نظرية قواعد البيانات  • نظرية التعمية  • طريقة شكلية  • تحسيب طبيعي معلوماتية عملية أنظمة تشغيل  • حوسبة  • رسوميات الحاسب  • قواعد بيانات  • بنى بيانات  • برمجة معلوماتية تقنية تكنولوجيا المعلومات  • شبكات الحاسب  • عتاد الحاسب  • أمن الحاسب  • اختراق الحاسب معلوماتية تطبيقية أنظمة معلومات  • معلوماتية حيوية  • معلوماتية جيولوجية  • كيمياء حاسوبية  • فيزياء حاسوبية  • معلوماتية اقتصادية  • وسائط متعددة ذكاء اصطناعي تعلم آلي  • معلوماتية عصبونية  • طرق التصنيف  • لغويات حاسوبية برمجيات لغات البرمجة  • برمجيات حرة  • برمجيات تجارية أنظمة التشغيل دوس  • ويندوز  • يونكس  • لينكس  • ماك أو إس  • نتوير  • تاريخ أنظمة تشغيل الحاسوب عتاد الحاسب وحدة المعالجة المركزية  • ذاكرة الحاسب  • القرص الصلب  • اللوحة الأم