در نظریهٔ گراف، قضیه بروکس ( به انگلیسی: Brooks' theorem ) رابطه ای بین بیشترین درجه یک گراف و عدد رنگی آن بیان می کند. بر اساس این قضیه، در یک گراف همبند که هر راسی حداکثر Δ همسایه دارد، راس ها می توانند تنها با Δ رنگ، رنگ آمیزی شوند، به جز در دو حالت، گراف های کامل و گراف های دوری با دور به طول فرد، که به Δ + ۱ رنگ نیاز دارند.
این قضیه به افتخار R. Leonard Brooks نام گذاری شده است، کسی که یک اثبات از این مسئله را در سال ۱۹۴۱ منتشر کرد. یک رنگ آمیزی با تعداد رنگ هایی که قضیه بروکس ارائه می دهد، عموماً رنگ آمیزی بروکس یا Δ - رنگ آمیزی نامیده می شود
برای هر گراف بدون جهت همبند G با بیشترین درجه Δ، عدد رنگی G حداکثر Δ است مگر در حالتی که G خوشه یا دور فرد باشد، در این حالت عددرنگی Δ + ۱ است.
László Lovász یک اثبات ساده شده برای قضیه بروکس ارائه داد. اگر گراف دوهمبند نباشد مؤلفه های دوهمبند آن را می توان به صورت جدا رنگ آمیزی کرد و سپس رنگ آمیزی ها را با هم ترکیب کرد. اگر گراف یک راس v با درجهٔ کمتر از Δ داشته باشد، آنگاه یک الگوریتم رنگ آمیزی حریصانه که راس های دور از v را قبل از راس های مجاور آن رنگ می کند حداکثر Δ رنگ استفاده می کند. ازاین رو، سخت ترین حالت اثبات به گراف های Δ - منتظم دوهمبند با Δ≥۳ مربوط است. در این حالت، Lovász نشان داد که می توان یک درخت پوشا پیدا کرد به طوری که دو راس همسایه با ریشه v, u و w که با هم مجاور نیستند در درخت برگ باشند. یک رنگ آمیزی حریصانه از راس u و w شروع می کند و راس های باقی مانده از درخت پوشا را از پایین به بالا با حداکثر Δ رنگ، رنگ می کند. برای رنگ کردن هر راس به جز v، آن راس یک پدر در درخت دارد که هنوز رنگ نشده است، پس همسایه های رنگ شده این راس نمی توانند همهٔ رنگ ها را استفاده کرده باشند، در حالی که برای راس v هم دو راس همسایه آن، u و w رنگ یکسان دارند پس باز هم یک رنگ برای راس v باقی می ماند.
یک تعریف عمومی تر از این تئوری به فهرست رنگ آمیزی اشاره می کند: برای هر گراف هم بند بدون جهت با بیش ترین درجه Δ که خوشه یا دور فرد نباشد، و یک فهرست از Δ رنگ برای هر راس، می توان به هر راس یک رنگ از این فهرست تخصیص داد به صورتی که هیچ دو راس همسایه، رنگ یکسان نداشته باشند. به عبارت دیگر، فهرست تعداد رنگ گراف هم یند بدون جهت G هرگز از Δ بیش تر نمی شود، مگر G خوشه یا دور فرد باشد. این قضیه توسط Vadim Vizing اثبات شده است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین قضیه به افتخار R. Leonard Brooks نام گذاری شده است، کسی که یک اثبات از این مسئله را در سال ۱۹۴۱ منتشر کرد. یک رنگ آمیزی با تعداد رنگ هایی که قضیه بروکس ارائه می دهد، عموماً رنگ آمیزی بروکس یا Δ - رنگ آمیزی نامیده می شود
برای هر گراف بدون جهت همبند G با بیشترین درجه Δ، عدد رنگی G حداکثر Δ است مگر در حالتی که G خوشه یا دور فرد باشد، در این حالت عددرنگی Δ + ۱ است.
László Lovász یک اثبات ساده شده برای قضیه بروکس ارائه داد. اگر گراف دوهمبند نباشد مؤلفه های دوهمبند آن را می توان به صورت جدا رنگ آمیزی کرد و سپس رنگ آمیزی ها را با هم ترکیب کرد. اگر گراف یک راس v با درجهٔ کمتر از Δ داشته باشد، آنگاه یک الگوریتم رنگ آمیزی حریصانه که راس های دور از v را قبل از راس های مجاور آن رنگ می کند حداکثر Δ رنگ استفاده می کند. ازاین رو، سخت ترین حالت اثبات به گراف های Δ - منتظم دوهمبند با Δ≥۳ مربوط است. در این حالت، Lovász نشان داد که می توان یک درخت پوشا پیدا کرد به طوری که دو راس همسایه با ریشه v, u و w که با هم مجاور نیستند در درخت برگ باشند. یک رنگ آمیزی حریصانه از راس u و w شروع می کند و راس های باقی مانده از درخت پوشا را از پایین به بالا با حداکثر Δ رنگ، رنگ می کند. برای رنگ کردن هر راس به جز v، آن راس یک پدر در درخت دارد که هنوز رنگ نشده است، پس همسایه های رنگ شده این راس نمی توانند همهٔ رنگ ها را استفاده کرده باشند، در حالی که برای راس v هم دو راس همسایه آن، u و w رنگ یکسان دارند پس باز هم یک رنگ برای راس v باقی می ماند.
یک تعریف عمومی تر از این تئوری به فهرست رنگ آمیزی اشاره می کند: برای هر گراف هم بند بدون جهت با بیش ترین درجه Δ که خوشه یا دور فرد نباشد، و یک فهرست از Δ رنگ برای هر راس، می توان به هر راس یک رنگ از این فهرست تخصیص داد به صورتی که هیچ دو راس همسایه، رنگ یکسان نداشته باشند. به عبارت دیگر، فهرست تعداد رنگ گراف هم یند بدون جهت G هرگز از Δ بیش تر نمی شود، مگر G خوشه یا دور فرد باشد. این قضیه توسط Vadim Vizing اثبات شده است.
wiki: قضیه بروکس