برای آنکه از تابلوهای گران قیمت یک گالری هنری نگهداری شود لازم است که محیط امنی ایجاد شود. زیرا دزدیده شدن این اشیا بسیار محتمل است. حال برای آنکه به هنگام شب بتوان بیشترین امنیت را ایجاد کرد باید بتوان این مساله را حل کرد که: چه تعداد دوربین نیاز است و مکان آن بهتر است کجا باشد؟ ??♀️
قبلش بگم این مساله خیلی قدیمیه و بر میگرده به ۱۹۷۳ یعنی ۴۸ سال پیش☺️
در این قسمت اول درباره مساله میگیم و قدم به قدم به جواب میرسیم. یک گالری را میتوان به صورت یک سه بعدی در نظر گرفت ولی قسمت کف آن را میتوان تنها در نظر گرفت تا از این طریق به توان گالری را به یک پلیگان یا چند ضلعی مدل کرد. در یک چند ضلعی دوربین ها نقطه ها هستند و هر دوربین میتواند جاهایی از گالری را ببیند که از آن دوربین بتوان به سمت آن خط کشید به طوری که خط کشیده شده جایی از چند ضلعی را قطع نکند. چند ضلعی میتواند به صورت غیر محدب باشد زیرا اگر چند ضلعی محدب باشد تنها یک دوربین برای نگهبانی تمام گالری کافی است.
شکل زیر نمونه ای از یک گالری را نشان میدهد.
یکی از ابتدایی ترین راه حل ها استفاده از مثلث بندی است. ثابت شده است که تمام چند ضلعی ها با n راس دارای n-2 مثلث هستند. برای مثلا چند ضلعی فوق را به صورت زیر مثلث بندی میکنیم.
حال میتوان در هر یک از مثلث ها یک دوربین قرار داد و از این طریق گالری را تحت نظر قرار داد! ولی این تعداد دوربین بسایر زیاد است! در واقع باید n-2 دوربین را استفاده کرد که با یکم فکر میتوان فهمید که میتوان یک دوربین را بر روی ضلع مشترک بین دو تا مثلث قرار داد که از این طریق تعداد دوربین ها به نصف کاهش پیدا میکند. ولی اگر باز هم دقیق تر بشیم به این مورد میرسیم که میتوان دوربین را بر روی راس ها قرار داد زیرا ممکن است یک راس راس مشترک چندید مثلث باشد که این ایده بنیان گذار روش زیر است:
باید راس هایی از چندضلعی انتخاب شود که هر کدام از مثلث های داخل چند ضلعی حداقل دارای یکی از راس ها باشد. برای همین از مساله coloring-3 استفاده میشود و به این شکل است که راس ها را به سه رنگ طوری رنگ میزند که هیچ دو رنگی در دو طرف دو ضلع چند ضلعی و یا خطوطی که برای ساخت مثلث ها کشیده ایم یک رنگ نباشد. با این کار میتوان تعداد دوربین ها را به n/3 کاهش داد!?
حالا سوالی که پیش می آید این است که آیا این رنگبندی برای تمام چندضلعی ها امکان پذیر است؟
باید این چند ضلعی را به فضای دو گان آن برد. به این صورت که هر کدام از مثلث ها یک نقطه هستند و اگر بین آن ها ضلع مشترکی وجود داشته باشد باشد بین آنها یک خط رسم کرد که چند ضلعی مورد بحث به این صورت میشود.
حالا فرض کنید از یک مثلث شروع کردیم و مثلثی که در آن هستیم را با سه رنگ رنک کرده ایم حالا می خواهیم به نقطه بعدی برویم نقطه ای هست که در مثلث کناری قرار دارد که تنها یک راس آن رنگ نشده است و با توجه به آنکه شکل ایجاد شده درخت است و از این روی قبلا آن را ملاقات نکرده ایم میتوان آزادانه آن را رنگ کرد.
پس اثبات میشود مساله گالری را میتوان با حد اکثر n/3 دوربین حل کرد.
