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
Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Define tractable and intractable problems Problems that can be solved in polynomial time are known as tractable problems, problems that cannot be solved in polynomial time are

Binary: Each node has one, zero, or two children. This assertion creates many tree operations efficient and simple. Binary Search : A binary tree where each and every left

Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?