Questions tagged [transitivity]
The transitivity tag has no usage guidance.
13 questions
3
votes
0
answers
52
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{$...
- 124
3
votes
1
answer
278
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$...
- 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 \...
- 173
1
vote
1
answer
202
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
...
- 113
1
vote
0
answers
156
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 <...
- 187
1
vote
0
answers
56
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 ...
- 385
2
votes
1
answer
177
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 ...
- 229
0
votes
2
answers
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.
- 11
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 ...
- 319
2
votes
1
answer
69
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 ...
- 325
0
votes
1
answer
715
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.
...
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 ...
- 271
2
votes
1
answer
936
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 ...
- 2,019