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
a. Explain the sum of subset problem. Apply backtracking to solve the following instance of sum of subset problem: w= (3, 4, 5, 6} and d = 13. Briefly define the method using a sta

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know

Question 1. Explain the different types of traversal on binary tree 2. Explain the Prim's minimum spanning tree algorithm 3. Differentiate fixed and variable storage allo

After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

The controversy of RISC versus CISC never ends. Suppose that you represent an advocate for the RISC approach; write at least a one-page critic of the CISC approach showing its disa

Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays.           Circular queue:

Determine about the unreachable code assertion An unreachable code assertion is an assertion that is placed at a point in a program that shouldn't be executed under any circum

explain quick sort algorithm

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most