- +1-530-264-8006
- info@tutorsglobe.com

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

Now Priced at $70 (50% Discount)

Recommended **(92%)**

18,76,764

Questions

Asked

21,311

Experts

9,67,568

Questions

Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment
## Q : Constructing deterministic finite automata-turing machine

Construct the DFA (Deterministic Finite Automata) accepting following Set: {w ∈ {a,b}*: w has the even number of a’s and odd number of b’s}. Construct Turing Machine for the following languages: {anbncn : n > 1}.