سلام دوستان کسی میدونه چطورمیشه تشخیص دادگراف همبندهست یانه؟
برای گراف بدون جهت این طور باید تحلیل کرد که اگرتعداد یالهای ما برای یک گراف n راسی برابربا تعدادیالهای گراف کامل n-1 راسی به اضافه ی یک یال باشد حتما گراف ما همبنداست.برای گراف جهتدار اگرگراف با حذف جهت ها همبند باشد، گراف ما همبند است.
سلام
نکته ۱ : یک گراف ساده n راسی اگر کمتر از (n-1) یال داشته باشد، حتما ناهمبند است (همبند نیست)
نکته ۲ : یک گراف n راسی اگر بیشتر از [tex]\binom{n-1}{2}[/tex] یال داشته باشد، حتما همبند می باشد، در غیر اینصورت ممکن است همبند یا ناهمبند باشد.
موفق باشید
سلام ممنون ازپاسختون
اما اگربیشترازترکیب ۲ ازn-1 نبودممکنه همبندباشه یا نباشه اینوچطورتشخیص بدیم؟
(۲۴ آذر ۱۳۹۳ ۰۶:۳۰ ب.ظ)فاطمه رنجبر نوشته شده توسط: سلام ممنون ازپاسختون
اما اگربیشترازترکیب ۲ ازn-1 نبودممکنه همبندباشه یا نباشه اینوچطورتشخیص بدیم؟
سلام. این شرط، یه شرط کافیه. اگه برقرار باشه میدونیم همبنده. در غیر این صورت باید گراف رو ببینیم. باید از هر راس به هر راس دیگه ای مسیر باشه یا به عبارتی از یه راس به همه رئوس مسیر داشته باشیم.
سلام متوجه شدم ممممممممممممممممممنون