Graph Theory

  1. Paths, Walks, and Cycles
    1. Walks, Trails, and Paths
      1. Walks
        1. Vertex and Edge Sequences
          1. Length of Walks
            1. Closed and Open Walks
            2. Trails
              1. Distinct Edges
                1. Relationship to Walks
                2. Paths
                  1. Distinct Vertices
                    1. Simple Paths
                    2. Distinctions and Relationships
                      1. Hierarchy of Concepts
                        1. Examples and Counterexamples
                      2. Cycles and Circuits
                        1. Cycles
                          1. Definition in Undirected Graphs
                            1. Cycle Length
                              1. Simple Cycles
                              2. Circuits
                                1. Definition in Directed Graphs
                                  1. Directed Cycles
                                  2. Acyclic Graphs
                                    1. Trees as Acyclic Connected Graphs
                                      1. Forests
                                      2. Directed Acyclic Graphs (DAGs)
                                        1. Definition and Properties
                                          1. Topological Ordering
                                            1. Applications
                                              1. Task Scheduling
                                                1. Dependency Resolution
                                                  1. Compiler Design
                                              2. Connectivity
                                                1. Connected Components
                                                  1. Component Identification
                                                    1. Strongly Connected Components (Directed Graphs)
                                                      1. Weakly Connected Components (Directed Graphs)
                                                      2. Cut Vertices (Articulation Points)
                                                        1. Significance for Connectivity
                                                          1. Identification Algorithms
                                                          2. Cut Edges (Bridges)
                                                            1. Significance for Connectivity
                                                              1. Bridge-Finding Algorithms
                                                              2. Vertex Connectivity
                                                                1. k-Connected Graphs
                                                                  1. Minimum Vertex Cut
                                                                  2. Edge Connectivity
                                                                    1. k-Edge-Connected Graphs
                                                                      1. Minimum Edge Cut
                                                                      2. Menger's Theorem
                                                                        1. Vertex Version
                                                                          1. Edge Version
                                                                            1. Implications for Connectivity

                                                                        Previous

                                                                        3. Representing Graphs

                                                                        Go to top

                                                                        Next

                                                                        5. Graph Traversal