Structures for complete undirected graphs, Data Structure & Algorithms

Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1)/2.         

Ans:

The Graphs are drawn below:

i. Graph for One vertex:-

.A

ii. Graph for Two vertices:-

939_Undirected Graphs.png

2410_Graph for 2, 3, 5 vertices.png

From the above drawn Graphs we can see

i.     When n=1,

Then number of edges becomes

=n(n-1)/2

= 1(1-1)/2

=1(0)/2

=0/2

=0

Therefore, number of edges = 0. ii.   When n=2,

Then number of edges becomes

=n(n-1)/2

=2(2-1)/2

=2(1)/2

=2/2

=1

Therefore, number of edges = 1. iii. When n=3,

Then number of edges becomes

=n(n-1)/2

 

 

=3(3-1)/2

=3(2)/2

=6/2

=3

Therefore, number of edges becomes = 3.
 iv.   When n=4,

Then number of edges

=n(n-1)/2

=4(4-1)/2

=4(3)/2

=12/2

=6

Therefore, number of edges becomes = 6.
 v. When n=5,

Then number of edges becomes

=n(n-1)/2

=5(5-1)/2

=5(4)/2

=20/2

=10

Therefore, number of edges becomes = 10.

Posted Date: 7/10/2012 4:26:42 AM | Location : United States







Related Discussions:- Structures for complete undirected graphs, Assignment Help, Ask Question on Structures for complete undirected graphs, Get Answer, Expert's Help, Structures for complete undirected graphs Discussions

Write discussion on Structures for complete undirected graphs
Your posts are moderated
Related Questions

According to this, key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record. The choice of s

. Create a decision table that describes the movement of inventory

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

Program will demonstrate deletion of an element from the linear array /* declaration of delete_list function */ voiddelete_list(list *, int); /* definition of delete_list

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.


Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

In this section, we will discuss about Sequential file organization. Sequential files have data records stored in a particular sequence. A sequentially organized file might be stor

Q. Develop a representation for a list where insertions and deletions can be done at either end. Such a structure is known as a Deque (Double ended queue). Write functions for inse