Why Choose Us?
0% AI Guarantee
Human-written only.
24/7 Support
Anytime, anywhere.
Plagiarism Free
100% Original.
Expert Tutors
Masters & PhDs.
100% Confidential
Your privacy matters.
On-Time Delivery
Never miss a deadline.
Show that if two vertices u and v have the same score in a tournament T, then u and v belong to the same strong component of T
Show that if two vertices u and v have the same score in a tournament T, then u and v belong to the same strong component of T.
Can you explain what does score mean?
Hint : Try to prove it on two lines. Definitely your proof shouldn't be longer than 4 lines! If it is longer, you are doing something wrong.
Expert Solution
1. Oriented graph: An oriented graph is a directed graph that at most
a single edge exists between two vertices. For example, if u->v is
an edge from u and v, then the edge v->u does not exist in this
graph.
2. Complete graph: any two vertices in the graph must have an edge.
3. Tournament: Tournament is a complete oriented graph.
4. Score: In a tournament with n vertices, each vertex connects with
the other n-1 vertices. So it has k outedges and n-k-1 inedges. The
number k of outedges is called the score of this vertex.
Now we begin our proof.
u and v have the same scores in a tournament. We can assume the tournament
has n vertices and the score of u and v is k. So u and v have k outedges
and n-k-1 inedges.
To show that u and v belong to the same strong components, we only need to
show that there is a path from u to v and there is a path from v to u.
I claim that there is a path from u to v.
If the edge u->v exists, we are done. Otherwise, excluding u and v, there are
n-2 vertices. k of them are those whom u goes to, n-k-1 of them are those who
go to v. But k+(n-k-1)=n-1>n-2, so there must exists some w, such that u goes
to w and w goes to v. So we find the path u->w->v and we are done.
Similarly, there is a path from v to u.
Therefore, u and v belong to the same strong components.
Archived Solution
You have full access to this solution. To save a copy with all formatting and attachments, use the button below.
For ready-to-submit work, please order a fresh solution below.





