Payamvdn/NorthPersian_fa_wiki huggingface dataset:
واکنش اشمیت-کولب که در شیمی آلی مورد بحث قرار می گیرد عبارت است از یک واکنش شیمیایی که طی آن نمک یک فنول با کربن دی اکسید واکنش داده و گروه کربوکسیل جانشین هیدروژن می شود. این فرایند معمولاً در فشار ۱۰۰ اتمسفر و دمای ۱۲۵ درجه سانتی گراد انجام می پذیرد و حاصل این واکنش پس از قرار گرفتن در معرض سولفوریک اسید یک هیدروکسی اسید آروماتیک خواهد بود. مهمترین کاربرد این واکنش تبدیل فنول به سالیسیلیک اسید است.
Trivial File Transfer Protocol) TFTP) یک پروتکل انتقال فایل است که به دلیل سادگی در به کارگیری، پرکاربرد شده است. این پروتکل به کاربران دسترسی برای قرار دادن یا دریافت فایل از ریموت هاست را می دهد. از عمده ترین کاربرد آن می توان به انتقال خودکار فایل های مربوط به تنظیمات یک دستگاه یا فایل های مورد نیاز یک دستگاه برای بوت شدن در یک شبکه محلی اشاره کرد. این پروتکل اولین بار در سال ۱۹۸۱ استانداردسازی شد که مشخصات فعلی این پروتکل را می توان در RFC 1350 یافت. بررسی اجمالی. تی اف تی پی دارای طراحی ساده ای است که به کارگیری آن را آسان کرده است. این پروتکل برای انتقال اطلاعات در مراحل اولیه بوت کردن از طریق شبکه مانند BOOTP ,PXE ,PSDP و… استفاده می شود. در واقع تی اف تی پی یکی از عناصر PXE یا پروتکل بوت شدن دستگاه ها از محیط شبکه است که در واقع درون بایوس کارت شبکه رایانه های میزبان، الگوریتمی برای استفاده از آن پیش بینی و نهادینه شده است. از تی اف تی پی برای انتقال دیسک ایمیج های سیستم عامل ها و پرونده های پیکربندی به روتر، آی پی های تلفن و فایروال ها نیز استفاده می شود. طراحی این پروتکل از پروتکل ای اف تی پی که بخش
ی از مجموعه پروتکل های PUP است تأثیر گرفته است. امروزه به دلیل امنیت پایین این پروتکل از آن در انتقالات فایل در اینترنت استفاده نمی شود و تقریباً تنها استفاده آن در شبکه محلی (LAN) می باشد. تی اف تی پی اولین بار در سال ۱۹۸۱ توسط IEN 133 تعریف شد. پس از آن در سال بعد در ماه ژوئن تجدیدنظر دوم این پروتکل به عنوان RFC 783 منتشر شد. بعد از آن آپدیت های مختلفی برای این پروتکل ارائه شد که آپدیت های کلی آن به ترتیب عبارتند از: پروتکل تی اف تی پی که یکی از ساده ترین پروتکل های انتقال است با استفاده از پروتکل UDP از پورت شمارهٔ ۶۹ استفاده می کند. کار با این پروتکل بسیار آسان است و از بسیاری از تنظیمات و امکانات پیشرفته ای که بسیاری از پروتکل های انتقال داده پیشنهاد می کنند مستثنا است. این پروتکل تنها برای خواندن و نوشتن اطلاعات به ریموت سرور یا از ریموت سرور طراحی شده است و نمی تواند اطلاعات را تغییر نام دهد، حذف یا لیست کند. تفاوت تی اف تی پی و اف تی پی. در مقایسه با پروتکل انتقال داده تی اف تی پی، اف تی پی بسیار ساده تر عمل می کند. به عنوان مثال در تی اف تی پی خبری از احراز هویت استفاده کننده نیست و هر کسی که دسترسی
شبکه به آن داشته باشد می تواند از آن استفاده کند درحالی که برای استفاده از اف تی پی احراز هویت اهمیت بالایی دارد. البته این موضوع امنیت تی اف تی پی را کاهش می دهد. تی اف تی پی در مقایسه با اف تی پی از سرعت بالاتری نیز برخوردار است. دلیل این موضوع این است که اف تی پی در هنگام انتقال اطلاعات نیاز به تصدیق کردن بسته فرستاده شده(Packet) دارد ولی تی اف تی پی منتظر تصدیق بسته فرستاده شده نمی ماند و فایل بعدی را ارسال می کند. در نتیجه سرعت آن بسیار بالاتر از اف تی پی است و می تواند فایل های با حجم بالایی را انتقال دهد. میزبان های تی اف تی پی. سایت های زیر نمونه هایی از تی اف تی پی سرور هستند:
مرتب سازی ادغامی دسته ای فرد–زوج معرفی. مرتب سازی ادغامی دسته ای فرد–زوج یک ساز و کار عمومی برای مرتب سازی شبکه هاست. این روش توسط کِن بچر ابداع شده است. اگر تعداد عناصری که می خواهیم مرتب کنیم n باشد اندازه (تعداد مقایسه کننده های استفاده شده) این الگوریتم nlog۲n و عمق (حداکثر تعداد مقایسه کننده هایی که در مسیر یک ورودی به خروجی قرار دارند) آن log۲n است. هرچند که مقایسه خوبی نیست اما دانلد_کنوت در سال ۱۹۹۸ به این نتیجه رسید که روش دسته ای نسبت به روش شبکه AKS بهتر است مگر اینکه n بیش از کل ظرفیت حافظه رایانه های روی زمین باشد. این الگوریتم به عنوان یکی از ساده ترین راه ها برای انجام مرتب سازی های منطقی بهینه بر روی انواع سخت افزارهای پردازش گرافیکی انجام پذیر است. نمونه کد. یک نمونه پیاده سازی از این الگوریتم به زبان پایتون در زیر آمده است. ورودی آن یک لیست x به طول توانی از ۲ است. def compare_and_swap(x، a، b): if x[a]&gt; x[b]: x[a], x[b] = x[b], x[a] def oddeven_merge(x، lo، hi، r): step = r * 2 if step &lt;hi - lo: oddeven_merge(x, lo, hi, step) oddeven_merge(x, lo + r, hi, step) for i in range(lo + r, h
i - r, step): compare_and_swap(x, i, i + r) else: compare_and_swap(x, lo, lo + r) def oddeven_merge_sort_range(x، lo، hi): """ sort the part of x with indices between lo and hi. Note: endpoints (lo and hi) are included. if (hi - lo)&gt;= 1: # if there is more than one element, split the input # down the middle and first sort the first and second # half, followed by merging them. mid = lo + ((hi - lo) / 2) oddeven_merge_sort_range(x, lo, mid) oddeven_merge_sort_range(x, mid + 1, hi) oddeven_merge(x, lo, hi, 1) def oddeven_merge_sort(x): oddeven_merge_sort_range(x, 0, len(x)-1) »&gt; data = [۴، ۳، ۵، ۶، ۱، ۷، ۸] »&gt; oddeven_merge_sort(data) »&gt; data [۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸]
قضیه پنج رنگ نتیجه ای است از نظریه گراف که صفحه ای به چند منطقه تقسیم شده داده می شود. مناطق به گونه ای به پنج رنگ مختلف رنگ آمیزی می شوند که هیچ دو منطقه مجاوری رنگ یکسان نداشته باشند. قضیه پنج رنگ از قضیه چهار رنگ می رسد اما به طور قابل توجهی اثباتش از آن ساده تر است. اثبات این قضیه بر مبنای تلاش شکست خورده ای برای اثبات قضیه چهار رنگ توسط آلفرد کمپ در سال ۱۸۷۹ می باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر مبنای کار کمپ قضیه پنج رنگ را اثبات نمود. نمای کلی اثبات توسط تناقض. در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می دهیم به این صورت که هر منطقه را متناظر با یک رأس در نظر می گیریم و بین دو رأس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد. اثبات بر مشخصه اویلر استوار است تا نشان دهد حتماً باید یک رأس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلاً می تواند در یک صفحه بدون یال های متقاطع تعبیه شود. حال V
را از G حذف می کنیم. گراف از این کار حاصل می شود که یک رأس کمتر از G دارد. پس ما می توانیم با استقرا فرض کنیم که این را می توان با پنج رنگ، رنگ آمیزی کرد. V حتماً باید به پنج رأس دیگر متصل شود؛ چون در غیر این صورت می تواند در گراف G با رنگی که در آن ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج رأس formula_1، formula_2، formula_3، formula_4، formula_5 نگاه می کنیم که در ترتیب دایره ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلماً می توانیم رأس V را به رنگی متفاوت از آن ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم. پس ما می توانیم فرض کنیم که رئوس به ترتیب رنگ های ۱ تا ۵ را گرفته اند. حال زیر گراف formula_6 از formula_7 را در نظر می گیریم که تنها از رئوسی تشکیل شده که رنگ های ۱ و ۳ را دارند و یال هایی که دو تا از این رئوس را به هم متصل می کند. اگر formula_1 و formula_3 در مؤلفه های همبندی متفاوتی از formula_6 باشند، می توانیم رنگ آمیزی مؤلفه همبندی شامل formula_1 را معکوس کنیم که بنابراین رأس V رنگ ۱ را می گیرد و کار تمام است. اما اگر f
ormula_1 و formula_3 در مؤلفه های همبندی یکسانی از formula_6 بودند، می توانیم مسیری در formula_6 که آن دو را به هم متصل می نماید پیدا نماییم که ترتیبی از یال ها و رئوس فقط رنگ شده با ۱ و ۳ باشد. حال زیر گراف formula_16 از formula_7 را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال های متصل کننده این رئوس به هم است را در نظر می گیریم و روندی مشابه قبلی برای آن اجرا می کنیم. پس یا می توانیم رنگ آمیزی زیر گراف formula_16 را برعکس نموده و رأس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، formula_2 و formula_4 را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در formula_6 تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می تواند با پنج رنگ، رنگ آمیزی شود. الگوریتم پنج رنگ کردن در زمان خطی. در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان جا، آن ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف
شده بر روی چند گراف عمل می کند و بر قابلیت داشتن چندین نسخه از یال ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می باشد که در پایین آمده است: قضیه ورنیک: فرض می کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است. ما نمایشی از این گراف را به کار می بریم که در آن هر رأس یک لیست پیوندی دایره ای از رئوس مجاور را در جهت ساعتگرد گراف مسطح نگه می دارد. در مفهوم، الگوریتم بازگشتی است؛ در هر مرحله گراف را به یک گراف با یک رأس کمتر کاهش می دهد؛ آن را پنج رنگ می کند و سپس از آن رنگ کردن استفاده می کند تا معین کند رنگ کردن گراف بزرگتر در زمان ثابتی انجام می شود. در عمل بیش از این که برای هر گراف کوچک شده، نمایش یک گراف صریح را نگه داریم، ما رئوس را از گراف حذف می کنیم و آن ها را به یک پشته اضافه می کنیم. سپس در آخر هنگامی که آن ها را از پشته خارج می کنیم، رنگشان می کنیم. ما سه تا پشته را نگه خواهیم داشت: الگوریتم به نحوه زیر کار می کند:
تحلیل سر شکن: در این نوع آنالیز، n عمل انجام می شود و هزینه زمانی آن روی n عمل سرشکن می شود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد. لازم به ذکر است که آنالیز استهلاکی با آنالیز در حالت میانگین متفاوت است و روش های آماری را شامل نمی شود. در واقع آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان می دهد. برای این نوع آنالیز 3 روش مطرح است: آنالیز تجمعی در این روش هزینه n عمل را به دست می آوریم سپس به n تقسیم می کنیم . مثلاً n عمل formula_1 روی پشته s که در ابتدا خالی است انجام داده ایم formula_2 (عنصر از پشته pop می کند، البته اگر کمتر از k عنصر در پشته باشند، همه عناصر pop می شوند) درست است که هزینه formula_2 ممکن است formula_4 باشد ولی n عمل از عملیات فوق روی هم هزینه formula_5 باشد ولی N عمل از عملیات فوق روی هم هزینه formula_5 دارند پس هزینه هر عمل به صورت سرشکن شده برابر formula_7 است. روش حسابرسی در این روش به عملیات مختلف، شارژهای مختلفی نسبت می دهیم که ممکن است شارژی که نسبت می دهیم، از هزینه واقعی عمل ک
متر یا بیشتر باشد . مقداری که یک عمل شارژ می شود را «هزینه استهلاک » آن عمل گویند. اگر « هزینه استهلاک » یک عمل از «هزینه واقعی » آن عمل بیشتر باشد، تفاوت این دو به عنوان «اعتبار» به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را می توان بعداً برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد. به عنوان مثال عملیات پشته را در نظر بگیرید . می دانیم هزینه واقعی عملیات عبارت است از : formula_8 که s تعداد عناصر موجود در پشته هنگام فراخوانی Multipop است. ولی ما هزینه استهلاکی زیر را به عملیات نسبت می دهیم : formula_9 با این مقادیر، می توان هر دنباله از عملیات را پشتیبانی کرد. هر push که انجام می شود، هزینه واقعی اش 1 است، پس از شارژ 2 مقداری آن ، 1 مقدار برای هزینه اش صرف می شود و 1 مقدار در عنصر push شده به عنوان اعتبار ذخیره می شود، پس تمام عناصری که در پشته هستند، اعتبار 1 مقداری دارند. حال اگر pop انجام شود، چون هزینه واقعی pop ، 1 است، این 1 را از اعتبار عنصری که pop می شود، دریافت می کند . پس از آنجایی که هزینه استهلاکی push ، pop و Multipop ثابت formula_10 است پس هزینه Nعمل ، for
mula_5 است. روش پتانسیل روش قبلی، اعتبار را به عنصر تخصیص می داد ولی این روش، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص می دهد. فرض کنیدformula_12 وضعیت اولیه ساختمان داده ای است که می خواهیم formula_13 عمل روی آن انجام دهیم. formula_14 هزینه واقعی عمل i ام ، formula_15 وضعیت ساختمان داده است پس از انجام عمل i ام روی formula_16 تابع پتانسیلی تعریف می کنیم به اسمformula_17 که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت می دهد: یک عدد حقیقی=formula_18 بنابراین هزینه استهلاکی formula_19 عمل i ام برابر است با : formula_20&lt;br&gt; پس کل هزینه استهلاکی برابر است با : formula_21 مثلاً فرض کنید در عملیات پشته formula_1، تابع پتانسیل formula_17 را برابر عناصر موجود در پشته فرض کنیم . در حالت پشته خالی formula_12، که حالت شروع استformula_25. از آنجایی که تعداد عناصر موجود در پشته عددی نامنفی است پس همیشه formula_26 . پس هزینه کل مستهلک شده برای formula_13 عمل با توجه به تابع formula_17، یک کران بالا برای هزینه واقعی است. حال هزینه مستهلک شده را برای formula_1 به دست می آوریم . اگر عمل formula_30ام روی پشته f
ormula_31 باشد و در حال حاضر تعداد formula_32 عنصر در پشته باشد آنگاه: formula_33 بنابراین هزینه مستهلک شده formula_31 برابر است با : formula_35 به همین ترتیب نشان دهید که هزینه مستهلک شده formula_36 برابر صفر است. پس هزینه مستهلک شده هر عمل formula_7 است. بنابراین از آنجایی که هزینه مستهلک شده کران بالای هزینه واقعی است پس هزینه واقعی formula_13 عمل برابر formula_5 است. منابع. کتاب طراحی الگوریتم- هادی یوسفی
درنظریه گراف، به مجموعه ای از یال های گراف که با هم گره ای هموند ندارند، تطابق یا مجموعه ی ناوابسته ی یال ها گفته می شود. تطابق دوبخشی حالتی ویژه از پرسمان شبکه شاره است. تعریف. در گراف داده شدهٔ G با مجموعهٔ یال ها و گره ها مشخص که می توان آن را به صورت (G(V,E نشان داد، به مجموعه ای از یال های ناهمسایه که هیج یک از دو یال آن گره هموند نداشته باشند، یک تطابق در G می گویند و آن را با M نشان می دهند. در صورتی که گرهی در یکی از دو انتهای یکی از یال ها در تطابق گراف G واقع شده باشد، به آن گره منطبق شده (یا اشباع) می گویند. در غیر این صورت، آن گره منطبق نشده است. تطابق ماکسیمال یکی از تطابق های بدست آمده برای گراف G است، با این ویژگی که اگر به آن، هر یک از یال هایی که در گراف G وجود دارد اما در تطابق M نیامده است را اضافه کنیم، گراف به وجود آمده خاصیت تطابق بودن خود را از دست می دهد؛ بنابراین چنانچه تطابق M یک زیرمجموعهٔ محض از تطابق دیگری برای گراف G نباشد، آنگاه M یک گراف تطابق ماکسیمال است. به عبارت دیگر در صورتی M می تواند یک تطابق ماکسیمال برای گراف G باشد که هر یال از گراف G، حداقل با یکی از یال های M، تقاطع
ناتهی داشته باشد (منظور از تقاطع، تنها در دو سر یک یال است) تصاویر زیر، تطابق ماکسیمال را برای ۳ گراف نشان می دهد (گراف تطابق بیشینه با رنگ قرمز نشان داده شده است). تطابق بیشینه تطابقی است که دربردارنده ی بیشترین تعداد ممکن از یال هاست؛ بنابراین ممکن است تعداد تطابقهای بیشینه برای یک گراف، بیشتر از یکی باشد. عدد تطابق گراف G، اندازهٔ تطابق بیشینه آن گراف است که با (ν(G نشان داده می شود. با توجه به تعاریف بالا برای تطابق بیشینه و ماکسیمال، می توان نتیجه گرفت که هر تطابق بیشینه، یک تطابق ماکسیمال نیز هست، اما همهٔ تطابق های ماکسیمال لزوماً تطابق بیشینه نیستند. تصاویر زیر تطابق بیشینه را برای سه گراف نشان می دهد: تطابق کامل تطابقی است که همهٔ گره های یک گراف را تطبیق می دهد. یعنی هر یک از گره ها گراف، دقیقاً با یکی از یال های تطابق برخورد می کند. در شکل های بالا، شکل (ب) یک تطابق کامل را نشان می دهد. هر تطابق کاملی، یک تطابق بیشینه و در نتیجه تطابق ماکسیمال است. همچنین تطابق کامل، همان کوچکترین مجموعهٔ پوشش یال است. پس (ν(G) ≤ ρ(G که در آن، (ν(G سایز تطابق بیشینه است که هیچ گاه بیشتر از کمترین سایز برای گراف پو
شش یال ها نیز نمی شود. تطابق نزدیک به کامل به تطابقی گفته می شود که در آن دقیقاً یک گره، مطابقت داده نشده است و این تنها زمانی اتفاق می افتد که تعداد گره ها گراف فرد باشد و تطابقی که به دنبال آن هستیم، تطابق بیشینه باشد. در شکل های بالا، شکل (ج) یک تطابق نزدیک به کامل را نشان می دهد. اگر برای همهٔ گره ها یک گراف، یک تطابق نزدیک به کامل وجود داشته باشد که تنها همان گره را در نظر نمی گیرد، به آن گراف factor-critical هم گفته می شود. در یک گراف تطابقی M: می توان ثابت کرد که یک تطابق بیشینه است اگر و تنها اگر در آن مسیر افزایشی وجود نداشته باشد (این نتیجه گیری به قضیه برژ) هم مشهور است). ویژگی ها. در هر گرافی که در آن گره ناهمبند وجود نداشته باشد، مجموع عدد تطابق و عدد پوشای یال، برابر تعداد گره ها است. چنانچه یک تطابق کامل وجود داشته باشد، عدد تطابق و عدد پوشش یال، برابر یکیدیگر و هر دو برابر V|/2| است. اگر A و B هر دو تطابق ماکسیمال باشد همواره داریم: |A| ≤ 2|B| و |B| ≤ 2|A. برای اثبات، توجه کنید که چون B تطابق است، هر یال در A می تواند حداکثر با دو یال در B همسایه باشد. همچنین با توجه به بیشینه بودن تطابق، هر ی
ال در B همسایه یک یال در A است.(این استدلال را می توان برای گراف Aهم به کار برد و به نتایج مشابه رسید). بنابراین خواهیم داشت: بنابراین: به طور خاص، نامساوی بالا نشان می دهد که هر تطابق ماکسیمال، ۲ برابر تقریبی از تطابق بیشینه و همچنین ۲ برابر تقریبی از کوچکترین تطابق ماکسیمال است. به عنوان مثال، اگر G یک مسیر با ۳ یال و۴ گره باشد، اندازهٔ کوچکترین گراف تطابق ماکسیمال ۱ است و سایز تظابق بیشینه ۲ است. چندجمله ای تطابق. تابع مولد تعداد تطابق های k یالی در یک گراف، چندجمله ای تطابق نامیده می شود. فرض کنید G گرافی است که برای آن می خواهیم تعداد تطابق ها را پیدا کنیم و "mk"، تعداد تطابق های k-یالی برای آن باشد. یکی از چندجمله ای های تطابق برای G، تابع مولد زیر است. تعریف دیگری، چندجمله ای تطابق دیگری را به صورت زیر می دهد: که در آن، n تعداد گره ها گراف است. هر یک از انواع چندجمله ای بالا، کاربردهای مخصوص به خود را دارد. برای کسب اطلاعات بیشتر در این مورد، می توانید مقالات مربوط به چندجمله ای های تطابق را مطالعه کنید. الگوریتم ها و پیچیدگی رایانشی آنها. تطابق بیشینه در گراف های دو بخشی. اغلب اوقات مسئلهٔ تطابق برای
گراف دوبخشی مطرح می شود. شاید پیدا کردن یک تطابق دو بخشی بیشینه (که اغلب به آن تطابق دو بخشی با سایز بیشینه گفته می شود) در یک گراف دو بخشی(G = (V = (X,Y),E، ساده ترین مسئله در قسمت تطابق باشد. الگوریتم مسیر افزایشی، در صورتی که بین هر گره مانند x ∈ X به هر گره مانند y مسیر اقزایشی وجود داشته باشد، آن را پیدا می کند و به تطابق اضافه می کند. از آنجا که هر یک از این مسیرهای افزایش می تواند در زمان (O(E پیدا شود، زمان اجرا برای کل این الگوریتم از مرتبهٔ (O(VE می شود. این راه حل معادل این است که یک منبع مانند s که به همهٔ گره ها در X یال دارد و همچنین یک گودال مانند t که از همهٔ گره ها در Y به آن یال وجود دارد، به گراف اضافه کنیم و سپس شار بیشینه را از s به t حساب کنیم. با این کار، همهٔ یال هایی که از X به Y جریان دارند، تطابق بیشینه را تشکیل می دهند. این الگوریتم، در الگوریتم هاپ کرافت-کارپ )، بهبود داده شده است و می تواند در زمان formula_5 اجرا شود. راه حل دیگر برای پیدا کردن تطابق بیشینه در گراف دو بخشی، بر پایهٔ الگوریتم ضرب سریع ماتریس هاست و دارای پیچیدگی زمانی formula_6 است که از نطر تئوری برای گراف هایی ک
ه تا حد امکان فشرده هستند، کارآمد تر است. اما در عمل این الگوریتم کندتر است. در گراف دوبخشی وزن دار، هر یال دارای یک وزنی است که به آن نسبت داده شده است. تطابق بیشینهٔ وزن دار برای گراف های دو بخشی، تطابق کاملی است که در آن مجموع مقادیر (وزن ها) روی یال های تطابق، بیشترین مقدار را داشته باشد. اگر گراف دو بخشی کامل نباشد، یال هایی که برای دوبخشی کامل شدن لازم است را با وزن ۰ به گراف اضافه می کنیم. پیدا کردن این تطابق به پرسمان انتساب مشهور است. این مسئله را می توان با استفاده از روش اصلاح شدهٔ یافتن کوتاه ترین مسیر در الگوریتم مسیر افزایشی، حل کرد. اگر از الگوریتم بلمن فورد استفاده کنیم، زمان اجرا، formula_7 می شود. اما چنانچه از الگوریتم دیکسترا و هیپ فیبوناتچی استفاده کنیم، زمان اجرا به formula_8 کاهش می یابد. یک الگوریتم قابل توجه بلغاری، برای حل پرسمان انتساب ارائه شده است که از نخستین الگوریتم های بهینه سازی ترکیبی بود. راه حل اصلی این الگوریتم، نیاز به زمان اجرای formula_9 دارد اما با استفاده از صف اولویت، می توان زمان اجرای آن را به formula_8 بهبود بخشید. تطابق بیشینه. یک راه حل چندجمله ای برای پیدا کرد
ن تطابق بیشینه یا تطابق با وزن بیشینه در یک گراف غیر دوبخشی وجود دارد. این روش با توجه به jack Edmonds که بنیانگذار آن بود، روش راهها، درخت ها و گل ها یا به طور مختصر الگوریتم Edmonds نامگذاری شد. این الگوریتم از یال های دو سویه استفاده می کند. این الگوریتم متعاقباً بهبود بخشیده شد تا در زمان اجرا شود که از مرتبهٔ زمان لازم برای پیدا کردن تطابق بیشینه در گراف های دو بخشی است. همچنین الگوریتم دیگری برای پیدا کردن تطابق ماکسیمال وجود دارد که بر پایهٔ ضرب سریع ماتریس هاست و به الگوریتم Mucha و Sankowski مشهور است. اجرای این الگوریتم از مرتبهٔ formula_6 زمان می برد. تطابق ماکسیمال. تطابق ماکسیمال را می توان به سادگی و با استفاده از یک الگوریتم حریصانه بدست آورد. یک تطابق بیشینه، تطابقی ماکسیمال نیز هست؛ بنابراین می توان بزرگ ترین تطابق ماکسیمال را نیز در زمان چندجمله ای پیدا کرد. با این وجود هنوز هیچ الگوریتم چندجمله ای برای پیدا کردن کوچکترین گراف تطابق ماکسیمال که بزرگ ترین تطابق بیشینه با کمترین تعداد یال ممکن است، وجود ندارد. توجه کنید که تطابق ماکسیمال با kیال، یک مجموعهٔ غالب یال ها) با k یال است. در مقابل،
اگر کوچک ترین مجموعهٔ غالب یال ها با k یال را در اختیار داشته باشیم، می توان در زمان چندجمله ای تطابق ماکسیمال با k یال را ساخت؛ بنابراین پرسمان یافتن کوچکترین گراف تطابق ماکسیمال، معادل پرسمان یافتن کوچکترین مجموعهٔ غالب یال هاست. هر دوی این مسائل بهینه سازی ان پی-سخت است. نسخه های تصمیم گیری از این مسائل، از جمله مثال های کلاسیک مسائل ان پی (کامل) هستند. هر دوی این مسائل را می توان تا جملهٔ دوم در زمان چندجمله ای تقریب زد: پیدا کردن تطابق بیشینه دلخواه به سادگی. پرسمان شمارش. پرسمان پیدا کردن تعداد تطابق های کامل برای بک گراف مسئله ای #پی-کامل است. هر چند که نظریهٔ قابل توجه Kasteleyn نشان می دهد که تعداد تطابق های بیشینه در یک گراف مسطح را می توان با استفاده از الگوریتم FKT دقیقاً در زمان چندجمله ای محاسبه کرد. همچنین یک تقریب تصادفی اما چندجمله ای برای شمارش تعداد تطابق های دوبخشی وجود دارد. نطریهٔ کونیگ نشان می دهد که در گراف های دو بخشی، تطابق بیشینه از نطر اندازه برابر با کوچکترین پوشش گره است. با توجه به نتایج این نطریه، مسئلههٔ بزرگ ترین مجموعهٔ ناوابسته و بزرگترین پوشش گره ها ممکن است در زمان چندجم
له ای برای گراف های دو بخشی حل شود. قضیه هال، توصیفی از گراف های دو بخشی که تطابق کامل دارد را فراهم می کند و همچنین قضیهٔ tutte این خصوصیات را برای گراف دلخواه بیان می کند.
الگوریتم مقیاس دهی گبو برای کوتاهترین مسیرها از یک مبدأ واحد الگوریتم مقیاس دهی ابتدا با در نظر گرفتن فقط بالاترین بیت یک مقدار ورودی مناسب (مانند وزن یال ها)، مسئله را حل می کند. سپس جواب اولیه را با نگاه کردن به دو بیت اول پالایش می کند. به همین ترتیب بیت های بیشتر و بیشتری را در نظر می گیرد و در هر بار جواب را پالایش می کند تا این که همه بیت ها در نظر گرفته شوند و جواب صحیح محاسبه شود. دراین مسئله، الگوریتم محاسبه کوتاهترین مسیرها از یک مبدأ واحد را به وسیله مقیاس دهی وزن یال ها بررسی می کنیم. گراف جهت دار formula_1 با وزن های صحیح غیر منفی formula_2 داده شده است. فرض کنید formula_3 هدف، ایجاد الگوریتمی است که در زمان formula_4 اجرا می شود. فرض می کنیم که همه راس ها از مبدأ قابل دستیابی اند. الگوریتم در نمایش دودویی وزن های یال ها، هربار یک بیت را به ترتیب با ارزش ترین بیت، وارد حل مسئله می کند. به ویژه فرض کنید formula_5، تعداد بیت ها در نمایش دودویی formula_6 باشد و برای formula_7 formula_8. به عبارت دیگر، formula_9 شکل "کوچک شده " formula_10است که به وسیله با ارزش ترین formula_11 بیت، formula_10 تولید م
ی شود. (بنابراین برای همهformula_13 داریم، formula_14. بعنوان مثال اگر formula_15 وformula_16باشد آنگاه formula_17 است. formula_18 را به عنوان وزن کوتاهترین مسیر از راس formula_19 به راس formula_20 با استفاده از تابع وزن formula_21 تعریف می کنیم؛ بنابراین برای همه formula_22 داریم formula_23. برای مبدأ formula_24الگوریتم مقیاس دهی ابتدا وزنهای کوتاهترین مسیر formula_25 را برای همه formula_26. محاسبه می کند، سپس برای همه formula_26 وformula_28. را محاسبه می کند و به همین ترتیب ادامه می دهد تا این که برای همه δ_k (u_,v)v∈V محاسبه شود. فرض می کنیم formula_29 است و خواهیم دید که محاسبه formula_30 به اندازه formula_31، و لذا کل الگوریتم به اندازه formula_32 زمان می برد. اکنون به محاسبه formula_30 از formula_41 می پردازیم. سپس ثابت کنید که برای همه formula_26 داریم formula_46 formula_49 ثابت کنید برای formula_47 و همهformula_22, formula_52 یال formula_53 یعنی مقدار وزن جدید آن یال، یک عدد صحیح غیر منفی است. formula_60 و formula_61
در ریاضیات و علوم رایانه و علم اقتصاد یک مسئله بهینه سازی، مسئله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسئله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. یک مسئله بهینه سازی با متغیرهای گسسته به عنوان یک مسئله بهینه سازی ترکیبی یا ترکیبیاتی شناخته می شوند. در یک مسئله بهینه سازی ترکیبی، ما به دنبال مجموعه ای از اشیاء از قبیل عدد صحیح، جایگشت یا گرافی می گردیم که تعداد اعضایش محدود (و یا به طور قابل شمارش نامحدود) باشند. مسئله بهینه سازی پیوسته. شکل استاندارد مسئله بهینه سازی (پیوسته) به صورت زیر است: به طوری که: طبق قرارداد، شکل استاندارد، یک مسئله به حداقل رساندن را توصیف می کند. یک مسئله به حداکثر رساندن می تواند با منفی کردن تابع هدف به دست آید. مسئله بهینه سازی ترکیبی. به طور رسمی یک بهینه سازی ترکیبی A یک چهارتایی formula_6 است به طوری که: هدف این است که برای یک نمونه formula_3، یک راه حل بهینه پیدا کنیم که یک راه حل ممکن formula_11 است با این شرط که برای هر مسئله بهینه سازی ترکیبی، یک مسئله تصمیم متناظر وجود دارد که می پرسد ببیند آیا یک راه حل ممکن بر