UGC NET CS: Discrete Structures & Optimization - Graph Theory (9)

@sweetyasaiyed5920 UGC NET Paper 2 Computer Science and Applications Code No.:(87) UGC NET CS Syllabus Link: https://comptechaholic.com/e-learning/ For Lecture pdf of given video e-mail at: [email protected] Subject: PDF UNIT1 TOPIC5A Unit 1: Discrete Structures and Optimization (PART: 5A/7) Graph Theory: Topics Covered: Simple Graph Multigraph Weighted Graph Paths and Circuits Shortest Paths in Weighted Graphs Eulerian Paths and Circuits Hamiltonian Paths and Circuits Planner graph Graph Coloring Bipartite Graphs Index: Terminology: 1) Graph G=(V,E) 2) Edge 3) Loop 4) Multiple edge / parallel edges 5) Simple edge 6) Degree of a Vertex Deg(V) 7) Even and Odd Vertex 8) Degree of a Graph Types of graphs: 1) Null Graph Nn 2) Simple Graph / Strict Graph 3) Multi-Graph 4) pseudo-graph 5) Directed and Undirected Graph 6) Connected and Disconnected Graph 7) Strongly Connected Graph 8) Weakly Connected Graph 9) Complete Graph 𝐾5 10) Cycle Graph 11) Regular Graph 12) Bipartite Graph 13) Complete Bipartite Graph K3,3 14) Weighted Graph G=(E,V,w) 15) Planner graph 16) Non-planar graph 17) Eulerian Graph 18) Hamiltonian Graph Terminology: 9) Walk (Closed Walk & Open Walk) 10) Length of walk l 11) Trail, Circuit 12) Path, Cycle 13) Tour (Hamiltonian tour / Hamiltonian cycle & Eulerian tour / Eulerian circuit) Euler cycle (or tour) problem / Bridges of KAonigsberg problem: Eulerian Trail traversable Eulerian circuit Eulerian graph Euler’s Theorem Postman Problem / Chinese Postman Problem (CPP) Hamiltonian cycle problem: Hamiltonian circuit Hamiltonian graph Theorems (Dirac's Theorem & Ore's theorem) Traveling Salesman Problem (TSP) Hamiltonian Cycle Problem v/s Traveling Salesman Problem Traveling Salesman Problem (TSP) Example TSP Naive Solution Steps Kuratowski's theorem Planarity Criteria Graph Colouring: Vertex colouring (Chromatic number X(G), (proper) k-colouring, k-colourable, k-chromatic, Color class, k-colouring, k-independence sets / k-partite / k-colorable, Chromatic Polynomial, Method of Vertex colouring) Edge colouring (Chromatic index / edge chromatic number X'(G), k-edge colouring, k-matching, Tait-colouring, Four colour theorem) Hall's Marriage Theorem: Bipartite Graph Perfect Matching Neighbour The marriage problem / Bipartite perfect matching with Example Graphs Representation: Adjacency Matrix and Adjacency List Timecode: 00:12 Terminology 02:16 Types of graphs 10:58 Terminology 13:50 Euler cycle (or tour) problem / Bridges of KAonigsberg problem 16:44 Postman Problem / Chinese Postman Problem (CPP) 18:29 Hamiltonian cycle problem 19:22 Theorems (Dirac's Theorem & Ore's theorem) 20:17 Traveling Salesman Problem (TSP) 20:28 Hamiltonian Cycle Problem v/s Traveling Salesman Problem 22:41 Kuratowski's theorem 24:46 Planarity Criteria 25:22 Graph Colouring 25:33 Vertex colouring 29:10 Edge colouring 29:20 Hall's Marriage Theorem 31:31 The marriage problem / Bipartite perfect matching with Example 37:35 Graphs Representation: Adjacency Matrix and Adjacency List