أثبت أنه في أي رسم بياني ، يكون عدد رؤوس الدرجة الفردية زوجيا

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

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

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

وهكذا ، في الرسم البياني مع ن الرؤوس و ك الحواف ، عدد رؤوس الدرجة الفردية هو ك. ولكن تم حساب كل حافة مرتين ، لذلك ، ك يجب أن يكون عددا زوجيا. وبالتالي ، فإن عدد رؤوس الدرجة الفردية في الرسم البياني سيكون دائما زوجيا.

1. الرسم البياني ، القمم ، الدرجة
2. نظرية الرسم البياني
3. الرسوم البيانية ، الاتصال ، مكونات الاتصال
4. نظرية أويلر
5. المسارات والدورات والحواف والرؤوس
6. طرق
7. دورات
8. الأضلاع
9. القمم
10. دليل على النظرية
11. الشروط الضرورية والكافية
12. سؤال وجواب
13. لماذا هو عدد القمم من درجة غريبة في الرسم البياني حتى?
14. هل هناك أي استثناءات عندما يكون عدد القمم من درجة غريبة في الرسم البياني يمكن أن يكون غريبا?
15. ما هي العلاقة بين التكافؤ في عدد من القمم والمساواة في درجة?

الرسم البياني ، القمم ، الدرجة

الرسم البياني هو تجريد رياضي يمثل مجموعة من الرؤوس المتصلة بالحواف. هناك مفهومان مهمان في الرسم البياني — القمم والدرجة.

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

تحدد درجة الرأس في الرسم البياني عدد الحواف المرتبطة برأس معين. يمكن أن تكون درجة الرأس إما زوجية أو فردية.

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

1. افترض أن هناك عددا فرديا من الرؤوس بدرجة فردية في الرسم البياني
2. ضع في اعتبارك رأسا تعسفيا في رسم بياني بدرجة فردية وقم ببناء مسار باستخدام الحواف المترافقة فقط مع الرؤوس بدرجة فردية.
3. سيحتوي هذا المسار دائما على عدد زوجي من الحواف ، حيث تبدأ كل حافة وتنتهي عند رؤوس بدرجة فردية.
4. لذلك ، سيضيف كل رأس من هذا القبيل عددا زوجيا من الحواف إلى هذا المسار.
5. نظرا لأن الافتراض الأولي هو أن هناك عددا فرديا من الرؤوس ذات الدرجة الفردية في الرسم البياني ، فإن عدد الرؤوس المضافة إلى المسار بواسطة عدد زوجي من الحواف سيكون أيضا زوجيا.
6. نستنتج أنه لا يمكن أن يكون هناك عدد فردي من الرؤوس بدرجة فردية في الرسم البياني.

وهكذا ، أثبتنا أنه في أي رسم بياني ، يكون عدد رؤوس الدرجة الفردية زوجيا.

نظرية الرسم البياني

نظرية الرسم البياني هي فرع من فروع الرياضيات المنفصلة التي تدرس خصائص الرسوم البيانية وتطبيقاتها في مختلف المجالات. الرسم البياني هو بنية رياضية تتكون من مجموعة من الرؤوس والحواف التي تربط هذه الرؤوس.

تجد نظرية الرسم البياني تطبيقات في مجالات مختلفة ، مثل:

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

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

في هذا السياق ، ينص البيان المعني على أنه في أي رسم بياني يكون عدد رؤوس الدرجة الفردية زوجيا. دعونا نثبت هذا البيان:

دليل:

افترض أن هناك ن رؤوس من الدرجة الفردية في رسم بياني معين. اسمحوا س دلالة على جميع القمم مع درجة غريبة. ضع في اعتبارك مجموع درجات جميع الرؤوس في الرسم البياني:

في هذا الرسم البياني ، كل رأس بدرجة فردية له حافة (2ن+1). نظرا لأن مجموع الدرجات بالكامل يجب أن يكون متساويا ، يجب أن يكون مجموع درجات الرؤوس ذات الدرجة الزوجية متساويا. في نفس الوقت ، إذا افترضنا ذلك م القمم لها درجة زوجية ، إذن:

2 م + (2 ن + 1) * ن = 2 م + 2 ن^2 + ن = 2 (م + ن^2 + ن / 2) + ن / 2 = 2 ك + ن/2,

أين ك هو عدد صحيح. وبالتالي ، يجب أن يكون مجموع درجات الرؤوس ذات الدرجة الزوجية متساويا أيضا.

وبالتالي ، إذا كان هناك عدد فردي من الرؤوس في الرسم البياني ، فيجب أن يكون عدد الرؤوس ذات الدرجة الفردية زوجيا. وقد ثبت هذا البيان.

الرسوم البيانية ، الاتصال ، مكونات الاتصال

الرسم البياني هو بنية رياضية تتكون من مجموعة من الرؤوس والحواف التي تربط هذه الرؤوس.

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

