graphs

Some notes on computer science graphs.

• Edges are of the form (v1, v2)
• Can be ordered pair or unordered pair
• Definitions
• A weight or cost can be associated with each edge - this is determined by the application
• w is adjacent to v iff (v, w) $\in$ E
• path: sequence of vertices w1, w2, w3, …, wn such that (wi, wi+1) ∈ E for 1 ≤ i < n
• length of a path: number of edges in the path
• simple path: all vertices are distinct
• cycle:
• directed graph: path of length $\geq$ 1 such that w1 = wn
• undirected graph: same, except all edges are distinct
• connected: there is a path from every vertex to every other vertex
• loop: (v, v) $\in$ E
• complete graph: there is an edge between every pair of vertices
• digraph
• directed acyclic graph: no cycles; often called a “DAG”
• strongly connected: there is a path from every vertex to every other vertex
• weakly connected: the underlying undirected graph is connected
• For Google Maps, an adjacency matrix would be infeasible - almost all zeros (sparse)
• an adjacency list would work much better
• an adjacency matrix would work for airline routes
• detect cycle
• dfs from every vertex and keep track of visited, if repeat then cycle
• Topological Sort
• Given a directed acyclic graph, construct an ordering of the vertices such that if there is a path from vi to vj, then vj appears after vi in the ordering
• The result is a linear list of vertices
• indegree of v: number of edges (u, v) – meaning the number of incoming edges
• Algorithm
• take it out, and take out the edges that start from it
• keep doing this as we take out more and more edges
• can have multiple possible topological sorts
• Shortest Path
• single-source - start somewhere, get shortest path to everywhere
• unweighted shortest path - breadth first search
• Weighted Shortest Path
• We assume no negative weight edges
• Djikstra’s algorithm: uses similar ideas as the unweighted case
• Greedy algorithms: do what seems to be best at every decision point
• Djikstra: v^2
• Initialize each vertex’s distance as infinity
• Start at a given vertex s
• Update s’s distance to be 0
• Repeat
• Pick the next unknown vertex with the shortest distance to be the next v
• If no more vertices are unknown, terminate loop
• Mark v as known
• For each edge from v to adjacent unknown vertices w
• If the total distance to w is less than the current distance to w
• Update w’s distance and the path to w
• It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor’s distance if smaller. Mark visited (set to red) when done with neighbors.
• Shortest path from a start node to a finish node
1. We can just run Djikstra until we get to the finish node
1. Have different kinds of nodes
• Assume you are starting on a “side road”
• Transition to a “main road”
• Transition to a “highway”
• Get as close as you can to your destination via the highway system
• Transition to a “main road”, and get as close as you can to your destination
• Traveling Salesman
• Given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
• Hamiltonian path: a path in a connected graph that visits each vertex exactly once
• Hamiltonian cycle: a Hamiltonian path that ends where it started
• The traveling salesperson problem is thus to find the least weight Hamiltonian path (cycle) in a connected, weighted graph
• Minimum Spanning Tree
• Want fully connected
• Want to minimize number of links used
• We won’t have cycles
• Any solution is a tree
• Slow algorithm: Construct a spanning tree:
• Remove an edge from each cycle
• What remains has the same set of vertices but is a tree
• Spanning Trees
• Minimal-weight spanning tree: spanning tree with the minimal total weight
• Generic Minimum Spanning Tree Algorithm
• KnownVertices <- {}
• while KnownVertices does not form a spanning tree, loop:
• find edge (u,v) that is “safe” for KnownVertices
• KnownVertices <- KnownVertices U {(u,v)}
• end loop
• Prim’s algorithm
• Idea: Grow a tree by adding an edge to the “known” vertices from the “unknown” vertices. Pick the edge with the smallest weight.
• Pick one node as the root,
• Incrementally add edges that connect a “new” vertex to the tree.
• Pick the edge (u,v) where:
• u is in the tree, v is not, AND
• where the edge weight is the smallest of all edges (where u is in the tree and v is not)
• Running time: Same as Dijkstra’s: Θ(e log v)
• Kruskal’s algorithm
• Idea: Grow a forest out of edges that do not create a cycle. Pick an edge with the smallest weight.
• When optimized, it has the same running time as Prim’s and Dijkstra’s: Θ(e log v)
• unoptomized: v^2