Scribd Logo
Upload

Welcome to Scribd!

  • 97 views

    Mat206 Graph Theory, July 2021

    Uploaded by

    Neil shijil kumar
    This document appears to be an exam for a Graph Theory course. It contains 20 multiple choice and written response questions across 5 modules: 1. Basic graph theory concepts like complete graphs, walks, paths and circuits. 2. Graph operations like unions and spanning trees. 3. Graph algorithms like Prim's algorithm and Dijkstra's algorithm. 4. Graph properties like circuits and cuts. 5. Advanced concepts like chromatic polynomials and path matrices. The questions test a range of graph theory fundamentals and proofs about properties of graphs and graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Mat206 Graph Theory, July 2021

    Uploaded by

    Neil shijil kumar
    97 views3 pages
    This document appears to be an exam for a Graph Theory course. It contains 20 multiple choice and written response questions across 5 modules: 1. Basic graph theory concepts like complete graphs, walks, paths and circuits. 2. Graph operations like unions and spanning trees. 3. Graph algorithms like Prim's algorithm and Dijkstra's algorithm. 4. Graph properties like circuits and cuts. 5. Advanced concepts like chromatic polynomials and path matrices. The questions test a range of graph theory fundamentals and proofs about properties of graphs and graph algorithms.

    Original Description:

    GT

    Original Title

    MAT206 GRAPH THEORY, JULY 2021

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document appears to be an exam for a Graph Theory course. It contains 20 multiple choice and written response questions across 5 modules: 1. Basic graph theory concepts like complete graphs, walks, paths and circuits. 2. Graph operations like unions and spanning trees. 3. Graph algorithms like Prim's algorithm and Dijkstra's algorithm. 4. Graph properties like circuits and cuts. 5. Advanced concepts like chromatic polynomials and path matrices. The questions test a range of graph theory fundamentals and proofs about properties of graphs and graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    97 views3 pages

    Mat206 Graph Theory, July 2021

    Uploaded by

    Neil shijil kumar
    This document appears to be an exam for a Graph Theory course. It contains 20 multiple choice and written response questions across 5 modules: 1. Basic graph theory concepts like complete graphs, walks, paths and circuits. 2. Graph operations like unions and spanning trees. 3. Graph algorithms like Prim's algorithm and Dijkstra's algorithm. 4. Graph properties like circuits and cuts. 5. Advanced concepts like chromatic polynomials and path matrices. The questions test a range of graph theory fundamentals and proofs about properties of graphs and graph algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Reg No.

    *t*ooI,KAtSAqq0M*jffr96gsd896
    Fourth Semester B.Tech Degree ExaminationJuly 2021

    Course Code: MAT206


    Course Name: GRAPH TIIEORY
    Max. Marks: 100 Duration:3 Hours

    PART A
    \ (Answer all questions; each qaestion carries 3 marlcs) Marks

    -:f What is the maximum number of edges in a simple graph with n vertices? 3

    JustiS your answer.


    There are 25 telephones in Metropolis. Is it possible to connect them with wires 3

    so that each telephone is connected with exactly 7 others? Why?


    Show that all vertices ofan Euler graph G are ofeven degree 3

    Explain strongly connected and weakly connected graphs with the help of 3

    examples.

    Prove that a connected graph G with n vertices and n-l edges is a tree. 3

    How many labelled trees are there with n vertices? Draw all labelled trees with 3

    3 vertices.'

    Define planar graphs. Is IQ, the complete graph with 4 vertices, a planar graph? 3

    Justifr.
    Define fundamental circuits and fundamental cut-sets.
    Construct the adjacency matrix and incidence matrix of the graph .

    l0 Defi ne chromatic number, What is the chromatic number of a tree with two or

    more vertices?

    Page 1 of 3

    Downloaded from Ktunotes.in


    02000MAT206052101

    PART B
    (Answer onefull qaestionfrom each module, each qaesfion carries 14 marks)
    Module -l
    ll a) Define complete graph and complete bipartite gaph. Draw a graph which is a
    complete graph as well as a complete bipartite graph.
    b) Explain walks, paths and circuits with the help of examples. 7

    rz a) Define isolated vertex, pendant vertex, even vertex and odd vertex. Draw a 7
    graph that contains all the above.

    b) Prove that simple graph with n vertices and k components can have at most
    \ (n-k)(n-k+l)12 edges.
    Module -2
    t3 a)

    dg

    Find the unioru intersection and ring sum ofthe above graphs.
    b) State travelling salesman problem. How it is related to Hamiltonian circuits? 5

    14 a) Prove that in a complete graph with n vertices there are (n-l)/z edge disjoint 7

    Hamiltonian circuits, if n is an odd number and n 2 3 .

    b) For which values of m, n is the complete graph K-,n an Euler graph ? Justi$
    your answer.

    Module -3
    15 a) Prove that a binary tree with n vertices has (n+1)/2 pendant vertices. 7

    b) Using Prims algorithm, find a minimal spanning tree for the following graph. 7

    l6 a) Write down Dijkstra's algorithm and use it to find the shortest path from s to L

    Page 2 of 3

    Downloaded from Ktunotes.in


    020{x}MAIt2060s2101

    b) Plove that every tree has either one or two centers.

    Module -4
    l7 a) Define cut-set. Prove that every circuit in G has an even number
    of edges in
    a.
    coflrmon with any cut-set.

    ,"t
    b) Constnrct the geometric dual of the graph below

    18 a) Prove that a connected planar graph with n vertices and e


    edges has e-n+2
    regions.
    b) Let G be a connected graph and e an edge ofG. Show that e is a cut-edge
    if
    and only if e belon$s to every spanning tree.

    Module -5
    l9 a) Explainfour colour probren using the concept of chromatic number. 5
    b) Let B and A be the circuit matrix and the incidence matrix of a graph G which 9
    is free from loops, whose columns are arranged using the same
    order of edges.
    t Show that 6Br:94r:9 (mod 2).
    20 a) show that chroniatic polynomial of a tree with n vertices is pr,(,tr) :
    7Q'- 11n-t
    b) Define path matrix of a graph. Find the path matrix p(x, y) for the graph below.

    *****

    Page 3 of 3

    Downloaded from Ktunotes.in

    You might also like