يمكن أن تتكون الرسوم البيانية من عدة مكونات اتصال. مكون الاتصال هو مجموعة فرعية من الرؤوس الأكبر حجما ، بحيث يوجد لكل زوج من الرؤوس من هذا المكون مسار يربطها.

النظر في الرسوم البيانية مع عدد زوجي وفردي من القمم من درجة غريبة. في مثل هذا الرسم البياني ، يتم توصيل كل رأس بدرجة فردية بعدد فردي من الرؤوس ، ويتم توصيل كل رأس بدرجة زوجية بعدد زوجي من الرؤوس. إذا كان مجموع الأرقام الفردية غريبا ، فهذا يتعارض مع مبدأ وجود المسار.

وبالتالي ، في أي رسم بياني ، يكون عدد رؤوس الدرجة الفردية زوجيا.

نظرية أويلر

تؤسس نظرية أويلر علاقة بين عدد الرؤوس والحواف ومكونات الاتصال في الرسم البياني. على وجه الخصوص ، تنص النظرية على ما يلي:

النظرية: في الرسم البياني الذي يحتوي على العديد من مكونات الاتصال ، يكون عدد رؤوس الدرجة الفردية زوجيا.

يعتمد إثبات هذه النظرية على الملاحظات التالية:

1. كل حافة من الرسم البياني لها نقطتا نهاية ، أي رأسان. لذلك ، تزيد كل حافة من درجة رأسين.
2. توجد القمم ذات الدرجة الزوجية فقط في الحالات التي تكون فيها بداية ونهاية بعض المسارات في الرسم البياني.

بناء على هذه الملاحظات ، من السهل التحقق من أن عدد رؤوس الدرجة الفردية يكون دائما زوجيا:

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

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

المسارات والدورات والحواف والرؤوس

المسارات والدورات والحواف والرؤوس هي المفاهيم الأساسية لنظرية الرسم البياني. دعونا ننظر إلى كل واحد منهم بمزيد من التفصيل:

المسارات

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

قد يكون هناك عدة مسارات في الرسم البياني بين رأسين. يسمى المسار دورة إذا تزامنت رؤوس البداية والنهاية.

دورات

الدورة في الرسم البياني هي مسار تتطابق فيه رؤوس البداية والنهاية ، لكن جميع الرؤوس الأخرى فريدة من نوعها.

يمكن أن تكون الدورات ذات أطوال مختلفة وتحتوي على أعداد مختلفة من الحواف.

الأضلاع

تربط الحواف في الرسم البياني الرؤوس وتحدد العلاقة بينهما. الرسم البياني المرجح هو رسم بياني يتم فيه تعيين رقم يسمى الوزن لكل حافة.

يمكن أن تكون الحواف اتجاهية وغير اتجاهية. في الرسم البياني الموجه ، تحتوي الحافة على قمة بداية ونهاية ، تحدد الاتجاه.

القمم

القمم هي عناصر الرسم البياني التي ترتبط بها حواف وشكل العلاقات. يمكن أن يكون للرؤوس خصائص مختلفة ويمكن الإشارة إليها بالأرقام أو الحروف أو الرموز.

يطلق على الرأس أحيانا عقدة الرسم البياني.

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

دليل على النظرية

1. لنفترض أن هناك رأسين من الدرجة الفردية في الرسم البياني.
2. دعونا ربط القمم أ و ب مع حافة.
3. نتيجة لإضافة حافة بين القمم أ و ب ، سينخفض عدد الرؤوس ذات الدرجة الفردية بمقدار 2.
4. لننفذ عملية إضافة حافة بين الرؤوس أ و ب حتى لا يتبقى رؤوس ذات درجة فردية في الرسم البياني.
5. لذلك ، في أي رسم بياني ، يكون عدد رؤوس الدرجة الفردية زوجيا.

الشروط الضرورية والكافية

لإثبات أنه في أي رسم بياني ، يكون عدد رؤوس الدرجة الفردية زوجيا ، فمن الضروري والكافي مراعاة الشروط التالية:

1. شرط ضروري:

   • لا توجد رؤوس معزولة في الرسم البياني ، أي رؤوس بدون حواف ، لأن هذه الرؤوس سيكون لها درجة 0 ، وهو رقم زوجي.

2. شرط ضروري وكاف:

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

وبالتالي ، فإن الشروط الضرورية والكافية لعدد الرؤوس ذات الدرجة الفردية في أي رسم بياني تكون زوجية هي عدم وجود رؤوس معزولة ومجموع درجات جميع الرؤوس ليكون رقما زوجيا.

سؤال وجواب

لماذا هو عدد القمم من درجة غريبة في الرسم البياني حتى?

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

هل هناك أي استثناءات عندما يكون عدد القمم من درجة غريبة في الرسم البياني يمكن أن يكون غريبا?

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

ما هي العلاقة بين التكافؤ في عدد من القمم والمساواة في درجة?

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