See all results for
    1. In India, MOOCs Are Now Part of the Education System
    2. Coursera’s Monetization Journey: From 0 to $100+ Million in Revenue
    3. Udacity Doubles Prices, Relaunches 1-on-1 Mentorships & Career Coaching
    See more
    1. Sign in
    2. Register

    Get started with custom lists to organize and share courses.

    Sign up

    Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

    Advanced Graph Theory

    Indian Institute of Technology Kanpur and NPTEL via Swayam

    Found in Computer Science, Algorithms and Data Structures
    Go to class

    Taken this course? Share your experience with other students. Write review

    Overview

    Advanced Graph Theory focuses on problem solving using the most important notions of graph theory with an in-depth study of concepts on the applications in the field of computer science. This course provides an in-depth understanding of Graphs and fundamental principles and models underlying the theory, algorithms, and proof techniques in the field of Graph Theory. Emerging applications of Graph Theory in Computer Science domain will be covered for significant impact. Upon completing this course, students will have intimate knowledge about how the graph theory play an important role to solve the technology driven and research oriented problems.

    Syllabus

    Week 1 : Basic Concepts: Graphs and digraphs, Incidence and adjacency matrices, isomorphism, the automorphism group.
    Week 2 : Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger s theorem; Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, The Travelling Salesman problem, diameter and maximum degree, shortest paths.
    Week 3 : Trees: Equivalent definitions of trees and forests, Cayleys formula, the Matrix-Tree theorem, minimum spanning trees;
    Week 4 : Matchings: Berges Theorem, perfect matchings, Halls theorem, Tuttes theorem, Konigs theorem, Petersens theorem, Algorithms for matching and weighted matching (in both bipartitie and general graphs), factors of graphs (decompositions of the complete graph), Tuttes f-factor theorem;
    Week 5 : Extremal problems: Independent sets and covering numbers, Turans theorem, Ramsey theorems;
    Colorings: Brooks theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number
    Week 6 : Vizings theorem; Graphs on surfaces: Planar graphs, duality, Eulers formula, Kuratowskis theorem, toroidal graphs, 2-cell embeddings, graph on other surfaces;
    Week 7 : Directed graphs: Tournaments, directed paths and cycles, Connectivity and strongly connected digraphs, branchings;
    Networks and flows: Flow cuts, Max flow min cut theorems, perfect square;
    Week 8 : Selected topics: Dominating sets, The reconstruction problem, Intersection graphs, Perfect graphs, Random graphs.

    Taught by

    Rajiv Misra

    Tags

    graph theory algorithms core

    Related Courses

    Browse More Computer Science courses

    Reviews for Swayam's Advanced Graph Theory
    Based on 0 reviews

    • 5 star 0%
    • 4 star 0%
    • 3 star 0%
    • 2 star 0%
    • 1 star 0%

    Did you take this course? Share your experience with other students.

    Write a review

    Class Central

    Get personalized course recommendations, track subjects and courses with reminders, and more.

    Sign up for free

    Never stop learning Never Stop Learning!

    Get personalized course recommendations, track subjects and courses with reminders, and more.

    Sign up for free