Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [transitivity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
48 views

Does this endomorphism over finite automata have a name?

I found this function that can be applied onto a DFA to produce a DFA. Is there a name for it? Above: A simple DFA over the alphabet $\{0, 1\}$ Below: The resultant DFA over the alphabet $\{0\mathrm{$...
Brett Schreiber's user avatar
3 votes
1 answer
277 views

Changing a relation to become transitive

Given a binary relation $R$ on a finite set $S$, is there an efficient algorithm to transform $R$ to a transitive relation $R'$ by minimum number of addition or deletion of pairs $(x,y)$ to or from $R$...
Dandelion's user avatar
  • 287
2 votes
1 answer
50 views

Is this a valid encoding of a tree structure using set theory and a valid way to extract the leaves from it?

I'm looking to formally define a tree and then extract the leaves from it in a concise way. Does this look ok? What is the best way of doing this? $ Y = \{a,b,c,d,e,f,g\} \\ R = \{a \mapsto b, a \...
newlogic's user avatar
  • 165
1 vote
1 answer
189 views

Check if a relation is reflexive, symmetric and transitive

I want to better understand how this actually works, as my solutions are sometimes not 100% correct. I have the following relation: Check if the following relation is reflexive, symmetric, and/or ...
Prometheus's user avatar
0 votes
0 answers
141 views

Transitive reductions of transitive closure

Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure <...
Radio Controlled's user avatar
1 vote
0 answers
55 views

coloring of an interval graph with constraints

Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
Farah Mind's user avatar
2 votes
1 answer
169 views

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
Ignat Insarov's user avatar
-1 votes
1 answer
1k 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.
Luke D's user avatar
  • 1
21 votes
7 answers
6k 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 ...
James Wierzba's user avatar
2 votes
1 answer
68 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 ...
Pepper M's user avatar
  • 325
0 votes
1 answer
695 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. ...
Little Alien's user avatar
17 votes
8 answers
6k 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 ...
HugoRune's user avatar
  • 271
2 votes
1 answer
861 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 ...
G. Bach's user avatar
  • 2,019