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
1. Give both a high-level algorithm and an implementation (\bubble diagram") of a Turing machine for the language in Exercise 3.8 (b) on page 160. Use the ' notation to show the co

what are registers? why we need register? Definition? Types? What registers can do for us?

Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

How sparse matrix stored in the memory of a computer?

If a node in a BST has two children, then its inorder predecessor has No right child

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,

Q. Write down a non recursive algorithm to traverse a binary tree in order.                    Ans: N on - recursive algorithm to traverse a binary tree in inorder is as