Graphs and Networks

List of Algorithms

1. Minimum Spanning Trees

   • Krusikal’s (Any point but min with no cycle)
   • Prim’s (From starting point)

2. Graph Traversal Techniques

   • BFS
   • DFS
   • Djkstra’s Shortest Path
   • Apply DFS for checking cut vertex

3. Eulerian/Hamiltonian Graphs

   • Eulerian Graph even degree
   • Fleury’s Algorithm
   • Closure of Graph
   • Sufficient conditions of Hamiltonian Graph (and Restricted Hamiltonian Algo)

4. Travelling Salesman Problem

   • TSP1- From weight matrix, draw tables
   • TSP2 - Take min span, DFS from leaf node and join all endpoints

5. Network Flow Algo - MaxFlow Mincut

Resources

• D3 Graph Theory
• Algebraic Graph Theory Courses by Dan Spielman and his Miracles video
• Spectral Graph Theory Course and sources from Dan’s Course
• Recommended Papers for Eigenvalues of Graphs with applications by Dan

Proof/Question Hints

Induction is by far the most popular. Contradiction is sometimes used with a construction

• Take Longest path in graph (delete or not)
• Check type of cycles in graph
• Adjacency Matrix, Caylay Matrix, Graph Laplacian and Incidence Matrix based approach
• Number of components more or less (cut-edge, hamiltonian…)
• If cycle length 2, Bipartite
• Planar = draw planar drawing
• Non-planar
  • Euler’s Formula or 5-degree or variants(girth-analysis)
  • Check any Subgraph non-planar
  • Kuratowski and/or Wagner
• If no triangles, then relation between q & r (where q unrestricted)

List of Theorems

1. Isomorphic if complement is isomorphic
2. Every tree (with >= 2 vertices) has >=2 leaves
3. Simple G with n vert, k components, has atleast n-k edges
4. Characterstics of Tree
5. If G has walk, G contains path
6. Every closed odd walk contains odd cycle
7. Bipartite iff no odd cycle
8. Kirchoff’s Matrix-Tree Thm
9. Caylay Thm
10. Euler even degree (and disjoint cycle) thm
11. Whitney’s Thm
12. Euler’s Planar Graph Formula and Thm
13. Max Planar Graph thms using Girth Formula
14. Planarity of Graphs - Kuratowski and Wagner Thms
15. Graph Coloring
    • Simple graph with K-blocks has max chromatic no. of blocks
    • For any simple graph, max chromatic no. < max degree + 1
    • Five Color Theorem (Step towards of 4 Color Thm)

Week Wise Review

Week 1

• Types of Graphs
• Graphical Sequence Algorithm
• Degree Sum and Edges relation
• Neighbourhood (open/close)
• k-regular graphs
• Isomorphic or not
• Subgraphs and Induced Subgraphs

Types of Graphs

• Null
• Complete
• Bipartite
• Complete Bipartite
• Cycle
• Path
• (Graphs n = 1, 2 vertices)
• (self-compliment Graphs)
• (planar graphs)

Week 2

See Examples for each Case!

• walk :: anything from start_vertex to end_vertex

• trail :: edges distinct

• path :: vertices distinct

• closed walk :: start_vertex = end_vertex

• Connectivity, Components

• Cut-Edge, Cut-Vertex

• Contraction of graph, minor of a graph (Contraction)

• Weakly/Strongly Connected

Isomorphic Graphs

• Odd/Even Cycles and/or biparitite
• Compliment Isomorphism

Week 3

• Trees, Forests (star, path)
• Represent arithematical equations graphically
• Every tree has k leaves
• G contains atleast $E - V + 1$ cycles
• Characterstics of Tree (see proof)
• distance: shortest u,v path in tree (don’t count start!)
• eccentricity: max of distance between all u-v path for u
• diameter: max of eccentricites of all vertices (farthest two points)
• center: point with min eccentricity
• radius: min of eccentricities (or eccentricity of center)
• rooted trees, ordered rooted trees, parent, child, ancestor, descendants, siblings
• Binary trees, Regular binary trees (deg 3 or less)

Week 4

• wiring, spanning trees, spanning forests
• Three main types of Matrices
  • Adjacency Matrix: (V, V) based and shows no. of edges between each pair of vertices (1 or 0 only for simple graphs)
  • Incidence Matrix: which edges are incident for each vertex (V, E)
  • Graph Laplacian: Degree of vertices along diagonal. -1 wherever edge. 0 wherever no edges. See graph laplacian video
• Kirchoff’s Matrix-Tree Thm
• Minimum Cost Spanning Trees, Weight Func
• Krusikal and Prim’s Min Spanning Tree finding algo

Week 5

• Edge Based
  • eulerian trail( n-2 even 2 odd )
  • eulerian circuit (all even)
  • eulerian graph (contains eulerian circuit)
• Euler-Path finding algorithm (and proof of even degree)
• Fleury’s Algo
• Hamiltonian path, hamiltonian graph, sufficient conditions for hamiltonian graph

Hamiltonian Cycle is just another way of saying subgraph Cn!

• Hamiltonian closure and finding hamiltonian graphs
• TSP1 and TSP2 graph algos

Week 6

• Connectivity, edge cuts, k-edge-connected(returns bool), edge-connectivity (returns int connectivity)
• Vertex Connectivity, Vertex-Cut Set, min degree, max degree
• Whitney’s Thm

Network Flows and Related Topics (Week before Midsem)

• Flow - flow, capacity, source, sink
• Maximum Flow Problem :: Ford-Fulkerson Algo, Residual Graph, Augmented Paths
• Min Cut Problem :: S-T cut, Cap(A, B), Cut where Residual Graph paths end
• Flow value Lemma (same as out of source)
• Max-Flow Min-Cut Thm $$ val(f) = \sum*{out\ of\ a} f(e) - \sum*{in\ to\ a} f(e) = \sum_{out\ of\ a} f(e) = cap(A, B)$$
• Disjoint Paths - Ford-Fulkerson with capacities all 1
• Menger’s Thm - Min no. of vertices required to be removed to disconnect u-v path
• k-connected k-vertex disjoint paths

Blocks and Block Diagrams

Week 7

• Planar Graphs, Planar Embeddings
• Planar Drawing
• Face, Boundary
• Euler’s Graph Formula p - q + r = 2
• Maximal Planar Graphs and Girth Formula $$ \frac{g(n-2)}{g-2}$$
• Homeomorphic and Subdivisions
• Kuratowski and Wagner Thms
• Duality / Dual Plane
• Crossing Number

Kuratowski/Wagner Thm

Week 8

• Chromatic Number of Graph, k-colorable
• Chromatic No. of Blocks thm and max degree + 1 thms
• Booke’s Thm Neither Complete nor odd cycle < max degree
• 5 Color Thm (Towards 4-color)
• Edge Chromatic No. and Thm for Bipartite graphs and simple graph

Graph Numbers and their relations