payamvha/North_RAG huggingface dataset:
مسئلهٔ پایان خوش (که توسط پل اردیش نامگذاری شده‌است، چرا که به ازدواج جورج سیکریس و استر کلاین منجر شد) گزارهٔ ذیل است: این قضیه یکی از نتایج اصلی است که منجر به ظهور نظریهٔ رمزی شد. قضیهٔ پایان خوش، با تحلیل یک حالت ساده اثبات می‌شود: اگر چهار یا تعداد بیش‌تری نقطه، رأس‌های یک بدنهٔ محدب باشند، هر چهار نقطه‌ای به این شکل می‌توانند انتخاب شوند. از طرفی دیگر، اگر مجموعهٔ نقاط به فرم یک مثلث با دو نقطه درون آن باشند، دو نقطهٔ درونی و یکی از اضلاع مثلث می‌توانند انتخاب شوند. برای توضیح مصور این اثبات، پترسون
انتخاب شوند. برای توضیح مصور این اثبات، پترسون (۲۰۰۰) را ببینید و برای بررسی دقیق‌تر این مسئله نسبت به آنچه اینجا ارائه شده‌است، موریس و سالتن (۲۰۰۰) را ببینید. تخمین اردوش-سیکریس رابطهٔ کلی بین تعداد نقاطی که در یک مجموعهٔ نقاط با موقعیت عمومی هستند و بزرگ‌ترین چندضلعی محدب آن را به‌طور دقیق بیان می‌کند. این مسئله اثبات‌نشده باقی می‌ماند، اما مرزهای دقیق کم‌تری شناخته شده‌است. چندضلعی‌های درجهٔ بالاتر. دو دانشمند به نام‌های اردوش و سیکریس این قضیه را به صورت زیر تعمیم داده‌اند: اثبات قضیه اردیش–ژکرس در
صورت زیر تعمیم داده‌اند: اثبات قضیه اردیش–ژکرس در مقاله‌ای که قضیهٔ زیردنباله‌های یکنواخت در دنباله‌های عددی را اثبات می‌کند آمده است. فرض کنید ("f"("N" کمترین مقدار "M" را نشان دهد که برای هر مجموعه از "M" نقطه در موقعیت عمومی یک "N"ضلعی محدب وجود داشته باشد. داریم: بر مبنای مقادیر مشخص ("f"("N"، یعنی برای N" = ۳, ۴, ۵"، اردوش و سیکریس در مقالهٔ اصلی خود رابطهٔ زیر را تخمین زدند: به ازای هر N" ≥ ۳" بعدها این دو نفر با زدن مثال‌های خارجی دیگر ثابت کردند که: اما بهترین کران بالا برای حالت‌هایی که N" ≥ ۷"
اما بهترین کران بالا برای حالت‌هایی که N" ≥ ۷" است، به صورت زیر است: چندضلعی‌های خالی. ممکن است سؤال پیش بیاید که آیا برای هر مجموعهٔ کافی از نقاط در موقعیت عمومی دارای یک چهارضلعی، پنج‌ضلعی و.. هست یا نه، به این معنی که نیاز به نقطه ورودی جدید نداشته باشد. راه حل اصلی مسئلهٔ پایان خوش را می‌توان طوری تطابق داد که نشان دهد به ازای هر پنج نقطه با وضعیت موقعیت عمومی در صفحه یک چهارضلعی محدب خالی وجود دارد، همان‌طور که در تصویر نشان داده شده، و به ازای هر ده نقطه با شرایط فوق یک پنج‌ضلعی محدب خالی وجود دارد.
با شرایط فوق یک پنج‌ضلعی محدب خالی وجود دارد. اگرچه مجموعه‌های بزرگ و دلخواهی از نقاط با موقعیت عمومی ممکن است وجود داشته باشند که هیچ هفت‌ضلعی خالی برای آن‌ها یافت نشود. برای مدت طولانی این سؤال که آیا شش‌ضلعی خالی وجود دارد یا نه، بدون پاسخ ماند، ولی نیکولاس (۲۰۰۷) و گرکن (۲۰۰۸) ثابت کردند که به ازای هر مجموعهٔ کافی از نقاط با موقعیت عمومی در صفحه یک شش‌ضلعی محدب خالی وجود دارد. به صورت خاص، گرکن نشان داد که تعداد نقاط مورد نیاز بیشتر از (f"(۹" نیست. ("f" در بالا تعریف شده) درحالیکه نیکولاس نشان داد این
در بالا تعریف شده) درحالیکه نیکولاس نشان داد این مقدار حداکثر به اندازهٔ (f"(۲۵" است. (Valtr(۲۰۰۶ اثبات گرکن را ساده می‌کند و نشان می‌دهد که به نقاط بیشتری از (f"(۹"، یعنی به اندازهٔ (f"(۱۵" که برابر ۳۰ نقطه می‌شود، نیاز داریم، چرا که یک مجموعه از ۲۹ نقطه در موقعیت عمومی در صفحه وجود دارد که برای آن شش‌ضلعی محدب خالی وجود ندارد. مسائل مرتبط. مسئلهٔ پیدا کردن مجموعه‌عای شامل "n" نقطه به طوری که تعداد چندضلعی‌های محدب را کمینه کند، مشابه کمینه‌کردن تعداد عبور در یک ترسیمِ خطِ مستقیمِ یک گراف کامل است. تعداد
در یک ترسیمِ خطِ مستقیمِ یک گراف کامل است. تعداد چندضلعی‌ها باید متناسب با توان چهارم "n" باشد، اما مقدار ثابت دقیقی، مشخص نیست. به‌طور سرراست می‌توان نشان داد که در فضای اقلیدسی با ابعاد بالاتر، مجموعه‌های به اندازهٔ کافی بزرگ از نقاط، یک زیرمجموعه از "k" نقطه خواهند داشت که رأس‌های یک چندبر محدب را تشکیل می‌دهند، برای هر "k" بزرگ‌تر از بُعد: این مسئله خیلی سریع از موجود بودن "k"-ضلعی محدب در مجموعه‌های نقاط مسطح به اندازهٔ کافی بزرگ پیروی می‌کند، به این صورت که مجموعه نقاط با ابعاد بالاتر را در یک شبه
صورت که مجموعه نقاط با ابعاد بالاتر را در یک شبه فضای دوبعدی اختیاری طراحی می‌کند. اما تعداد نقاط لازم برای پیدا کردن "K" نقطه در حالت محدب ممکن است در ابعاد بالاتر نسبت به حالتی که در صفحه است، کم‌تر باشد، و همچنین پیدا کردن زیرمجموعه‌هایی که محدودتر هستند، امکان‌پذیر است. به‌طور مشخص، در "d" بعد، هر d" + ۳" نقطه در موقعیت عمومی، یک زیرمجموعه از d" + ۲" نقطه دارد که رئوس یک چندبر چرخه‌ای را تشکیل می‌دهند. در حالت کلی‌تر، برای هر "d" و "k"&gt; "d"، عدد ("m"("d", "k" وجود دارد به گونه‌ای که هر مجموعه از
"k" وجود دارد به گونه‌ای که هر مجموعه از ("m"("d", "k" نقطه در موقعیت عمومی یک زیر مجموعه از "k" نقطه خواهد داشت که رئوس یک چندبر همسایگی را تشکیل می‌دهد.
در ریاضیات، حوزهٔ نظریهٔ گرافها، گراف وتری گرافی است که هر دور به طول چهار یا بیشتر از آن شامل وتر باشد. (وتر: یالی است که دو رأس نامتوالی از دور را به هم وصل می‌کند). به عبارت دیگر، هر دور القایی در گراف می‌بایست حداکثر سه رأس داشته باشد. گراف‌های وتری زیرمجموعه‌ای از گراف‌های آرمانی می‌باشند که در مدت زمانی چندجمله‌ای شناسایی می‌شوند. اگر ورودی مسایلی همچون رنگ‌آمیزی گراف، گرافی وتری باشد در مدت زمانی چندجمله‌ای حل می‌شوند. طرد آرمانی و شناسایی بهینه. formula_1 یک ترتیب طرد آرمانی از رئوس گراف است به
formula_1 یک ترتیب طرد آرمانی از رئوس گراف است به طوری‌که به ازای هر راس formula_2، زیرگراف القایی ناشی از رئوس formula_2 وهمسایه‌های آن در زیرگراف القایی ناشی از formula_4 گرافی کامل باشد. نشان دادند که یک ترتیب طرد آرمانی از گرافی وتری را می‌توان به‌طور بهینه با الگوریتمی به نام پیدا کرد. خوشه‌های فرین و رنگ‌آمیزی گراف. کاربرد دیگر ترتیب طرد آرمانی پیدا کردن خوشهٔ فرین در یک گراف وتری در مدت زمانی چندجمله‌ای است، در حالی‌که این مسئله در حالت کلی از مسائل NP-complete است. در حالت کلی یک گراف وتری تعدادی
NP-complete است. در حالت کلی یک گراف وتری تعدادی خطی خوشهٔ فرین دارد در حالی‌که این تعداد در گراف‌های دیگر می‌تواند نمایی باشد. برای بدست آوردن خوشه‌های فرین از گراف وتری، ابتدا یک ترتیب طرد آرمانی (در صورت وجود) پیدا می‌کنیم. سپس از ابتدای این ترتیب شروع کرده و به ازای هر رأس formula_2 زیرگراف القایی ناشی از این رأس و رئوس قبلی آن در ترتیب را (که تشکیل خوشه می‌دهند) را در نظر می‌گیریم. خوشهٔ با اندازهٔ بیشینه در میان این خوشه‌ها، خوشهٔ فرین خواهد بود. از آنجا که گراف وتری آرمانی است، اندازهٔ خوشهٔ فرین،
آنجا که گراف وتری آرمانی است، اندازهٔ خوشهٔ فرین، همان عدد رنگی گراف خواهد بود. گراف‌های وتری، هستند: با اعمال رنگ‌آمیزی حریصانه بر روی ترتیب معکوس طرد آرمانی می‌توان به‌طور بهینه آن را رنگ کرد. جداساز مینیمال. در هر گراف، مجموعه‌ای از رئوس است که با حذف آن‌ها گراف ناهمبند می‌شود. جداساز مینیمال است اگر هیچ زیرمجموعهٔ محضی از آن این ویژگی را نداشته باشد. برطبق قضیهٔ در گراف‌های وتری، هر جداساز مینیمال یک خوشه است. Dirac با این ویژگی آرمانی بودن گراف‌های وتری را اثبات کرد. گراف‌های وتری به‌طور استقرایی توسط
را اثبات کرد. گراف‌های وتری به‌طور استقرایی توسط گراف‌هایی تعریف می‌شوند که رئوس آن‌ها به سه زیرمجموعهٔ ناتهی formula_6 افراز شوند، به طوری‌که formula_7 و formula_8 هردو تشکیل یک زیرگراف القایی وتری دهند، formula_9 خوشه باشد و هیچ یالی بین formula_10 و formula_11 نباشد. گراف تقاطع زیردرخت‌ها. ویژگی دیگر گراف‌های وتری مربوط به درخت و زیردرخت‌ها است. در یک درخت گراف تقاطع آن این گونه ساخته می‌شود: به ازای هر زیر درخت آن یک رأس در نظر می‌گیریم. دو رأس از این گراف مجاورند اگر زیردرخت متناظر آن‌ها در حداقل یک
گراف مجاورند اگر زیردرخت متناظر آن‌ها در حداقل یک رأس مشترک باشند. نشان داد که این گراف، گرافی وتری است. نمایش گراف وتری به صورت تقاطع زیردرخت‌ها، یک درخت تفکیک با پهنا درخت یکی کمتر از بزرگترین خوشهٔ گراف بدست می‌دهد. درخت تفکیک هر گراف را می‌توان به صورت نمایش زیرگرافی از گراف وتری در نظر گرفت. درخت تفکیک، همان درخت اتصال در است. مکمل وتری و پهنا درخت. "مکمل وتری" گراف دلخواه formula_12، گرافی وتری است که formula_12 زیرگراف آن باشد. اگر formula_14 "مکمل وتری" گراف formula_12 با عدد خوشه‌ای (تعداد رئوس
وتری" گراف formula_12 با عدد خوشه‌ای (تعداد رئوس خوشهٔ بیشینه گراف) کمینه باشد، در آن صورت پهنادرخت formula_12 یکی کمتر از عدد خوشه‌ای formula_14 است. " k-درخت" گرافی است که افزودن یک یال به آن، پهنادرخت آن را بزرگتر از k می‌کند. بنابراین " k-درخت" مکمل وتری خودش است و رده‌ای از گراف‌های وتری را تشکیل می‌دهد.
ساموئل ماریل وودبریج (زاده ۵ آوریل ۱۸۱۹ و در گذشته ۲۳ ژوئن ۱۹۰۵ میلادی) روحانی، کشیش و استاد دانشگاه اهل آمریکا بود. وی اهل گرینفیلد، ماساچوست بود. ساموئل ماریل وودبریج از دانش‌آموختگان دانشگاه نیویورک بود و در دانشگاه راتگرز تدریس می‌کرد.
درخت تِنِرِه ، ، یک درخت تنهای آکاسیا (سَمُر) یا آکاسیای چتری بود که روزگاری به عنوان تنهاترین و دورافتاده‌ترین درخت جهان به حساب می‌آمد. (نزدیک‌ترین درخت، حدود ۴۰۰ کیلومتر از آن فاصله داشت) مکان این درخت در روزگاران پیش، محل توقف کاروان‌های عازم منطقه تنره در صحرای بزرگ آفریقا در شمال‌شرقی نیجر بود. این درخت و درخت "آربر پِردو" (درخت گم‌شده) تنها درختانی هستند که در نقشه‌ای با مقیاس ۱:۴۰۰٬۰۰۰ دیده می‌شوند. این درخت در سال ۱۹۷۳ توسط یک رانندهٔ کامیون احتمالاً مست زیر گرفته شد و از بین رفت. تاریخچه. درخت
مست زیر گرفته شد و از بین رفت. تاریخچه. درخت تنره، آخرین درخت از درختانی بود که روزگاری که هنوز صحرا چون امروز نبود در مکان فعلی قرار داشتند. در طول زمستان ۱۹۳۸–۱۹۳۹، چاهی در کنار این درخت حفر شد و متوجه شدند که ریشه‌های این درخت تا عمق ۳۳–۳۶ متری (۱۰۸ تا ۱۱۸ فوت) پیش رفته و به داخل سطح ایستابی رسیده‌است. در کتاب L'épopée du Ténéré، هنری لوت، نژادشناس و جهانگرد فرانسوی، به شرح دو دیدار خود از درخت تنره پرداخته‌است. او ابتدا در سال ۱۹۳۴ به‌طور تصادفی در سفر خود با اتومبیل از جانت به اغادیز، درخت تنره را دید
با اتومبیل از جانت به اغادیز، درخت تنره را دید و آنرا "یک درخت آکاسیا با بدنی پوسیده که مریض به نظر می‌آید اما با این حال برگ‌های سبز زیبا و گل‌های زرد دارد" توصیف کرد. او ۲۵ سال بعد در ۲۶ نوامبر ۱۹۵۹ در طی عملیات برلیت-تنره از درخت تنره دوباره بازدید کرد اما درخت را از برخورد یک ماشین بسیار آسیب‌دیده یافت. مرگ. گفته می‌شود که درخت تنره در سال ۱۹۷۳ توسط یک راننده کامیون مست لیبیایی سرنگون شد. در ۸ نوامبر ۱۹۷۳، درخت مرده را به "موزه ملی نیجر" در نیامی منتقل کردند و به جای آن یک میله فلزی به عنوان یادبود
کردند و به جای آن یک میله فلزی به عنوان یادبود قرار دادند.
الگوریتمی که پوش محدب اشیای مختلف را به دست می‌دهد کاربردهای وسیعی در ریاضیات و علوم کامپیوتر دارد. در هندسه محاسباتی، الگوریتم‌های متعددی با پیچیدگی‌های محاسباتی گوناگون برای محاسبه پوش محدب مجموعه‌ای محدود از نقاط مطرح شده‌است. محاسبه پوش محدب به معنی ارائه نمایشی نامبهم و کارا از شکل مطلوب می‌باشد. پیچیدگیهای الگوریتم‌های مربوطه معمولاً بر حسب n، تعداد نقاط ورودی، و h، تعداد نقاط درون پوش محدب، سنجیده می‌شوند. حالت دو بعدی. اگر همهٔ نقاط روی یک صفحه نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که
نباشند آنگاه پوش محدب حاصلچندظلعی محدبی می‌شود که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. معمولترین نمایش پوشه محدب به صورت لیستی از رأس‌های آن می‌باشد که ترتیب آن بر اساس پیمایشی ساعتگرد یا پادساعتگرد بر روی مرز پوش محدب می‌باشد. در بعضی از کاربردها نمایش این چندظلعی محدب به صورت اشتراک تعدادی نیم صفحه مناسب تر می‌باشد. کران پایین پیچیدگی محاسباتی. کران پایین محاسباتی برای پیدا کردن پوش محدب و نمایش آن به صورت چند ضلعی محدب، مشابه این کران برای مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را
مرتب‌سازی می‌باشد و به سادگی می‌توان این مطلب را با کاهش نشان داد. برای نقاط formula_1 که می‌خواهیم مرتب کنیم، نقاط formula_2 را بر روی صفحه در نظر بگیرید. حال چون این نقاط بر روی سهمی که منحنی محدب است قرار دارند به راحتی می‌توان دید که پیمایش بر روی مرز پوش محدب آن‌ها ترتیب مرتب شدهٔ این اعداد را می‌دهد. به وضوح زمان خطی برای تبدیل اعداد به نقاط و سپس به دست آوردن ترتیب مرتب شده، نیاز می‌باشد. از این رو به دست آوردن پوش محدب n نقطه نمی‌تواند سریعتر از مرتبسازی عمل کند. کران پایین محاسباتی استاندارد به
عمل کند. کران پایین محاسباتی استاندارد به کمک مدل درخت تصمیمformula_3 می‌باشد که البته در این مدل تنها مقایسه انجام می‌شود و نه عملیات محاسباتی. به هر حال پوش محدب در این مدل نمی‌تواند محاسبه شود. مرتب‌سازی در مدلدرخت تصمیم جبری نیز از formula_3 می‌باشد که این مدل برای پوش محدب مناسبتر می‌باشد که در این مدل نیز به دست آوردن پوش محدب‌ها زمانی از formula_3 می‌خواهد. هر چند در مدل‌هایی که اجازه می‌دهند که اعداد سریعتر از formula_6 مرتب شودند، برای نمونه الگوریتم هایinteger sorting، پوش محدب نیز می‌تواند
هایinteger sorting، پوش محدب نیز می‌تواند سریعتر محاسبه شود: الگوریتم پیمایش گراهام شامل یک مرحله سادهٔ مرتب‌سازی است که به دنبال مقداری کار اضافه که در زمان خطی انجام می‌شوند امده‌اند. الگوریتم حساس به خروجی بهینه. همان که در بالا ذکر شد پیچیدگی پیدا کردن پوش محدب به صورت تابعی از تعداد نقاط ورودی formula_3 می‌باشد. هر چند که پیچیدگی بعضی از الگوریتم‌های پوش محدب بر حسب سایز ورودی n و سایز خروجی h (تعداد نقاط روی پوش محدب) عنوان می‌شود. این گونه الگورتم‌ها حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها
حساس به خروجی نامیده می‌شوند. این الگوریتم‌ها ممکن است به‌طور مجانبی کارا تر از formula_3 باشند در حالتی که formula_9 کران پایین در بدترین حالت زمانی الگوریتم‌های مربوط به پوش محدب حساس به خروجی در حالت دوبعدی formula_3می‌باشد.الگوریتم‌های متعددی وجود دارند که این پیچیدگی بهینه را به دست می‌دهند. اولین آن‌ها در سال ۱۹۸۶ توسط Kirkpatrick و Seidel معرفی شد (که آن را الگوریتم نهایی پوش محدب نامیدند.)الگوریتم ساده‌تر توسط Chan در ۱۹۹۶ داده شد که الگوریتم چان نامیده شد. الگوریتم‌ها. الگوریتم‌های شناخته شدهٔ
نامیده شد. الگوریتم‌ها. الگوریتم‌های شناخته شدهٔ مربوط به پوش محدب در زیر لیست شده‌اند که آن‌ها را بر اساس اولین تاریخ انتشار مرتب کرده‌ایم. پیچیدگی زمانی این الگوریتم‌ها بر اساس تعداد نقاط ورودی n و تعداد نقاط روی پوش محدب h بیان شده‌اند. توجه شود که در بدترین حالت h ممکن است به بزرگی n باشد. یکی از ساده‌ترین (اگر چه مؤثرترین در بدترین حالت نمی‌باشد) الگوریتم‌های صفحه‌ای می‌باشد که به‌طور مستقل توسط Chand و Kapur در ۱۹۹۰ و R.A.Jarvis در ۱۹۷۳ کشف شد. این الگوریتم دارای پیچیدگی زمانی formula_11 می‌باشد و در
دارای پیچیدگی زمانی formula_11 می‌باشد و در بدترین حالت این پیچیدگی از مرتبه formula_12 است. یک الگوریتم با کمی پیچیدگی بیشتر ولی کاراتر که در سال ۱۹۷۲ توسط رونالد گراهام انتشار یافت. اگر نقاط قبلاً بر اساس یکی از مؤلفه‌های مختصاتشان یا بر اساس زاویه با برداری ثابت مرتب شده باشند آنگاه این الگوریتم از formula_13 می‌باشد. به‌طور مستقل توسط W.Eddy در ۱۹۷۷ و A.Bykat در ۱۹۷۸ کشف شد. درست مانند مرتب‌سازی سریع به‌طور میانگین ازformula_14 است ولی ممکن است در بدترین حالت به formula_15 برسد. الگوریتم دیگری از
بدترین حالت به formula_15 برسد. الگوریتم دیگری از formula_6 که در سال ۱۹۷۷ توسطPreparata و Hong انتشار یافت. این اگوریتم برای حالت سه بعدی نیز قابل اجرا می‌باشد. در سال ۱۹۷۹ توسط A.M.Andrew انتشار یافت. به این الگوریتم می‌توان به دید تغییر شکل یافتهٔ Graham scan نگاه کرد که در آن نقاط بر اساس مؤلفه هایشان مرتب می‌شوند. اگر نقاط ورودی از قبل مرتب شده باشند این الگوریتم از formula_13 خواهد بود. منشتر شده در سال ۱۹۸۴ توسط Michael Kallay. اولین الگوریتم بهینه حساس به خروجی که در آن از تکنیک
الگوریتم بهینه حساس به خروجی که در آن از تکنیک marriage-before-conquest استفاده می‌شود. در سال ۱۹۸۶ توسطKirkpatrick و Seidel انتشار یافت. الگوریتم بهینه و ساده‌تر حساس به خروجی که در سال ۱۹۹۶ توسط Chan کشف شد. الگوریتم ابتکاری (heuristic) Alk-Toussaint. ابتکار ساده‌ای که در ادامهٔ کار می‌آید اغلب اولین مرحله در پیاده‌سازی الگوریتم پوش محدب برای بهبود کارایی آن می‌باشد. پایهٔ آن بر اساس اگوریتمی کارا که در سال ۱۹۷۸ توسطSelim Akl و G.T.Toussaint ارائه شد. ایدهٔ کار به این صورت است که به‌طور سریع نقاطی که به
کار به این صورت است که به‌طور سریع نقاطی که به هیچ وجه نمی‌توانند در پوش محدب باشند را حذف کنیم. این روش بر مبنای آن است که در ادامه می‌آید. دو نقطه‌ای را که دارای کمترین و بیشترین مختصات x می‌باشند و به همین ترتیب دو نقطه‌ای که دارای کمترین و بیشترین مختصات y اند را پیدا می‌کنیم.(این کار در formula_13 انجام می‌شود.)این چهار نقطه تشکیل یک چهار ظلعی محدب را می‌دهند و تمام نقاطی که در این چهار ظلعی قرار می‌گیرند (غیر از چهار نقطهٔ ابتدایی) نمی‌توانند درون پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این
پوش محدب باشند. پیدا کردن تمامی نقاطی که درون این چهار ظلعی قرار می‌گیرند نیز formula_13 هزینه می‌برد، پس در کل تا اینجا از formula_13 هزینه کرده‌ایم. به‌طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می‌توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می‌توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع‌های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش
چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می‌شود که الگوریتمی که اجرا می‌شود دارای پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از formula_23 باشد. مسئله پوش محدب برخط و داینامیک. در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده‌است. اما ممکن است کسی به این دو حالت بپردازد. درج یک نقطه به تعداد ضلع‌های پوش محدب حداکثر یک واحد اضافه می‌کند در حالی که عمل حذف می‌تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند. در نوع برخط با اضافه شدن هر
n-۱ راسی تبدیل کند. در نوع برخط با اضافه شدن هر نقطهformula_24 هزینه شده که به‌طور مجانبی بهینه است. در نوع داینامیک هر عملیات درformula_25 انجام می‌شود. به دست آوردن پوش محدب چندضلعی ساده. McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس‌های را درformula_13) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می‌باشد و ما آن را با formula_27 مشخص می‌کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می‌کنیم. در هر مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول
مرحله به سه راس متوالی نگاه می‌کنیم که دو تای اول به عنوان رأس‌های موقت پوش اختصاص داده شده‌اند و راس سوم هنوز پردازش نشده‌است که ما آن‌ها را به صورتformula_28 مشخص می‌کنیم. اگر زاویهٔ بین آن‌ها محدب بود انگاه formula_29 و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می‌کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی(formula_30) پاک شده و این تست برای سه تایی formula_31 تا تکرار می‌کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود
نقطهٔ بعدی به سه تایی برای تست شدن اضافه می‌شود و این روند تکرار می‌شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته‌اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می‌باشد. خوشبختانه، این مورد نیز به صورت کارا مدیریت می‌شود. بعداً Tor و Middleditch و به صورت مستقل Melkman رویکردی ساده‌تر با پیچیدگی زمانی یکسان ارائه کردند. بعدهای بالاتر. شماری از الگوریتم‌ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید
وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html برای مجموعه‌ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می‌باشد یا به‌طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس‌های آن زیر مجموعه‌ای از رأس‌های ورودی می‌باشد. نمایش آن به سادگی نمایش در بعد نمی‌باشد. در بعدهای بالاتر حتی اگر رأس‌های این چند وجهی معلوم باشند. ساختن وجههای آن کاری بدیهی نیست. همچنین دوگان این مسئله نیز این چنین است یعنی
همچنین دوگان این مسئله نیز این چنین است یعنی پیدا کردن رأس‌ها از روی وجه‌ها. سایز خروجی می‌تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم‌های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.
در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می‌کند که یال‌های هر گراف ساده را می‌توان با حداکثر یکی بیشتر از بیشترین درجه رئوس گراف رنگ کرد. همواره حداقل رنگ لازم است، بنابراین گراف‌های ساده را می‌توان به دو رده افراز کرد: گراف‌های «ردهٔ اول» آنهایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها کافی است و گراف‌های «ردهٔ دوم» آن‌هایی هستند که رنگ، برای رنگ‌آمیزی آن‌ها لازم است. مثال‌ها. هنگامی که است، گراف خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی
است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف‌های با جزء گرافهای ردهٔ اول هستند. هنگامی که است، گراف اجتماع مجموعه‌های مجزای مسیرها و دورها است. اگر همهٔ دورها زوج باشند، آن‌ها می‌توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. هر چند، اگر حداقل یک دور فرد وجود داشته باشد، هیچ ۲-رنگ آمیزی یالی ممکن نیست. پس، یک گراف با جزء گراف‌های ردهٔ اول است اگر و تنها اگر دوبخشی باشد. قضیهٔ ویزینگ در حالت کلی برای گراف‌های چندگانه برقرار نمی‌باشد. برای مثال، گراف چندگانهٔ
چندگانه برقرار نمی‌باشد. برای مثال، گراف چندگانهٔ حاصل از مضاعف کردن هر یال یک مثلث، بیشینه درجهٔ چهار دارد اما نمی‌توان آن را با کمتر از شش رنگ، رنگ‌آمیزی کرد. رده‌بندی گراف‌ها. چندین نویسنده شرایطی را برای رده‌بندی برخی گراف‌ها به ردهٔ اول یا ردهٔ دوم ارائه کرده‌اند اما رده‌بندی کاملی ارائه نشده‌است. برای مثال اگر مجموعهٔ رئوس با بیشینه درجهٔ در گراف یک مجموعه مستقل باشد، یا به‌طور کلی‌تر زیرگراف القایی این رئوس یک جنگل باشد، آنگاه باید جزء گراف‌های ردهٔ اول باشد. اردوش و ویلسون (۱۹۷۷) نشان دادند که
اول باشد. اردوش و ویلسون (۱۹۷۷) نشان دادند که تقریباً همهی گراف‌ها جزء ردهٔ اول هستند. پس، در مدل اردوش-رنیِ گراف‌های تصادفی، که تقریباً تمام گراف‌های -راسی برابر هستند، را احتمال کشیده شدن یک گراف -راسی از توزیع گراف‌های ردهٔ اول تعریف می‌کنیم، در نتیجه اگر به بینهایت میل کند به یک نزدیک می‌شود. برای حدود بهتری که به یک همگرا باشد، به رجوع شود. گراف‌های مسطح. ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف‌های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر
هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف‌های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گراف‌های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می‌توانند ساخته شوند. در حدس گراف‌های مسطح ویزینگ، ویزینگ (۱۹۶۵) بیان می‌کند که گراف‌های سادهٔ مسطح که بیشترین درجهٔ رئوس آن‌ها شش یا هفت است، جزء گراف‌های ردهٔ اول هستند، و این موارد ممکن باقی‌مانده را تمام می‌کند. سندرز و ژاو (۱۹۶۵)
باقی‌مانده را تمام می‌کند. سندرز و ژاو (۱۹۶۵) با نشان دادن ردهٔ اول بودن تمام گراف‌های مسطح با بیشترین درجهٔ رئوس هفت، تقریباً حدس گراف‌های مسطح ویزینگ را اثبات کردند. بنابراین، تنها حالت حدس که حل نشده باقی‌مانده این است که بیشترین درجه، شش باشد. این حدس شامل دلایلی برای حدس رنگ‌آمیزی کامل گراف است. گراف‌های مسطح ردهٔ دوم که با زیربخش‌های اجسام افلاطونی ساخته می‌شوند منظم نیستند: آن‌ها رئوس درجهٔ دو دارند همانطور که رئوس با درجهٔ بالاتر دارند. قضیه چهاررنگ، روی رنگ‌آمیزی راسی گراف‌های مسطح، معادل این
روی رنگ‌آمیزی راسی گراف‌های مسطح، معادل این گزاره است که هر گراف ۳-منظمِ مسطحِ بدون یال برشی جزء گراف‌های ردهٔ اول هستند (تایت ۱۸۸۰). این گزاره بعد از اثبات قضیه چهار رنگ توسط اپل و هاکن (۱۹۷۶) درست شناخته شد. گراف‌های روی رویه‌های غیرمسطح. در سال ۱۹۶۹، برانکو گرانبام حدس زد که تمام گراف‌های ۳-منظم با برازش چندوجهی روی هر خمینهٔ جهت‌دار دو بعدی مانند چنبره، باید جزو گراف‌های ردهٔ اول باشد. در این زمینه، برازش چندوجهی یک برازش گراف است که در آن هر ناحیه از برازش از نظر توپولوژیکی یک دیسک است و به طوری که
برازش از نظر توپولوژیکی یک دیسک است و به طوری که گرافِ دوگانِ برازش ساده است، بدون حلقه و یال چندگانه. در صورت درست بودن، این حدس یک تعمیم قضیهٔ چهار رنگ است که توسط تایت، نشان داده شد معادل این گزاره است که گراف‌های ۳-منظم با برازش چندوجهی روی یک کره، جزء رده اول هستند. اگرچه کُچُل (۲۰۰۹) نشان داد که حدس غلط است اگر اسنارکی که دارای برازش چندوجهی بر روی رویهٔ جهت‌دار بالادسته وجود داشته باشد. بر این اساس، او همچنان نشان داده است که دانستن اینکه برازش چندوجهی جزو گراف‌ها ردهٔ اول است، ان‌پی کامل است.
چندوجهی جزو گراف‌ها ردهٔ اول است، ان‌پی کامل است. الگوریتم‌ها. میسرا و گرایز (۱۹۹۲) یک الگوریتم با زمان چندجمله‌ای برای رنگ‌آمیزی هر گراف با رنگ ارائه کردند، که بیشینه درجهٔ گراف است. پس، الگوریتم برای گراف‌های ردهٔ دوم از تعداد رنگ‌های بهینه استفاده می‌کند، و حداکثر یکی بیشتر از تعداد رنگ‌های مورد نیاز برای همهٔ گراف‌ها. الگوریتم آن‌ها از روشی یکسان با اثبات اصلی ویزینگ برای قضیه‌اش پیروی می‌کند: این الگوریتم از یک گراف رنگ نشده شروع می‌کند، و سپس به‌طور مکرر راهی را برای رنگ‌آمیزی دوباره گراف پیدا می‌کند
راهی را برای رنگ‌آمیزی دوباره گراف پیدا می‌کند تا تعداد یال‌های رنگ شده را یک عدد افزایش دهد. به‌طور خاص‌تر، فرض کنید که یک یال رنگ نشده در یک گراف نیمه رنگ شده باشد. الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل جهت‌دار (یک گراف که هر رأس آن حداکثر یک یال خارج‌شونده دارد.) روی همسایه‌های تفسیر شود: برای هر همسایهٔ از ، الگوریتم یک رنگ را می‌یابد که توسط هیچ یک از یال‌های مجاور استفاده نشده‌است، رأس را می‌یابد (در صورت وجود) که یال رنگ را دارد و را به عنوان یک یال به اضافه می‌کند. دو حالت وجود
را به عنوان یک یال به اضافه می‌کند. دو حالت وجود دارد: با برخی از ساختمان داده‌های ساده برای پیگیری رنگ‌هایی استفاده شده و قابل استفاده در هر رأس، می‌توان ساختن و گام‌های رنگ‌آمیزی دوباره الگوریتم را با زمان پیاده‌سازی کرد، که تعداد رئوس گراف ورودی است. چون در هر تکرار این گام‌ها تعداد یال‌های رنگ شده یکی افزایش می‌یابد، باید این گام‌ها را بار تکرار کرد، پس زمان مجموع برابر است با . در یک گزارش فنی منتشر نشده، گابو و همکاران (۱۹۸۵) ادعای ارائهٔ یک محدودیت زمانی formula_1 سریع‌تر را برای مسئلهٔ رنگ‌آمیزی
زمانی formula_1 سریع‌تر را برای مسئلهٔ رنگ‌آمیزی یکسان با رنگ را کردند. تاریخچه. در هر دو گوتین و تافت (۲۰۰۰) و سافیر (۲۰۰۸)، ویزینگ اشاره کرد که کارش انگیخته شده توسط یکی از قضایای شانون (۱۹۴۹) است که نشان می‌دهد گراف‌های چندگانه می‌توانند با حداکثر رنگ، رنگ‌آمیزی شوند. هر چند حالا قضیه ویزینگ جزء مواد استاندارد بسیاری از کتاب‌های نظریه گراف است، ویزینگ در ابتدا برای انتشار نتایجش مشکل داشت، و مقاله‌اش در یک مجلهٔ گمنام به نام Diskret. Analiz. چاپ شد.