سلام.. ممنون میشم اگه کسی این ۲سوال من را با توضیح برای من جواب بده.
۱- فرض کنیم G=(V,E) گراف سودار باشد که |e=|E و |n =|V مقادیر Σ id(v و Σ od(v را بیابید؟ (درجه ورودی راس و درجه خروجی راس)
۲- فرض کنیم K=(V,E) گراف سودار کامل(تورنومنت) باشد. مقادیر Σ id(v و Σ od(v را بیابید؟ (درجه ورودی راس و درجه خروجی راس)
اگه منظورتون محاسبه مجموع درجات ورودی و مجموع درجات خروجی در گراف جهتدار هستش،با این فرض که تعریف درجه ورودی و خروجی رو میدونید و گراف ساده هست.
چون گراف جهت دار هست و جهت یال مهمه و هریال دقیقا ۱ بار شمارش میشه پس:
[tex]\sum indeg=\sum outdeg=\left | E \right |[/tex]
میدونیم که در گراف کامل بدون جهت [tex]\left | E \right |=\frac{V(V-1)}{2}[/tex] و
در گراف کامل جهت دار [tex]\left | E \right |=\left | V \right |*(\left | V \right |-1)[/tex]
پس طبق نکته بالا در هرگراف کامل جهت دار
[tex]\sum indeg=\sum outdeg=\left | E \right |=\left | V \right |*(\left | V \right |-1)[/tex]
موفق باشید.
ممنون بابت جوابتون... لطف کردی..
سوال:
فرض کنیم G=(V,E) گراف بیسوی بیطوقه ای باشد که در آن V={v1,v2,v3,....,v10} .
اگر deg(v1)=2 , deg(v2)=3 , deg(v3)=3 , deg(v4)=5 , deg(v5)=1 , deg(v6)=2 , deg(v7)=5 , deg(v8)=2 , deg(v9)=3 , deg(v10)=2 باشد.
deg(vi) را در مکمل G به ازای i=1 to 10 تعیین کنید.
ممنون میشم اگه کسی این را با جوابش برام توضیح بده
برای حل این مثال هم شما گراف کامل k10 رو در نظر بگیرید.اون یالهایی که در گراف کامل هست و در این گراف نیس در گراف مکمل قرار داره.سوال راحتیه.به همین طریقی که گفتم میشه حلش کرد.البته راه حل های خیلی کوتاهتر هم داره.
نمیفهمم منظورت چیه؟
خب راه حلش نمیدونم.. توضیح شما را هم نفهمیدم.. میشه بیشتر توضیح بدی.. ممنون