Lecture: Graph Theoretic Models for Optimization

Introduction

• Professor: Discusses importance and use of optimization models.
• Objective: Optimize a function (minimize or maximize) based on constraints.
• Previous Lectures: Introduced optimization through decision trees.

Graph Theoretic Models

What is a Graph?

• Components: Nodes (vertices) and edges (arcs).
• Nodes: May contain labels or complex data (e.g., student records).
• Edges: Connect nodes, can be undirected or directed (digraphs).
  • Undirected Edge: Flows both ways between two nodes.
  • Directed Edge (Digraph): Flows one way from source to destination.
• Edges Information: Can contain weights indicating effort, cost, etc.

Applications of Graphs

• Vacation Planning: Optimize travel routes.
• Drug Discovery: Model molecular interactions and transformations.
• Family Trees: Ancestral relationships as trees (directed graphs without loops).
• Real-Life Networks: Computer networks, transportation, financial networks, utility distribution (sewer, water, electrical), social networks, etc.

Analyzing Graphs

• Inference: Capturing interesting relationships and making predictions.
• Example: Analyzing character interactions in "The Wizard of Oz."
• Problems: Finding paths, shortest paths, graph partitions, min-cut/max-flow problems.

Building Graphs

Data Structures

• Nodes: Represented as objects with names.
  • Node class: Holds a name, methods to retrieve and print the name.
• Edges: Connect nodes; represented by the Edge class.
  • Edge class: Holds source and destination nodes.

Directed Graph (Digraph)

• Representation: Adjacency matrix (inefficient) or adjacency list (preferred).
• Adjacency List: Each node key maps to a list of destination nodes (values).
  • Code: Digraph class with methods to add nodes and edges, check for existence, and print.

Undirected Graph

• Subclassing Digraph: Adding edges in both directions.
• Graph: Uses inheritance and method overriding to handle bidirectional edges.

Searching Graphs

Depth-First Search (DFS)

• Approach: Explore edges deeply before backtracking.
• Implementation: Recursive method avoiding loops, exploring paths one at a time.
• Code: Provided for DFS with detailed explanation and example.

Breadth-First Search (BFS)

• Approach: Explore all edges of a given length before moving to longer paths.
• Implementation: Uses a queue to keep track of paths, guaranteeing the shortest path found is minimal in length.
• Code: Provided for BFS with an illustrative example.

Additional Considerations

Weighted Graphs

• Objective: Minimize the total weight rather than the number of edges.
• DFS Adaptation: Straightforward for weighted paths, sum the weights.
• BFS Limitation: Requires modification as it doesn’t naturally handle weights well.

Conclusion

• Summary: Graphs are versatile for modeling relationships and solving optimization problems.
• Next Steps: More examples and deeper exploration in future lectures.