My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
Fresher Jobs
Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian
cities including Bangalore, Chennai, Hyderabad, Pune or Kochi
Resources
Find educational articles, blogs, discussion threads and other resources.
Colleges
Find details about any college in India or search for courses.
|
Graph Theory
Posted Date: 30 Jan 2008 Resource Type: Articles/Knowledge Sharing Category: General
|
Posted By: satish Member Level: Gold
Rating:  Points: 4
|
|
|
Graph Theory (MA 601)
Tutorial Sheet – 2
1. Give an example of a graph:
(a) Which is regular, connected on six vertices that is not complete.
(b) On five vertices with exactly two components.
(c) That is regular, but not complete, with each vertex having degree three.
2. For each of the following sequences of vertices, state whether or not it represents a
walk, trail, path, closed walk, closed trail, or cycle in the graph illustrated.
(i) abcefcbd (ii) abcefcd
(iii) abcefcdba (iv) bcefcdb
(v) bcdb (vi) abefcd
3. For the above graph, count the total number of paths of length 3 or less than 3 from the vertex b to the vertex d.
4. For what values of n is the graph Eulerian?
5.
6. Determine the values of m and n such that is Eulerian.
7. Prove or disprove:
a. Every Eulerian bipartite graph has an even number of edges.
b. Every Eulerian Simple Graph with an even number of vertices has an even number of edges.
8. Give an example of the connected graph that has
i. Neither an Euler circuit nor a Hamiltonian Cycle.
ii. An Euler circuit but no Hamiltonian cycle.
iii. A Hamiltonian Cycle but no Euler Circuit.
iv. Both a Hamiltonian Cycle and Euler Circuit.
9. Give an example of a graph that has an Euler circuit and Hamiltonian circuit that are not the same.
10. How many vertices and how many edges do these graphs have?
11. Prove that , for , has (n-1)! Hamiltonian circuits.
12. Use Fleury’s Algorithm to produce an Euler circuit for the graph:
13. Use the first form of Dijkstra’s algorithm to find the shortest path from A to E (and its length) in the graph (a) shown.
(a) (b)
14. Suppose that the Floyd – Warshall algorithm is applied to the graph G given below (with vertices A, B, …,J relabeled respectively).
Graph G Graph H
(a) What are the final values of d(1,1), d(1,2),…,d(1,10)?
(b) Find the values of d(1,5), d(1,6), d(3,4), and d(8,5) after k = 4.
15. Solve the Chinese Postman Problem for each of the following graphs shown.
***
|
Responses
|
No responses found. Be the first to respond and make money from revenue sharing program.
|
|
Watch TV Channels
Watch Asianet TV onlineKairali TV in InternetSurya TV onlineAmritha TV Channel
|