[go: up one dir, main page]
Scribd
Upload
28 views2 pages

Imp. Questions

Ada imp question, gt important question ada lab program

Uploaded by

Nayana Kulkarni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
28 views2 pages

Imp. Questions

Ada imp question, gt important question ada lab program

Uploaded by

Nayana Kulkarni
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

1. Write the properties of the tree.

2. Define the fundamental circuit and fundamental cut set with examples.
3. Define edge connectivity and vertex connectivity. Give one example for each.
4. Define a tree. Prove that a tree with n vertices has (n – 1) edges.
5. Prove that a connected graph with n vertices and e edges has e - n + 2 regions.
6. Define a planar graph. Give two examples. Mention the properties of Kuratowski’s graph.
7. Prove that a graph can be embedded in the surface of a sphere if and only if it can be embedded in a plane.
8. Check whether the graph is non-planar or not. n = 5 and e = 10, Where n is the number of vertices and e is the
number of the edges.
9. Define Incidence Matrix and Circuit Matrix. Find the Incidence Matrix and Circuit Matrix for the Fig.1.
Prove that A.BT = 0 (mod2), where A is Incidence Matrix and B is the Circuit matrix.

10. State Euler’s Fundamental Theorem on planar graph. Verify the same for the following graph. Also construct
the dual for the same graph.

11. Define matching. Five students S1, S2, S3, S4, and S5 are the members of three committees C1, C2, and C3.
The committee C1 has S4 and s3 as members. the committee C2 has S1 S3 S5 as members and the committee
C3 has S2 and S5 as members. Each committee is to select a student representative. Can a selection be made
in such a way that each committee has a distinct representative?
12. Find the chromatic number of a complete bipartite graph Km,n and a complete graph of n vertices. Where n
greater than or equal to 3.
13. Define the chromatic number. Find chromatic polynomial Pn (λ) for the below graphs.
14. Prove that every tree with two or more vertices is 2-chromatic.
15. Minimize the given Boolean function using the concept of Covering.

16. Define dimer, 1-factor. Write the dimer covering for the below graph.

17. Define matching. Show that the graph has a complete matching from V1 to V2. Obtain two complete
matching.

18. Define covering. Write the two different coverings for the below graph.

You might also like