Width search algorithm to solve many logical equations

Question

I am trying to provide a solution for problems such as in the following example:

A != B B != C D != B C != B E != D E != A 

How many variables are true and how many are false? As far as I know, I should try to use a width search, but my task is to start with the fact that the graph will be oriented (I associate xi with !xj , where there is an equality relation). Can someone point me in the right direction?

Answer 1

This is a two-color chart problem. Vertices: A, B, C, … Edge (u, v) is present in this undirected graph if and only if u != v

2-coloring is one of the breadth-first search uses. See: http://en.wikipedia.org/wiki/Breadth-first_search#Testing_bipartiteness

Answer 2

I don’t think you need a search at all. Consider your constraints as a graph connecting the vertices xi and xj if there is a constraint xi =! Xj. Take the connected component of the graph (i.e. the one where there is a path connecting each pair of vertices). Assuming your constraints are consistent (i.e. Don't set xi = xj and xi =! Xj at the same time), you can select any vertex xi in the component and immediately find out if any sacred vertex xj xi or! Xi. Then it is easy to complete the tasks necessary to maximize or minimize the number of true variables.