مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

مقاله مقاله نشریه

مشخصات مقاله

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

نسخه انگلیسی
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

video

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

sound

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

نسخه انگلیسی

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

بازدید:

13
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

دانلود:

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

استناد:

اطلاعات مقاله نشریه

عنوان

لم بلاباس: تحلیل، کاربرد و الگوریتم

صفحات

 صفحه شروع 1 | صفحه پایان 18

چکیده

 بسیاری از قضایا یی که در دهه های 60 و 70 میلادی در ترکیبیات و نظریه ی گراف توسط پژوهشگران توسعه داده شده اند, امروزه در طراحی الگوریتم ها و حل مسائل جدید همچنان کاربرد دارد. هدف این مقاله این است که نشان دهیم چیزهای مفیدی در گذشته رخ داده است که نباید آنها را فراموش کنیم و باید با نگاهی خلاقانه از آنها استفاده کنیم. لم بلاباس, که در دهه 1970 مطرح شد یک مسئله معروف در حوزه ترکیبیات است. در این مسئله, یک خانواده از مجموعه های $A_1, A_2,\ldots,A_m$ هر کدام با اندازه $a$ و خانواده ای دیگر از مجموعه ها $B_1, B_2,\ldots,B_m$ هر کدام با اندازه $b$ داریم. هدف یافتن بیشترین مقدار $m$ از تعداد مجموعه ها است به طوری که برای هر اندیس $i$ داشته باشیم $A_i\cap B_i = \emptyset$ و همچنین $A_i\cap B_j \neq \emptyset$, برای هر $i \neq j$. لم بلاباس کران بالایی برای حداکثر تعداد این مجموعه ها به صورت $m\leq \binom{a+b}{b} $ بیان می کند. در این مقاله, پس از بیان حالات لم و اثبات موجود برای این لم, اثبات دیگری بر پایه احتمال برای لم بلاباس ارائه می دهیم و سپس با نگاهی متفاوت به این مسئله ترکیبیاتی, به بررسی کاربردهای جالب این لم در مسائل نظریه گراف و الگوریتم های پارامتری می پردازیم.

چندرسانه ای

  • ثبت نشده است.

    • استنادها

  • ثبت نشده است.

    • ارجاعات

  • ثبت نشده است.

    • استناددهی

    مقالات مرتبط نشریه ای

  • ثبت نشده است.

    • مقالات مرتبط همایشی

  • ثبت نشده است.

    • طرح های مرتبط

  • ثبت نشده است.

    • کارگاه های پیشنهادی






    بازگشت به بالا
    telegram sharing button
    whatsapp sharing button
    linkedin sharing button
    twitter sharing button
    email sharing button
    email sharing button
    email sharing button
    sharethis sharing button