Skip to content

Corrected the image not visible issue in 2SAT.md #1442

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 1 commit into from
Closed

Corrected the image not visible issue in 2SAT.md #1442

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
9 changes: 7 additions & 2 deletions src/graph/2SAT.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -39,7 +39,10 @@ b \Rightarrow a & \lnot b \Rightarrow \lnot a & b \Rightarrow \lnot a & c \Right

You can see the implication graph in the following image:

<center>!["Implication Graph of 2-SAT example"](2SAT.png)</center>
<p align="center">
<img src="2SAT.png" alt="Implication Graph of 2-SAT example">
</p>


It is worth paying attention to the property of the implication graph:
if there is an edge $a \Rightarrow b$, then there also is an edge $\lnot b \Rightarrow \lnot a$.
Expand All @@ -59,7 +62,9 @@ The following image shows all strongly connected components for the example.
As we can check easily, neither of the four components contain a vertex $x$ and its negation $\lnot x$, therefore the example has a solution.
We will learn in the next paragraphs how to compute a valid assignment, but just for demonstration purposes the solution $a = \text{false}$, $b = \text{false}$, $c = \text{false}$ is given.

<center>!["Strongly Connected Components of the 2-SAT example"](2SAT_SCC.png)</center>
<p align="center">
<img src="2SAT_SCC.png" alt="Strongly Connected Components of the 2-SAT example">
</p>

Now we construct the algorithm for finding the solution of the 2-SAT problem on the assumption that the solution exists.

Expand Down