Graph Theory

1. Special Types of Graphs
   1. Trees
      1. Rooted Trees
         1. Definition and properties of rooted trees
         2. Applications in data structures (e.g., binary trees, quad trees)
         3. Tree traversal methods
            1. Pre-order traversal
            2. In-order traversal
            3. Post-order traversal
            4. Level-order traversal
         4. Conversion between general and rooted trees
      2. Binary Trees
         1. Characteristics of binary trees
         2. Special types:
            1. Full binary trees
            2. Complete binary trees
            3. Perfect binary trees
            4. Balanced binary trees
         3. Binary Search Trees (BST)
            1. Insertion and deletion operations
            2. Properties of BSTs
            3. Traversal and search operations
         4. Applications in databases and searching algorithms
      3. Spanning Trees
         1. Definition of spanning trees
         2. Relationship to connectivity
         3. Applications in network design and optimization
      4. Minimum Spanning Trees
         1. Concepts and properties
         2. Algorithms for finding MSTs
            1. Kruskal's Algorithm
               1. Description and step-by-step process
               2. Edge selection and sorting
               3. Use of disjoint set data structures
            2. Prim's Algorithm
               1. Description and step-by-step process
               2. Priority queue optimization
               3. Comparison with Kruskal's Algorithm
   2. Bipartite Graphs
      1. Definition and recognition
      2. Properties of bipartite graphs
      3. Applications in matching problems and network flows
      4. Complete Bipartite Graphs
         1. Definition and representation
         2. K_{m,n} notation and examples
         3. Applications in scheduling and resource allocation
   3. Planar Graphs
      1. Definition and basic properties
      2. Testing planarity
         1. Planarity criteria and theorems
         2. Kuratowski's Theorem
            1. Understanding forbidden subgraphs
         3. Graph drawing techniques for planar graphs
      3. Euler's Formula
         1. Application and derivation
         2. Use in proving properties of planar graphs
      4. Applications in circuit design and geography
   4. Complete Graphs
      1. Definition and characteristics
      2. Representation and notation (K_n)
      3. Properties, including edge count formula and adjacency relations
      4. Applications in network modeling
   5. Regular Graphs
      1. Definition and types (k-regular graphs)
      2. Properties and examples
      3. Applications in network topology and design
   6. Directed Acyclic Graphs (DAGs)
      1. Definition and identification
      2. Topological sorting
         1. Algorithms for topological sorting
         2. Applications in scheduling and dependency resolution
      3. DAGs in computer science and project management
         1. Application in compiler construction (dependency graphs)
   7. Hypergraphs
      1. Introduction and basic concepts
      2. Difference between graphs and hypergraphs
      3. Hypergraph partitioning and duality
      4. Applications in database theory and combinatorial optimization