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
Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse

Program: Creation of a linked list In the next example, wewill look to the process of addition of new nodes to the list with the function create_list(). #include #includ

Triangular Matrices Tiangular Matrices is of 2 types: a)  Lower triangular b)  Upper triangular

This unit dealt along with the methods of physically storing data in the files. The terms fields, records & files were described. The organization types were introduced. The sev

By taking an appropriate example explain how a general tree can be represented as a Binary Tree.                                                                    C onversio

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Write the algorithm for Binary search. Also apply this algorithm on the following data. 22, 44, 11, 88, 33, 55, 77, 66

extra key inserted at end of array is called