Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [transitivity]

The tag has no usage guidance.

-1
votes
1answer
29 views

Can someone point out why these directed graphs aren't equivalence relations?

As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
21
votes
6answers
5k views

in O(n) time: Find greatest element in set where comparison is not transitive

Title states the question. We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal. Key points: Comparison is not transitive (think rock ...
3
votes
1answer
60 views

Algorithm for getting symetric vertex sets of undirected graph

For my application problem, I am searching for an algorithm that can find all symmetric vertex sets of an undirected labeled graph. My definition of symmetric vertex set is: Let $G$ be a graph with ...
0
votes
1answer
191 views

Reflexive transitive closure = (zero or more) Kleene star?

In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position. ...
14
votes
4answers
3k views

Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm generally ...
1
vote
1answer
142 views

Simplest way to check edge set for transitivity

I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can ...