# Graph Theory Notes KTU S4 Maths 2019 Scheme | Kerala Notes

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)

Are you in need of study materials for Graph Theory MAT206? Well, stay connected with us to download complete study materials which include class notes, presentations (PPT or PowerPoint), downloadable (PDF or WORD files) and lab activities.

### 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 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 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 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 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 QUESTION BANK

Feel free to comment and share this if you found it useful. Give your valuable suggestions in the comment session or contact us for any details regarding the KTU Second Year S4 Computer Science (CSE) 2019 Scheme Study Materials, Syllabus, Previous Year Solved Question Papers, and Other Materials.

### KTU S4 CSE Related Links

We hope the given KTU S4 Computer Science (CSE) Latest 2019 Scheme Syllabus, Notes, Study Materials, Previous Year Questions and Other Materials will help you.

If you have any queries regarding the KTU S4 Computer Science (CSE) Study Materials, drop a comment below and we will get back to you at the earliest.

Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com      Keralanotes.com