نظریه دیلورث

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

ضد-زنجیره : یک ضد-زنجیره در یک مجموعه ی مجموعه جزئاً مرتب ، یک مجموعه از اعضا می باشد که هیچ دو عضوی از آن ، با هم دو به دو مقایسه پذیر نمی‌باشند .

زنجیره : یک زنجیره در یک مجموعه ی ترتیب جزیی ، یک مجموعه از اعضا می باشد که هر دو عضوی از آن ، با هم دو به دو مقایسه پذیر می باشند .

نظریه ی Dilworth : در یک ترتیب جزیی ، یک ضد-زنجیره ی A و یک افراز ترتیب به یک دسته ی P تایی از زنجیره ها وجود دارد ، به طوری که تعداد زنجیره ها در افراز برابر با تعداد اعضای A ، می باشد ، این اتفاق وقتی می افتد که مجموعه ی A ، بزرگترین ضد-زنجیره در ترتیب باشد ، برای هر ضد-زنجیره ، حداکثر یک عضو از هر کدام از اعضای P ، می تواند داشته باشد و به طور مشابه P باید کوچکترین دسته ای از زنجیره ها باشد که ترتیب می تواند به آنها ، افراز شود ، که برای هر افراز به زنجیره ها ، باید حداقل یک زنجیره از اعضای A ، باشد .طول ترتیب جزیی ، به عنوان سایز رایج A و P ،تعریف می شود. یک تعریف دیگر از این نظریه به این صورت است که در هر مجموعه ی ترتیب جزیی محدود ، بیشترین تعداد اعضا در هر ضد-زنجیره ، برابر با کمترین تعداد زنجیره ها یی است که ترتیب ، می تواند به آنها افراز شود .

اثبات نظریه ی Dilworth ، با استفاده از نظریه ی König[ویرایش]

اثبات نظریه ی Dilworth ، با استفاده از نظریه ی König : ساختن یک گراف دو بخشی از روی یک ترتیب جزیی و افراز آن به زنجیره ها بر اساس یک جورسازی .

برای اثبات نظریه ی Dilworth ، با یک مجموعه ی ترتیب جزیی S ، با n عضو ، ازنظریه ی König، استفاده می کنیم . یک گراف دوبخشی G=(U,V،E) ،تعریف می کنیم به طوری که U=V=S و (u,v)یک یال در G ، می باشد به طوری که u<v در S ، باشد . با توجه به نظریه ی König ، یک جورسازی M و یک مجموعه از رئوس C ، در G ، وجود دارد ، به طوری که هر یال در گراف شامل حداقل یک راس از C ، باشد و چنان که تعداد اعضای M و C ، برابر m ، باشد .گیریم A ، مجموعه ای از اعضای S ، باشد که به هیچ راسی از مجموعه ی C ، مرتبط نباشد ،بنابراین A ، حداقل n-m عضو دارد . گیریم P ، هم دسته ای از زنجیره هایی باشد که اگر یال (u,v) ، در جورسازی M ، باشد ، آنگاه زنجیره هایی که شامل x و y می باشد را در یک زنجیره قرار می دهد ، بنابراین P، هم شامل n-m زنجیره می باشد . پس ما یک ضد-زنجیره و یک افراز ترتیب جزیی ، به زنجیره هایی ، با تعداد یکسان داریم . به طور برعکس ، برای اثبات نظریه ی König ، از نظریه ی Dilworth ، برای یک گراف دو بخشی G = (U,V،E) ، ترتیب جزییu<v ، را روی راس های G ، طوری تشکیل می دهیم اگر u در U ، v در V و یک یال در E ، از u به v ، باشد . به دلیل نظریه ی Dilworth ،یک ضد-زنجیره ی A و یک افراز ترتیب جزیی به دسته ی زنجیره های P ، که هر دو سایز مشابه دارند وجود دارد .اما فقط زنجیره های مهم در ترتیب جزیی ، جفت اعضای مرتبط ، به یال ها در گراف می باشد .بنابراین زنجیره های مهم در P ، تشکیل یک جورسازی در گراف می دهند و مکمل A ، یک پوشش راسی در G ، با تعداد اعضای برابر با جورسازی ، تشکیل می دهد . این اتصالات در جورسازی گراف دو بخشی ، اجازه می دهد که طول هر ترتیب جزیی ، بتواند در زمان چند جمله ای محاسبه شود .

منابع[ویرایش]