Graph Theory [MAT206] introduces the basic concepts of graph theory in KTU, including the properties and characteristics of graph/tree and graph theoretical methods that are widely used in mathematical modelling and have applications in computer science and other branches of engineering. In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
A graph in this context is made up of vertices that are connected by edges. You can learn KTU subjects through our excellent study materials comprising of Notes, Presentations and Previous Years Question papers which are easily available on our website (www.keralanotes.com).
| Board | KTU |
| Scheme | 2019 New Scheme |
| Year | Second Year |
| Semester | S4 Computer Science |
| Subject | MAT 206 | Graph Theory Notes |
| Credit | 4 Credit |
| Category | KTU S4 Computer Science |
KTU S4 CSE Graph Theory | MAT206 | Notes (2019 Scheme)
Module 1
Module 1 - Syllabus
Introduction to graphs: Introduction- Basic definition – Application of graphs – finite, infinite and bipartite graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Paths and circuits – Isomorphism, subgraphs, walks, paths and circuits, connected graphs, disconnected graphs and components
Module 1 - Notes
Module 1 Graph Theory | MAT206 PDF Notes
Module 1 Graph Theory | MAT206 PPT Notes
Module 1 Graph Theory | MAT206 QUESTION BANK
Module 2
Module 2 - Syllabus
Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and binary relation, Directed paths, Fleury’s algorithm.
Module 2 - Notes
Module 2 Graph Theory | MAT206 PDF Notes
Module 2 Graph Theory | MAT206 PPT Notes
Module 2 Graph Theory | MAT206 QUESTION BANK
Module 3
Module 3 - Syllabus
Trees and Graph Algorithms: Trees – properties, pendant vertex, Distance and centres in a tree - Rooted and binary trees, counting trees, spanning trees, Prim’s algorithm and Kruskal’s algorithm, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm.
Module 3 - Notes
Module 3 Graph Theory | MAT206 PDF Notes
Module 3 Graph Theory | MAT206 PPT Notes
Module 4
Module 4 - Syllabus
Connectivity and Planar Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits, Planar graphs, Kuratowski’s theorem (proof not required), Different representations of planar graphs, Euler's theorem, Geometric dual.
Module 4 - Notes
Module 4 Graph Theory | MAT206 PDF Notes
Module 4 Graph Theory | MAT206 PPT Notes
Module 5
Module 5 - Syllabus
Graph Representations and Vertex Colouring: Matrix representation of graphs- Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix. Colouring- Chromatic number, Chromatic polynomial, Matchings, Coverings, Four-colour problem and Five colour problem. Greedy colouring algorithm.
Module 5 - Notes
Module 5 Graph Theory | MAT206 PDF Notes
Module 5 Graph Theory | MAT206 QUESTION BANK
KTU S4 CSE Related Links
| KTU S4 CSE Syllabus | Click Here |
| KTU S4 CSE Study Notes | Click Here |
| KTU S4 CSE Reference Textbook | Click Here |
| KTU S4 CSE Previous Year Solved Questions | Click Here |
| KTU S4 CSE Study Materials | Click Here |
Other Related Links
| MAT 206 - Graph Theory | Click Here |
| CST 202 - Computer Organization and Architecture | Click Here |
| CST 204 - Database Management Systems | Click Here |
| CST 206 - Operating System | Click Here |
| EST 200 - Design and Engineering | Click Here |
| HUT 200 - Professional Ethics | Click Here |
| MNC 202 - Constitution Of India | Click Here |
| CSL 202 - Digital Lab | Click Here |
| CST 206 - Operating Systems Lab | Click Here |
