Summary of Operations Research: Theory and Applications
Operations Research: Theory and Applications for Students
Introduction
Graph theory studies structures made of vertices (nodes) and edges (links) and models relationships, routes, and networks. This guide summarizes key concepts, algorithms, and applications you should memorize for quick recall.
Definition: A graph is a set of vertices connected by edges; edges may be directed or undirected and may carry weights representing cost, distance, time, or capacity.
Basic concepts
Vertices and degrees
- Degree of a vertex: number of incident edges (for directed graphs, use in-degree and out-degree).
Definition: An odd-degree vertex is a vertex connected to an odd number of edges.
Paths and cycles
- Path: a sequence of vertices where each adjacent pair is connected by an edge and vertices are not repeated. Example: $A$-$B$-$C$.
- Cycle (or circuit): a path that starts and ends at the same vertex, e.g. $A$-$B$-$C$-$A$.
Definition: An Eulerian circuit is a closed route that starts and ends at the same vertex and uses every edge exactly once.
Applications:
- Paths: shortest-path routing and navigation.
- Cycles: Chinese Postman problem, tours, and circuit inspection.
Special graphs
- Complete graph $K_n$: every pair of distinct vertices is connected by an edge.
Property: The chromatic number of $K_n$ is $n$ (you need $n$ distinct colors).
- Weighted graph: edges (or vertices) have numerical values such as cost, distance, time, or capacity.
Interpretations of weights: distance in routing, time in scheduling, cost in transportation, capacity in flows.
Spanning trees and minimum spanning tree (MST)
- Spanning tree: a connected, acyclic subgraph that contains all vertices. For $n$ vertices it has $n-1$ edges.
- Minimum Spanning Tree (MST): a spanning tree with minimum total edge weight. Useful for designing cheapest networks.
Compare Prim vs Kruskal:
| Aspect | Prim | Kruskal |
|---|---|---|
| Growth | Grows one tree from a start vertex | Builds forest by adding edges globally |
| Edge selection | Cheapest edge connecting tree to outside | Globally cheapest edge that doesn't create cycle |
| Useful when | Dense graphs, implemented with heaps | Sparse graphs, implemented with union-find |
Shortest paths
Dijkstra's algorithm
- Start at source with distance $0$.
- Repeatedly pick unvisited node with smallest tentative distance, relax outgoing edges, update distances.
- Works for non-negative edge weights.
Example: On a graph, label nodes with tentative distances and update them using edge weights; in an adjacency matrix, use the row/column weights to relax distances.
LP formulation (compact)
For shortest path from source $s$ to sink $t$, let $x_{ij}=1$ if arc $i$-$j$ is chosen. Minimize $$\sum_{i,j} c_{ij} x_{ij}$$ subject to flow-balance: source sends $1$, sink receives $1$, other nodes balance $0$ (and $x_{ij}\ge 0$).
(Note: this is a flow-model representation; see separate LP course for deeper LP theory.)
Eulerian trails and Chinese Postman
- A graph is Eulerian (has an Eulerian circuit) iff every vertex has even degree and the graph is connected (ignoring isolated vertices).
- Chinese Postman problem: make a non-Eulerian graph Eulerian with minimum extra cost.
- Find vertices of odd degree.
- Pair them so that the sum of shortest path distances between paired vertices is minimal.
- Duplicate the edges on those shortest paths; after duplication all degrees become even, enabling an Eulerian circuit.
Example: If there are four odd vertices, compute pairwise shortest paths, find pairing with minimal total weight, and duplicate those paths.
Network flows and Ford–Fulkerson
- Flow network: nodes are junctions, directed edges are routes, capacities limit flow.
Goal: Maximum Flow Problem:
Zaregistruj se pro celé shrnutíAlready have an account? Sign in
Graph Theory Essentials
Klíčová slova: Linear Programming, Graph Theory, Project Management
Klíčové pojmy: Odd-degree vertex: vertex with odd number of incident edges, Eulerian circuit: closed trail using every edge exactly once, Chinese Postman: pair odd vertices via shortest paths and duplicate them, Path vs cycle: path has no repeated vertices; cycle starts and ends at same vertex, Complete graph K_n has chromatic number n, MST has n-1 edges and minimizes total edge weight, Dijkstra finds shortest paths for non-negative weights by greedy relaxation, Ford–Fulkerson augments flow via residual graph and bottleneck capacity, Saturated edge: capacity fully used, Chromatic number gives minimum time slots in scheduling, Degree centrality = degree; normalized by n-1, Betweenness centrality counts shortest paths passing through a node