ktu s4 cse graph theory SOME IMPORTANT UNIVERSIRTY QUESTIONS

on

 Some important questions of graph theory

MODULE 1

  • define: walk,path, circuit, isolated vertex, pendant vertex,null graph,trial and examples
  • state and prove hand shaking theorem
  • definition of isomorphism   : check whether the graph are isomorphism or not
  • non isomorphism with example
  • prove that  for a simple graph with n vertices and ko - Components an have atmost (n-k) (n-k+1)/2 edges 
  • ST a simple graph with n-vertices, the maximum no of edges n(n-1)/2and the maximum degree of any vertex is n-1.
  • show that in a simple graph with vertices is connected, if it has more that(n-1)(n-2)/2 edges
  • Discuss some of the Applications of graphs. 
  •  Explain kongisberg bridge problems
  • consider a graph with   4 Vertices; V1,V2, V3 and V4 degree 3, 5, 2. and 1 If possible to construct a graph?
  • Explain Konigsberg Bridge Problem?
  • Draw a 10 vertices disconnected Simple graph G and 4 components calculate the maximum G, with no: of edges.
  • Definition: Subgraphs (Edge disjoint Subgraph and Vertex disjoint Subgraph

MODULE 2

  • Different types of digraphs with example
  • Euler path,
  • Definition: Eulerian graph. Hamiltonian graph. Example Path, circuit
  • Fleury's Algorithm. Problem.
  • Theorem A connected graph if all vertices are of I's an degree. Euler graph
  • Fleury's Algorithm. Problem
  • Euler's circuit
  • Theorem A connected graphs "degree. if all vertices are of even Euler grapb
  •  Explain Travelling Salesman Theorem.
  •  Planar graph.

MODULE 3

  • Properties of trees 
  •  Rooted Tree., Spanning Tree.
  •  Find The centre & Eccentricity of a tree
  • Explain Warshall's (or) Algorithm Floyd - Warshall's Algorithm.
  • Cayley's Theorem.
  • Minimum Spanning Tree.- Algorithm 
  • Prims Algorithm.
  •  Kruskal's Algorithm.
  •  Dijkstra's Algorithm

MODULE 4

  • Vertex Connectivity & Edge Connectivity.
  • Definition: cut vertex, Example. cutset cut edge. Articulation point
  •  An inequality for vertex Connectivity and Edge connectivity 
  •  Fundamental cutset Properties of cutset
  • Planar graphs - kuratowski's Theorem
  • State and Prove the Euler's Formula
  • Dual of a graph (or) Geometric dual.

MODULE 5

  • Definition 
    • Adjacency Matrix
    • Incidence Matrix.
    • Circuit Matrix
  • Fundamental cycle matrix, cutset Matrix.
  • Path matrix, Fundament cutset Matrix.
  • Matching
  • Maximal matching
  • Matching Number
  • Perfect Matching
  • Every tree with n ≥ 2 vertices is 2- chromatic.
  • Colouring
    • Proper colouring
    • chromatic Polynomial 
    • chromatic Number 



Comments

Post a Comment