Question

Suppose that ~ is a relation defined on the vertices of a graph G. There are...

Suppose that ~ is a relation defined on the vertices of a graph G. There are three things we have to check to show that u ~ v is an equivalence relation: that it is reflexive, symmetric and transitive. Describe clearly what each one requires.

Homework Answers

Answer #1

That's easy, just an process of equivalence relation.

Have a great day!!!

Solution:

We know that v~v since we have a path from a vertex to itself (the empty path). So i t is reflexive.

Let v,u∈V. If v~u Then there is a path from vv to uu. Inversely, if you walk that path from end to start, you get a path from uu to vv, so u~v. So it is symmetric.

Now let v,u,w∈V such that there is a path from v to u and from u to w. This trivially means that there is a path from v to w. Just go to u and from there go to w. So v~w which means transitivity.

So this is a required relation.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Suppose we define the relation R on the set of all people by the rule "a...
Suppose we define the relation R on the set of all people by the rule "a R b if and only if a is Facebook friends with b." Is this relation reflexive?  Is is symmetric?   Is it transitive?   Is it an equivalence relation? Briefly but clearly justify your answers.
1. Suppose we have the following relation defined on Z. We say that a ∼ b...
1. Suppose we have the following relation defined on Z. We say that a ∼ b iff 2 divides a + b. (a) Prove that the relation ∼ defines an equivalence relation on Z. (b) Describe the equivalence classes under ∼ . 2. Suppose we have the following relation defined on Z. We say that a ' b iff 3 divides a + b. It is simple to show that that the relation ' is symmetric, so we will leave...
Define on the vertices of a graph G u ≈ v if the distance d(u, v)...
Define on the vertices of a graph G u ≈ v if the distance d(u, v) is even. Is this an equivalence relation? If you say yes than show that it satisfies all properties. If you say no than show me which ones are satisfied and which are not. Justify your answers.
Consider the following relation on the set Z: xRy ? x2 + y is even. For...
Consider the following relation on the set Z: xRy ? x2 + y is even. For each question below, if your answer is "yes", then prove it, if your answer is "no", then show a counterexample. (i) Is R reflexive? (ii) Is R symmetric? (iii) Is R antisymmetric? (iv) Is R transitive? (v) Is R an equivalence relation? If it is, then describe the equivalence classes of R. How many equivalence classes are there?
Determine the distance equivalence classes for the relation R is defined on ℤ by a R...
Determine the distance equivalence classes for the relation R is defined on ℤ by a R b if |a - 2| = |b - 2|. I had to prove it was an equivalence relation as well, but that part was not hard. Just want to know if the logic and presentation is sound for the last part: 8.48) A relation R is defined on ℤ by a R b if |a - 2| = |b - 2|. Prove that R...
Suppose u and v are two vertices in a graph G with ecc(u) = m, ecc(v)...
Suppose u and v are two vertices in a graph G with ecc(u) = m, ecc(v) = n. Prove: d(u, v) ≥ |m − n|.
Let G = (V,E) be a graph with n vertices and e edges. Show that the...
Let G = (V,E) be a graph with n vertices and e edges. Show that the following statements are equivalent: 1. G is a tree 2. G is connected and n = e + 1 3. G has no cycles and n = e + 1 4. If u and v are vertices in G, then there exists a unique path connecting u and v.
Let G be a graph with vertex set V. Define a relation R from V to...
Let G be a graph with vertex set V. Define a relation R from V to itself as follows: vertex u has this relation R with vertex v, u R v, if there is a path in G from u to v. Prove that this relation is an equivalence relation. Write your proof with complete sentences line by line in a logical order.  If you can, you may write your answer to this question directly in the space provided.Your presentation counts.
Suppose G is a simple, nonconnected graph with n vertices that is maximal with respect to...
Suppose G is a simple, nonconnected graph with n vertices that is maximal with respect to these properties. That is, if you tried to make a larger graph in which G is a subgraph, this larger graph will lose at least one of the properties (a) simple, (b) nonconnected, or (c) has n vertices. What does being maximal with respect to these properties imply about G?G? That is, what further properties must GG possess because of this assumption? In this...
Let's say we have the following relation defined on the set {0, 1, 2, 3}: {...
Let's say we have the following relation defined on the set {0, 1, 2, 3}: { (0, 0), (0, 2), (2, 0), (2, 2), (2, 3), (3, 2), (3, 3) } - Please answer the following 3 questions about this relation. (The relation will be repeated for each question.) Is this relation a function? Why or why not? - What are the three properties that must be present in an equivalence relation? Please give the names of the three properties...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT