جاده های شهر شاز آباد

از shaazzz
پرش به ناوبری پرش به جستجو

به تازگی قراره که تو شاز آباد جاده کشی شه. میدونیم که شاززز آباد 100 تا شهر داره و یک نوع جاده کشی مطلوبه اگه هر 11 تا شهرو که در نظر بگیریم حداقل 2 تا باشن که بینشون یه جاده هست ، حالا ثابت کنید َیک جاده کشی مطلوب حداقل 450 تا جاده دارد. یک مثال هم بزنید که شامل دقیقا 450 جاده است.

پاسخ

ما به دنبال گرافی با 100 راس هستیم که عدد استقلال آن کمتر اکید از ۱۱ باشد و کمترین یال ممکن را داشته باشد.

مکمل این گراف، عدد خوشه ای آن کمتر اکید از ۱۱ است و بیشترین یال ممکن را دارد.

طبق قضیه توران، هر گراف ۱۰۰ راسی که خوشه با اندازه ۱۱ نداشته باشد، حداکثر ۴۵۰۰ یال دارد. پس مکمل این گراف حداقل یال می تواند داشته باشد.

برای قسمت مثال، می توانیم گرافی را در نظر بگیریم که از ۱۰ گراف کامل ۱۰ راسی مجزا تشکیل شده باشد. این گراف ۴۵۰ یال دارد و هر ۱۱ راس از این گراف طبق اصل لانه کبوتری، دو راس متعلق به یکی از گراف های کامل است و در نتیجه آن دو به هم یال دارند.