(۱۴ تیر ۱۳۹۱ ۰۱:۳۷ ق.ظ)moh3en نوشته شده توسط:  سلام

درجه رئوس مثلا خروجی های گراف منظور هست مثلا



درجه راس ها یعنی به تعداد یال های که از راس بیرون اومده تو این شکلیه درجه ها ۲ هست پس گراف اویلری هست. درسته؟

همبندی یعنی چه؟

دوست گرامی همبند یعنی بین هر دوراس در یک گراف حداقل یک مسیر باشه(حتما نباید این مسیرمستقیم باشه فقط مسیری باید باشه)،اما اویلری یعنی:یعنی یک مسیری که از همه راسهای یک گراف عبورکنه واز هر یالی فقط یکبار بگذره.
درحالت کلی شرط لازم وکافی برای وجود یک مدار اویلری دریک گراف بدون جهت اینه که گراف همبندباشه ودرجه تمام رئوس اون زوج باشه.
دراین شکلی که کشیدید درجه همه رئوس ۲نیست مثلاv5درجه اون ۴هست،ببین درجه رئوس یعنی چندتا یال از اون خارج میشه وباید برای همه راسها را بررسی کنی.دراین شکل اگه یکی از یالهای پایین را هم حذف کنی همبند هست درغیراون صورت هم بازم همبندهست چون بین همه رئوس یک یالی یا مسیری وجود داره.