1
$\begingroup$

If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John.

Would there be a way to figure out that there is a contradiction in this set of statements using graphs?

My attempt at it was to symbolize each of the names, assuming they have different first letters to statements like, J = M, M = S, C = S, C ≠ J.

My idea is to find a cycle after using DFS on some graph but I'm having trouble making the actual graph which is perhaps the most troublesome part.

I hope I'm on the right track. Any help would be much appreciated!

Edit: The comment makes a good point and the statements do have inequalities as well, but I'd like to make another attempt at that on my own afterwards. If the question were to be simplified to just "as tall" and "not as tall", what sort of graph would I make?

$\endgroup$
  • $\begingroup$ C < J instead of C $\not=$ J. $\endgroup$ – Apass.Jack Mar 20 at 3:37
  • $\begingroup$ Oops, I forgot to mention that, thanks! I've edited my post to address that. $\endgroup$ – SunnySideUp Mar 20 at 3:40
  • 1
    $\begingroup$ Have you heard of directed graph? Equivalence class? $\endgroup$ – Apass.Jack Mar 20 at 3:45
  • $\begingroup$ Unfortunately, I haven't. I did some googling just now and am a little overwhelmed as I'm unfamiliar with the strongly connected terminology as well... $\endgroup$ – SunnySideUp Mar 20 at 3:48
  • 1
    $\begingroup$ I suggest getting a good algorithms textbook and reading about strongly connected components, and algorithms for finding them. Then, work through a small example (make the graph, find the SCCs), and I think you'll discover that these concepts are exactly what you need. $\endgroup$ – D.W. Mar 20 at 5:40
1
$\begingroup$

First, you can consider only the equality relationships and build an undirected graph with each edge representing each equality relationship. Then you can simply apply BFS or DFS to partition this graph into connected components.

Next you can consider the "<" and ">" relationships. You can treat each connected component as a vertex and add directed edges so that $(u,v)$ represents the relationship $u<v$. Then you can detect if there is a cycle in the directed graph by DFS again. If there is cycle, there is a contradiction among these relationships; otherwise the relationships we processed so far are consistent.

At last you can consider the "$\neq$" relationships. You can simply check for each relationship $a\neq b$ if $a$ and $b$ belong to the same connected component. If $a$ and $b$ belong to different connected components for all relationships $a\neq b$, then all the relationships are consistent; otherwise there is a contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.