درجه رأس و قضیه دستدادن؛ شمارش یالهای گراف
آموزش درجه رأس، مجموع درجات، تعداد یالها، رأسهای فرد و گراف کامل همراه تستهای نظریه گراف.
پاسخ کوتاه
در گراف بدون جهت، هر یال به درجه دو رأس سهم میدهد. همین مشاهده ساده قضیه دستدادن را میسازد و اجازه میدهد از مجموع درجات تعداد یالها یا از اطلاعات ناقص درجه یک رأس را پیدا کنیم.
درجه رأس
درجه هر رأس تعداد یالهای متصل به آن است. یک حلقه در صورت وجود دو واحد به درجه همان رأس اضافه میکند، چون دو سر یال روی آن قرار دارند. در گراف ساده حلقه و یال موازی نداریم و درجه هر رأس حداکثر n-1 است.
قضیه دستدادن
مجموع درجه همه رأسهای یک گراف بدون جهت برابر دو برابر تعداد یالهاست: Σdeg(v)=2|E|. دلیل آن این است که هر یال دقیقاً دو سر دارد. بنابراین مجموع درجات همیشه زوج است و نصف آن تعداد یالها را میدهد.
رأسهای درجه فرد
تعداد رأسهایی که درجه فرد دارند همیشه زوج است. اگر مجموع همه درجات زوج باشد، تعداد جملههای فرد در این مجموع نمیتواند فرد باشد. این نتیجه برای رد سریع بعضی دنبالههای درجهای در تستها بسیار مفید است.
گراف کامل و منتظم
در گراف کامل K_n هر رأس به n-1 رأس دیگر وصل است، پس درجه همه رأسها n-1 و تعداد یالها n(n-1)/2 است. در گراف r-منتظم با n رأس نیز تعداد یالها nr/2 خواهد بود و حاصل nr باید زوج باشد.
مثال و تست کوتاه
اگر درجات پنج رأس برابر 2، 3، 3، 4 و x و گراف 7 یال داشته باشد، مجموع درجات 14 است. پس 12+x=14 و x=2. دو رأس درجه فرد داریم که با زوجبودن تعداد رأسهای فرد سازگار است.
چکلیست حل تست
- هر یال دو واحد به مجموع درجات میافزاید.
- تعداد رأسهای درجه فرد زوج است.
- تعداد یالهای K_n برابر n(n-1)/2 است.