تئوری 4 رنگ

مدیران انجمن: parse, javad123javad

ارسال پست
نمایه کاربر
rohamavation

نام: roham hesami radرهام حسامی راد

محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 3222

سپاس: 5492

جنسیت:

تماس:

تئوری 4 رنگ

پست توسط rohamavation »

یک رنگ C1 را به حلقه بیرونی اختصاص دهید. به دلیل تقارن و توپولوژی شکل، یک نامزد امیدوارکننده است.
حلقه بیرونی هیچ مرز مشترکی با دیسک داخلی ندارد، بنابراین C1 می تواند دوباره در آنجا استفاده شود.
هر ناحیه از دیسک داخلی با دو قسمت دیگر هم مرز است، بنابراین این سه ناحیه باید هر کدام یک رنگ مجزا داشته باشند
بنابراین دو رنگ دیگر C2 و C3 را انتخاب کنید و C1، C2 و C3 را به عنوان رنگ های مناطق دیسک داخلی اختصاص دهید. فرقی نمی‌کند که کدام رنگ به کدام ناحیه اختصاص داده شود، زیرا همه آرایش‌ها با عملیات تقارن روی شکل قابل تبدیل هستند، همانطور که در مرحله (1) تا حدی رنگ شده است.
توجه کنید که دقیقاً یک بخش از حلقه میانی وجود دارد که هم مرز C2 و C3 از دیسک داخلی است. همچنین، پرفورس، C1 را از حلقه بیرونی مرز می گیرد. آن بخش به رنگ چهارم، C4 نیاز دارد.
تخصیص رنگ های انجام شده در این مرحله، هر کدام تنها یک انتخاب (بدون استفاده از رنگ پنجم) برای بخش های حلقه میانی باقی مانده به غیر از قسمت مقابل ناحیه اختصاص داده شده در مرحله قبل باقی می گذارد. پس از انجام آن تکالیف، دو گزینه برای منطقه نهایی باقی می ماند. هر دو را می توان اختصاص داد.
برای پاسخ به سؤال «الگوریتمی»، این نقشه دارای مناطقی است که فقط با چهار منطقه دیگر هم مرز هستند. یک اثبات الگوریتمی نسبتاً کوتاه وجود دارد که نشان می‌دهد اگر بتوانید همه مناطق یک نقشه به جز یکی را 4 رنگ کنید، و آخرین منطقه، R، فقط با چهار منطقه دیگر هم مرز است (آنها را R_1، R_2، R_3، R_4 به ترتیب در جهت عقربه‌های ساعت بنامید. R)، سپس می توانید کل نقشه را رنگ آمیزی کنید. برای این کار به صورت زیر عمل کنید. آسان است مگر اینکه R_1 تا R_4 از قبل از همه رنگ ها استفاده کرده باشد. بگویید آبی، سبز، قرمز، زرد به ترتیب در اطراف منطقه R هستند. اکنون ما سعی می کنیم R_1 را مجدداً به قرمز رنگ کنیم، به این امید که این به ما امکان دهد R_1 را آبی رنگ کنیم. اگر این کار را انجام دهیم، باید هر ناحیه قرمزی را که هم مرز آبی R_1 است، دوباره رنگ کنیم. سپس ما باید هر منطقه آبی را که در مرز یکی از این قرمزها قرار دارد و غیره دوباره رنگ کنیم. ما به این کار ادامه می دهیم تا زمانی که چیزهایی برای رنگ آمیزی مجدد تمام شود. اکنون یکی از این دو اتفاق می افتد: یا می توانیم R را آبی رنگ کنیم یا باید R_3 را دوباره رنگ آبی می کنیم. در مورد دوم، زنجیره ای از مناطق قرمز و آبی وجود داشت که از R_1 تا R_3 امتداد دارد، اما همچنین نمی تواند زنجیره ای از مناطق سبز و زرد از R_2 تا R_4 امتداد داشته باشد (آنها باید از جایی عبور کنند، اما این واقعیت که آنها از رنگ های مختلف استفاده می کنند یعنی نمی توانند). بنابراین اگر همین ترفند را برای رنگ آمیزی مجدد R_2 به رنگ زرد، هر ناحیه زرد در کنار R_2 سبز و غیره امتحان کنیم، این بار دیگر نیازی به رنگ آمیزی مجدد R_4 نخواهیم داشت و می توانیم R_2 را سبز رنگ کنیم.
اکنون نشان داده‌ایم که اگر بتوانیم همه چیز را جدا از منطقه‌ای که با چهار (یا کمتر) منطقه دیگر ملاقات می‌کند، رنگ‌آمیزی کنیم، می‌توانیم این ترفند رنگ‌آمیزی را انجام دهیم و سپس آخرین ناحیه را رنگ کنیم. به همین ترتیب، اگر رنگ‌آمیزی برای برخی از مناطق داشتیم، و یکی از مناطق بدون رنگ فقط با چهار منطقه رنگی حاشیه داشت، می‌توانیم به این ترتیب دوباره رنگ‌آمیزی کنیم و سپس آن منطقه را نیز رنگ‌آمیزی کنیم. بنابراین اگر بتوانیم ترتیبی از مناطق پیدا کنیم که هر کدام حداکثر با چهار منطقه قبلی هم مرز باشد، می‌توانیم به تدریج به این شکل رنگ‌آمیزی کنیم. در این نقشه می‌توانیم -- اساساً به تدریج مناطقی را که فقط چهار همسایه در باقیمانده دارند حذف کنیم، سپس آن ترتیب را معکوس کنیم -- بنابراین این الگوریتم کار خواهد کرد.
این روش اساس اثبات نادرست قضیه 4 رنگ توسط کمپ بود و توسط هیوود برای اثبات قضیه 5 رنگ استفاده شد (با استفاده از پنج رنگ، ما خوب هستیم تا زمانی که همیشه منطقه ای وجود داشته باشد که بتوانیم حداکثر مرزها را حذف کنیم. پنج مورد دیگر، اما این برای هر نقشه هواپیما صادق است). می توان از آن برای یافتن آسان نقشه 4 رنگی مارتین گاردنر "اپریل Fools" استفاده کرد که یافتن آن با آزمون و خطا بسیار دشوار است.
شما می توانید این مسئله را به عنوان یک مسئله رنگ آمیزی نمودار نشان دهید: G=(V,E) را می سازید که در آن هر کلاس یک راس است، و یک یال بین رئوس هر زمانی که دو کلاس شامل دانش آموز یکسانی باشند. رنگ‌های شما نشان‌دهنده زمان‌های امتحانی مختلف است. حداقل عددی که می توانید با آن نمودار را رنگ آمیزی کنید، کمترین تعداد بازه های زمانی است که برای نوشتن تمام امتحانات خود نیاز دارید.
مشکل به طور کلی NP سخت است، اما اگر اطلاعاتی در مورد برنامه خود داشتید، مثلاً اینکه برنامه خود مسطح بود، می توانید قضیه 4 رنگ را برای نوشتن همه امتحانات با هم اعمال کنید.
من 100% مطمئن نیستم که در یک مسئله زمان‌بندی واقعی، یک نمودار مسطح دریافت کنید، اما یک درس گسترده‌تر در اینجا وجود دارد: نمودارها به طور گسترده برای چیزهایی که فوراً آشکار نیستند قابل استفاده هستند. قضیه 4 رنگ فقط در مورد نمودارها و نقشه ها نیست، می توان از آن برای مدل سازی مشکلات زندگی واقعی استفاده کرد که در آن شما مجموعه ای از اشیاء و برخی روابط دودویی بین آن اشیاء را بیان می کنید..hope I helped you understand the question. Roham Hesami, sixth semester of aerospace engineering
smile072 smile072 رهام حسامی ترم ششم مهندسی هوافضا
تصویر

ارسال پست