Question

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.

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.

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 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) 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 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 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) = n. Prove: d(u, v) ≥ |m − n|.

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 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 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}:
{ (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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 44 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago