Euler graph and kruskals algorithm

Question 1:

a) Define Euler line and Euler graph with two examples?
b) A connected graph G is an Euler graph if and only if all vertices of G are of even degree.

Question 2: Define the terms multigraph and simple graph. Differentiate between them with the help of example.

Question 3:

a) Prove that Petersen graph is neither Eulerian nor Semi Eulerian.
b) Prove that connected graph is Semi-Eulerian if and only if its has actually 0 or 2 vertices of add degree.

Question 4: Define the term simple graph. Prove that a simple graph with n position and k components can have at most (n-k)(n-k+1)/2 lines?

Question 5:

a) Define chromatic number of a graph and prove that every tree with 2 or more vertices is 2-chromatic?
b) Define covering  proving that covering of graph is minimal if graph comprises of no path of length 3 or more?

Question 6:

a) Prove: In any nondirected graph there is an even no of vertices of odd order.
b) Is there a simple graph with degree sequence (1,1,3,3,3,4,6,7)? Give reason?

Question 7:

a) Define simple graph, connected graph, degree of a vertex and minimal cut of a graph.
b) show that the maximum no of edges in a simple graph of n vertices is = n(n-1)/2

Question 8:

a) Describe the terms: Cycle, tree, forest and spanning tree.
b) State and explain Kruskals algorithm

Solution Preview :

Prepared by a verified Expert
Theory of Computation: Euler graph and kruskals algorithm
Reference No:- TGS03284

Now Priced at $70 (50% Discount)

Recommended (92%)

Rated (4.4/5)

2015 ©TutorsGlobe All rights reserved. TutorsGlobe Rated 4.8/5 based on 34139 reviews.