والدليل على أن مجموع درجات الرؤوس في أي رسم بياني يساوي ضعف عدد الحواف هو أحد النتائج الأساسية في نظرية الرسم البياني. تنص هذه النتيجة على أنه إذا أخذنا أي رسم بياني وجمعنا درجات جميع رؤوسه ، نحصل على عدد مزدوج من الحواف ، مع مراعاة التعددية. ويستند هذا الدليل على مبدأ الاستقراء.
بادئ ذي بدء ، ضع في اعتبارك الحالة الأساسية: رسم بياني يتكون من رأس واحد فقط. في هذه الحالة ، ستكون درجة الرأس الواحد صفرا ، وسيكون مجموع درجات الرؤوس صفرا أيضا. وبالتالي ، فإن الحالة الأساسية تؤكد حقيقة البيان.
لنفترض الآن أن العبارة صحيحة بالنسبة للرسم البياني ذي الرؤوس (ن-1) ، حيث ن هو رقم طبيعي. النظر في الرسم البياني مع ن القمم. دعنا نختار رأسا تعسفيا في هذا الرسم البياني ونحذفه مع جميع حوافه الحادثة. نحصل على رسم بياني برؤوس (ن-1) ، والتي ، وفقا للافتراض ، يساوي مجموع درجات الرؤوس ضعف عدد الحواف.
الآن ، دعنا نضيف الرأس المحذوف مرة أخرى إلى الرسم البياني. سيتم توصيل الرأس بعدد من الرؤوس في الرسم البياني. يؤدي إرفاق رأس جديد إلى زيادة مجموع درجات الرؤوس برقم يساوي درجة الرأس المضاف. نظرا لأن الرأس الذي يتم حذفه كان له درجة مساوية لعدد حواف الحادث ، عند إضافته ، سيزداد مجموع الدرجات بمقدار درجة هذا الرأس. ويترتب على ذلك أن مجموع درجات الرؤوس في الرسم البياني الأصلي يساوي مجموع درجات الرؤوس في الرسم البياني برؤوس (ن-1) تزداد بدرجة الرأس المضاف ، أي بمقدار واحد.
هذا يعني أنه سيتم زيادة العدد الإجمالي للحواف في الرسم البياني بمقدار واحد بعد إضافة رأس جديد. لذلك ، فإن مجموع درجات الرؤوس في الرسم البياني الأصلي يساوي مجموع درجات الرؤوس في الرسم البياني مع (ن-1) زيادة الرؤوس بمقدار اثنين. بافتراض أن مجموع درجات الرؤوس في رسم بياني برؤوس (ن-1) يساوي ضعف عدد الحواف ، نحصل على أن مجموع درجات الرؤوس في رسم بياني برؤوس ن يساوي ضعف عدد الحواف زائد اثنين. يمكن كتابة هذا البيان كمساواة: مجموع درجات القمم = 2 * عدد الحواف + 2. وبالتالي ، فإن الدليل كامل.
- إثبات المساواة في مجموع درجات الرؤوس وعدد الحواف في الرسم البياني
- تعريف الرسم البياني وعناصره
- يعتمد الدليل على مثال الرسم البياني التعسفي
- التبرير الرياضي للبيان
- أمثلة على تطبيق المساواة في درجات القمم وعدد الحواف
- سؤال وجواب
- كيف يمكننا أن نثبت أنه في أي رسم بياني مجموع درجات القمم يساوي ضعف عدد الحواف?
- لماذا يساوي مجموع درجات الرؤوس في أي رسم بياني مضاعفة عدد الحواف?
- هل يمكنك شرح دليل النظرية على مجموع درجات الرؤوس في الرسم البياني?
إثبات المساواة في مجموع درجات الرؤوس وعدد الحواف في الرسم البياني
لإثبات المساواة في مجموع درجات الرؤوس وعدد الحواف في الرسم البياني ، عادة ما يتم استخدام طريقة الحث الرياضي. سنثبت هذا البيان للرسوم البيانية البسيطة ، أي الرسوم البيانية بدون حلقات وحواف متعددة.
اسمحوا ز يكون رسم بياني بسيط مع ن القمم و م الحواف. بادئ ذي بدء ، ضع في اعتبارك قاعدة الحث متى ن = 1. في هذه الحالة ، الرسم البياني جي له رأس واحد فقط وليس له حواف. لذلك ، فإن مجموع درجات الرؤوس (يساوي 0) يساوي بالفعل عدد الحواف (يساوي 0) ، وقاعدة الحث صحيحة.
الآن دعونا نفترض أن العبارة صحيحة لجميع الرسوم البيانية البسيطة مع ما يصل إلى ن — 1 القمم. دعونا نثبت ذلك لرسم بياني بسيط ز مع ن القمم و م الحواف.
لنختار أي رأس الخامس في الرسم البياني جي. إزالة هذا الرأس من الرسم البياني جي يعطينا رسما بيانيا بسيطا جديدا جي ' يحتوي على ن-1 رؤوس. من افتراض الاستقراء ، مجموع درجات الرؤوس في جي 'يساوي عدد الحواف في جي'.
الآن ضع في اعتبارك مجموع درجات الرؤوس في الرسم البياني جي يتكون من درجة الرأس الخامس ومجموع درجات الرؤوس في جي'. إذا أزلنا الرأس الخامس من الرسم البياني جي ، فسيتم أيضا حذف كل حافة يشارك فيها الرأس الخامس. لذلك ، فإن مجموع درجات الرؤوس في جي يساوي مجموع درجات الرؤوس في جي زائد درجة الرأس الخامس.
وبالتالي ، فإن مجموع درجات الرؤوس في الرسم البياني جي يساوي عدد الحواف في جي ' زيادة بدرجة الرأس الخامس. ولكن بافتراض الاستقراء ، فإن مجموع درجات الرؤوس في جي 'يساوي عدد الحواف في جي'. لذلك ، فإن مجموع درجات القمم في جي يساوي ضعف عدد الحواف ، ويتم إثبات البيان.
وهكذا ، أثبتنا أنه في أي رسم بياني بسيط ، فإن مجموع درجات الرؤوس يساوي ضعف عدد الحواف.
تعريف الرسم البياني وعناصره
الرسم البياني هو بنية بيانات مجردة تتكون من مجموعة من الرؤوس ومجموعة من الحواف التي تربط هذه الرؤوس. تستخدم الرسوم البيانية على نطاق واسع في مجالات مختلفة مثل الرياضيات وعلوم الكمبيوتر ونظرية الشبكة وغيرها.
العناصر الرئيسية للرسم البياني:
- الرأس: هذا هو العنصر الرئيسي في الرسم البياني. يمكن أن يكون لكل رأس اسم أو تسمية خاصة به تسمح لك بتحديده. يمكن توصيل الرؤوس ببعضها البعض عن طريق الحواف.
- الحافة: هذا هو الاتصال بين رأسين. يمكن توجيه الحافة إذا كان لها اتجاه معين ، أو غير موجهة إذا لم يكن لها اتجاه معين. يمكن ترجيح الحواف ، أي أن يكون لها وزن عددي مرتبط بها.
- درجة الرأس: هذا هو عدد الحواف المتصلة برأس معين. يعتبر الرأس مجاورا لرأس آخر إذا كان متصلا بحافة.
يمكن أن تكون الرسوم البيانية مختلفة في الطبيعة والخصائص. على سبيل المثال ، يمكن توجيه الرسوم البيانية أو غير موجهة أو متصلة أو غير متصلة أو دورية أو غير دورية. هناك أيضا أنواع خاصة من الرسوم البيانية مثل الرسوم البيانية الكاملة والأشجار وما إلى ذلك.
من أجل راحة العمل مع الرسوم البيانية ، هناك طرق وخوارزميات مختلفة ، مثل البحث عن العمق أولا ، والبحث عن الاتساع أولا ، وخوارزمية ديكسترا وغيرها. تسمح لك هذه الطرق بحل العديد من المشكلات المتعلقة بالرسم البياني ، مثل العثور على أقصر مسار ، وتحديد اتصال الرسم البياني ، والبحث عن الدورات ، وما إلى ذلك.
يعتمد الدليل على مثال الرسم البياني التعسفي
النظر في الرسم البياني التعسفي مع ن القمم و م الحواف.
دعونا نشير إلى درجة الرأس بواسطة دي. ثم مجموع كل درجات القمم يساوي:
| فيرتكس | درجة (دي) |
|---|---|
| 1 | دال-1 |
| 2 | د2 |
| ... | ... |
| n | دن |
تلخيص جميع الدرجات ، نحصل على:
دال-1 + دال-2 + ... + دن
من ناحية أخرى ، تربط كل حافة رأسين وتضيف قوتين إلى المجموع. نظرا لوجود حواف م في الرسم البياني ، فإن مجموع الدرجات هو 2 م.
وهكذا نحصل على المساواة:
دال-1 + دال-2 + ... + دن = 2 م
الدليل كامل.
التبرير الرياضي للبيان
من أجل إثبات العبارة رياضيا بأن مجموع درجات رؤوس الرسم البياني يساوي العدد المزدوج للحواف ، يمكن استخدام مبدأ الحث.
النظر في الرسم البياني ز مع ن القمم. دع ص (ن) يكون بيانا حول مجموع درجات رؤوس الرسم البياني ز مع ن الرؤوس.
- قاعدة الحث: للحالة ن = 1 ، الرسم البياني جي يتكون من رأس واحد فقط ولا توجد حواف. مجموع درجات القمم هو صفر ، وعدد مزدوج من الحواف هو أيضا صفر. يتم تنفيذ البيان ص (1).
- انتقال: افترض أن العبارة ص (ك) صحيح بالنسبة للرسم البياني جي مع ك القمم. دعنا نضيف رأسا جديدا إلى الرسم البياني جي ، الحصول على الرسم البياني جي ' مع ك + 1 القمم.
عند إضافة رأس جديد إلى رسم بياني ، ستتصل جميع حواف هذا الرأس الجديد بالرؤوس الموجودة في الرسم البياني ز. ستضيف كل حافة وحدة واحدة إلى درجات رأسين: أحدهما متصل بالحافة الجديدة ، وواحد من الرؤوس التي ترتبط بها بالفعل.
مجموع درجات الرؤوس في الرسم البياني جي ' سيكون مساويا لمجموع درجات الرؤوس في الرسم البياني الأصلي جي ، زيادة بمقدار 2 ك-عدد الحواف الموجودة في الرسم البياني جي.
بافتراض الاستقراء ، البيان ص(ك) يحمل. وبالتالي ، عند إضافة رأس جديد إلى الرسم البياني ، سيتم أيضا تنفيذ العبارة ص (ك+1).
ويترتب على أساس الاستقراء ومبدأ الاستقراء أن البيان ص(ن) صحيح لأي عدد طبيعي ن.
وهكذا ، يتم الانتهاء من الدليل الرياضي للبيان أن مجموع درجات رؤوس الرسم البياني يساوي العدد المزدوج للحواف.
أمثلة على تطبيق المساواة في درجات القمم وعدد الحواف
تعد المساواة بين درجات الرؤوس وعدد الحواف حقيقة مهمة في نظرية الرسم البياني ، والتي لها العديد من التطبيقات في مختلف المجالات.
1. بلانيميتري
في قياس الكواكب ، تسمح لك المساواة بين درجات الرؤوس وعدد الحواف بتحديد العلاقة بين عدد الحواف والزوايا في المضلع. على سبيل المثال ، بالنسبة لمضلع تعسفي مع ن الجانبين ، مجموع درجات الرؤوس هو 2ن. هذا يعني أن هناك دائما رأسان على الأقل بدرجة زوجية في المضلع.
2. وسائل التواصل الاجتماعي
في الشبكات الاجتماعية ، يمكن استخدام المساواة في درجات القمم وعدد الحواف لتحليل الاتصالات بين المستخدمين. على سبيل المثال ، إذا كان مجموع درجات أصدقاء كل مستخدم في بعض الشبكات الاجتماعية يساوي ضعف عدد أصدقائه ، فيمكننا أن نستنتج أن الشبكة متناظرة وأن جميع المشاركين فيها لديهم علاقات ودية.
3. شبكات النقل
في شبكات النقل ، يمكن أن تكون المساواة في درجات الرؤوس وعدد الحواف مفيدة لتخطيط المسار وتحسين تدفق حركة المرور. على سبيل المثال ، إذا كان مجموع درجات التوقفات في النقل الحضري يساوي ضعف عدد الخطوط ، فهذا يعني أن كل محطة لها خطان يمران عبرها ، مما يبسط حركة الركاب.
4. شبكات الكمبيوتر
في شبكات الكمبيوتر ، يمكن تطبيق المساواة في درجات الرؤوس وعدد الحواف لتحليل بنية الشبكة وتحسينها. على سبيل المثال ، إذا كان مجموع درجات كل عقدة في الشبكة يساوي ضعف عدد جيرانها ، فهذا يعني أن الشبكة فعالة ويمكن للعقد تبادل البيانات دون اختناق.
وبالتالي ، فإن المساواة في درجات القمم وعدد الحواف لها مجموعة واسعة من التطبيقات في مختلف المجالات ، من قياس الكواكب إلى تحليل الشبكات الاجتماعية وشبكات النقل.
سؤال وجواب
كيف يمكننا أن نثبت أنه في أي رسم بياني مجموع درجات القمم يساوي ضعف عدد الحواف?
لإثبات هذا البيان ، يمكنك استخدام طريقة الحث. الحالة الأساسية: بالنسبة للرسم البياني برأس واحد ، فإن العبارة صحيحة ، لأن درجة الرأس تساوي صفرا ، وعدد الحواف يساوي صفرا. لنفترض أن العبارة صحيحة بالنسبة للرسم البياني لـ ن القمم. النظر في رسم بياني من ن + 1 القمم: دعونا إضافة قمة جديدة وتوصيله مع حواف إلى كل من القمم ن السابقة. وبالتالي ، فإن درجة كل من السابق ن تزداد الرؤوس بمقدار 1 ، ويزداد عدد الحواف بمقدار ن. بافتراض الاستقراء ، فإن مجموع درجات الرؤوس في الرسم البياني السابق يساوي ضعف عدد الحواف ، أي يساوي 2 * (ن-1). بإضافة قمة جديدة مع ن الحواف ، يصبح العدد الإجمالي للحواف 2 * (ن-1) + ن = 2 * ن ، ومجموع درجات القمم هو أيضا 2 * ن. وهكذا ، ثبت البيان.
لماذا يساوي مجموع درجات الرؤوس في أي رسم بياني مضاعفة عدد الحواف?
هذه الخاصية من الرسم البياني يمكن تفسيرها بسهولة. يتم تحديد درجة الرأس من خلال عدد الحواف المتصلة برأس معين. لنفترض أن هناك ن القمم و م حواف في الرسم البياني. كل حافة لها نقطتا نهاية ، أي أنها تساهم في درجة رأسين. وبالتالي ، فإن مجموع درجات جميع القمم يساوي ضعف عدد الحواف ، أي 2 م. وبالتالي ، بغض النظر عن البنية المحددة للرسم البياني ، ستظل المساواة دائما: مجموع درجات الرؤوس = 2 م.
هل يمكنك شرح دليل النظرية على مجموع درجات الرؤوس في الرسم البياني?
يمكن إجراء إثبات النظرية على مجموع درجات الرؤوس في الرسم البياني على النحو التالي. النظر في الرسم البياني التعسفي مع ن القمم و م الحواف. دع كل قمة لدي درجة دي. مجموع درجات جميع القمم يساوي د1 + د2 + ... + دن. الحافة التي تربط الرؤوس أنا و ي يساهم في درجة كل من هذه الرؤوس. وهكذا ، لكل حافة ، يزيد مجموع درجات القمم بمقدار 2. ويترتب على ذلك أن مجموع درجات الرؤوس هو 2 م ، وهو ضعف عدد الحواف في الرسم البياني.