سلام دوستان
فرمول دقیقی برا تشخیص خلوت بودن یا شلوغ بودن گراف وجودهست؟
سلام. وقت بخیر.
خلوت یا شلوغ بودن هم بیشتر زمانی اهمیت داره که تعداد رئوس گراف زیاد باشه. در چنین مواقعی میشه تعداد یالهای گراف رو از درجه رئوسش نوشت. مثلاً تعداد یالها از درجه [tex]\theta (n^2)[/tex] یا [tex]\theta (n)[/tex] یا موارد مشابهه. اگه تعداد یالها حداکثر از درجه n بود میشه گفت گراف خلوته.
تاثیر این بررسی هم زمانیه که نحوه ذخیره سازی و بازیابی یالها متفاوته. اگه خلوت باشه میشه از لینک لیست استفاده کرد و اگه شلوغ باشه بهتره از همون ماتریس استفاده بشه.
از درجه ی n یعنی مثلا اگر تعداد رئوس ده تا باشه تعداد یال ها حداکثر تا چند تا میتونه باشه که بگیم گراف خلوته؟[/size]
(۰۷ اردیبهشت ۱۳۹۵ ۰۵:۰۴ ب.ظ)behnazmahrokh نوشته شده توسط: از درجه ی n یعنی مثلا اگر تعداد رئوس ده تا باشه تعداد یال ها حداکثر تا چند تا میتونه باشه که بگیم گراف خلوته؟[/size]
با فرض بزرگ بودن n. فرض کنید تعداد یالها بین n/3 تا ۵n باشه.
از پاسختون خیلی ممنونم .