تعداد زیرگراف های یک گراف کامل - نسخهی قابل چاپ |
تعداد زیرگراف های یک گراف کامل - !!! - ۲۸ شهریور ۱۳۹۳ ۰۸:۳۸ ب.ظ
سلام دوستان تعداد زیرگراف ها از چه فرمولی بدست میاد؟ من قبلا یه فرمولی دیده بودم که برای K6 بود، درسته؟! [tex]\sum\binom{6}{k}(2^{\binom{k}{2}})\: for\: k=1\: to\: 6[/tex] |
RE: تعداد زیرگراف ها - !!! - ۳۱ شهریور ۱۳۹۳ ۰۱:۲۷ ب.ظ
اگه کسی جواب این مسئله رو میدونه بگه لطفا. |
RE: تعداد زیرگراف ها - software94 - 31 شهریور ۱۳۹۳ ۰۲:۴۱ ب.ظ
میشه سوالتون رو واضح تر بپرسید |
RE: تعداد زیرگراف ها - !!! - ۳۱ شهریور ۱۳۹۳ ۰۲:۵۳ ب.ظ
من یه گرافی دارم، برای مثال همین K6، میخوام بدونم تعداد زیرگراف هاش چند تاست. ---------------------------------- اون فرمولی هم که برای K6 نوشتم از تمرینات گریمالدی بود. (اگر اشتباه نکنم) |
RE: تعداد زیرگراف ها - Jooybari - 31 شهریور ۱۳۹۳ ۰۲:۵۸ ب.ظ
سلام. روش حل به این شکله که باید چند راس از رئوس گراف و بعد چند یال از یالهای بین این رئوس رو جدا کنیم. برای گراف کامل چون میدونیم بین تمام رئوس یال وجود داره بین k راس انتخاب شده [tex]2^k[/tex] یال داریم. هر یال هم میتونه باشه یا نباشه. پس دو حالت داره. پس تعداد زیرگرافهای k راسی یک گراف کامل n راسی برابر [tex]\binom{n}{k}2^{\binom{k}{2}}[/tex] خواهد بود. |
RE: تعداد زیرگراف ها - !!! - ۳۱ شهریور ۱۳۹۳ ۰۸:۳۸ ب.ظ
متشکرم جناب مدیر، کاملا متوجه شدم. |