2-SAT ============ 2-SAT که مخفف 2-Satisfiability است یک مسئله منطقیست. نکته ای که وجود دارد این است که به شما یک عبارت با متغیر های منطقی داده شده و شما باید جوری متغیر ها را صفر و یک دهید که شرط برقرار شه و یا بگویید که نمی توان شراطی را برقرار کرد. این عبارت چیزی شبیه به :math:`({a_1} ∨ {b_1}) ∧ ({a_2} ∨ {b_2}) ∧ ··· ∧ ({a_m} ∨ {b_m})` است که در آن :math:`a_i` و :math:`b_i` یکی از متغیر های :math:`({x_1}, {x_2},..., {x_n})` و یا نقیض آن ها یعنی :math:`({¬x_1}, {¬x_2},..., {¬x_n})` است. الگوریتم --------- در ابتدا به ازای هر متغیر و نقیض آن یک راس در گراف می گذاریم (در مجموع 2n راس) و به ازای هر عبارت :math:`u ∨ w` یک یال جهت دار از نقیض u به w و یک یال جهت دار از نقیض w به u می گذاریم. اگر دو راس u و نقیض u در یک مولفه قویاً همبندی باشند به این معنی است که نمی توان شرایط این عبارت را برقرار کرد چرا که اگر u یک باشد آنگاه نقیض آن هم یک است و اگر u صفر باشد نقیض آن هم صفر است. با توجه به این مفهوم می توانیم با الگوریتم `کوسارا جو `_ بفهمیم که آیا در یک مولفه قویاً همبندی یک راس با نقیضش آمده یا نه. اگر نکته بالا برقرار بود یعنی می توانیم جوری متغیر ها را یک و صفر دهیم که شرایط عبارت سوال برقرار شود بنابراین در گام بعدی می خواهیم متغیر ها را یک و صفر دهیم. راس های گراف را `مرتب سازی توپولوژیک `_ می کنیم. اگر u بعد از نقیضش بیاد مقدارش رو یک و اگر u قبل از نقیضش بیاد به آن صفر می دهیم. این الگوریتم دارای اردر :math:`O(n + m)` است. کاربرد ها ----------- از کاربرد های 2-SAT می توان به تشخیص دو بخش بودن گراف کرد. به این نحو که به ازای هر راس یک متغیر در نظر می گیریم. و اگر دو راس مانند u و v به هم یال داشتند دو شرط :math:`(a_v ∨ ¬a_u) ∧ (¬a_v ∨ a_u)` را به عبارت 2-SAT اضافه می کنیم. واضح است که می توانیم با این شرط ها گراف های دو بخشی را تشخیص دهیم. به این صورت که یک بخش گراف را صفر و بخش دیگر را یک در نظر بگیریم شرط 2-SAT برقرار است بنابراین اگر به جواب برسیم یعنی گراف دو بخشی است. 3-SAT ------- مسئله سخت تری نسبت به 2-SAT، که بجای دو متغیر در هر پرانتز سه متغیر وجود دارد. این مسئله NP است و بنابراین الگوریتم مناسبی برای آن موجود نیست. گفتی است که می توان تمام K-SAT ها را به 3-SAT تبدیل کرد که در آن k از سه بزرگ تر است.