Summary
Summary Graph Theory
- Course
- Institution
Summary of the Graph Theory course, taught at Maastricht University. Contains at least the following topics: graphs cliques tours paths flows walks map graphs
[Show more]
Seller
Follow
FamkeNouwens
Reviews received
Content preview
Graph Theory Matús MihalákGeneral graphs
A graph G has vertices V and edges E, notation: G = (V, E).
• ∑𝑣∈𝑉 𝑑(𝑣) = 2|𝐸| (sum of all degrees of vertices is equal to twice the number of edges)
• 𝛿(𝐺): minimum degree of G → vertex with the minimum degree (𝛿(𝐺) ≤ 𝑛 − 1)
• ∆(𝐺): maximum degree of G → vertex with the maximum degree
∑𝑣∈𝑉 𝑑(𝑣)
• 𝑑(𝐺): average degree of G ( )
|𝑉|
• Isomorphism: graphs that have the same number of vertices and edges and the same
edge connectivity (same vertices must be connected to each other).
Both graphs should have:
- Same |V| and |E|
- Same degree at every edge
- Same length of cycles
• Complete graph: every vertex is connected to every other vertex.
• Simple graph: unweighted, undirected graph containing no loops or multiple edges.
Vertices
• Number of vertices = |V| = n.
• Degree of a vertex = d(v).
• Vertices u and v are adjacent (neighbours) if there exists an edge with vertices u and v
and endpoints in E ( {𝑢, 𝑣} ∈ 𝐸 ).
• For an edge e= {u, v}, u and v are endpoints or end-vertices of edge e.
• Neighbourhood of a vertex v in a graph G= (V, E) is a set of all vertices that are connected
by edges to vertex v: 𝑁𝐺 (𝑣) = {𝑢|𝑢 ∈ 𝑉 ∧ {𝑢, 𝑣} ∈ 𝐸}
• A vertex with degree 1 is a leaf (especially makes sense in a tree).
Edges
• Number of edges = |E| = m.
• Edge e is incident to vertex v if there exists an edge e in E that has v as an endpoint.
A clique is a subset of vertices such that every vertex is connected to every other vertex in the
clique, meaning the subgraph (clique) is complete.
𝑉 ′ ⊆ 𝑉 such that ∀ 𝑢, 𝑣 ∈ 𝑉 ′ : {𝑢, 𝑣} ∈ 𝐸
Tours
Path: a set of vertices and a set of edges that connect every vertex to the next vertex in the set.
So it is a non-empty graph P= (V, E) of the form V= {x0, x1, …, xk}, E= {x0x1, x1x2, …, xk-1xk} and every
xi,xj (i≠j) are distinct vertices.
• Length of a path P is the number of edges of P (|E|)
• Pxi: x0,x1,…,xi
xiP: xi,xi+1,…,xk
xiPxj: xi,…,xj
• Two paths P and P’ are independent if none of the paths contains an inner vertex of the
other path, but they may contain end-vertices of the other path.
, • d(u, v): distance between vertices u and v is the length of the shortest path from u to v.
If no path exists, then d(u, v) = ∞.
• Shortest path
- dk[u]: weight of shortest s-u path using ≤ k edges
- Computing this u-v path by Dijkstra’s algorithm for positive weights (O(n
Log(n)+m)):
▪ Greedy algorithm
▪ Maintain d[v] for all v in V, upper-bound on d (u,v)= ∞
▪ D[v]=0 and S=∅
▪ Step-by-step, d[v] becomes d(u,v):
WHILE S≠V DO
u⟵arg minv⊆V\S d[v] (minimum of d[v]-list)
S⟵ S ∪ {u}
∀ edges (u,x) ∈ E:
IF d[x]>d[u]+w(u,x)THEN
d[x]:= d[u]+w(u,x)
▪ Keeps S⊆V, a set of “fixed” vertices for which d[v]=dist(u,v)
- Bellman-Ford algorithm (O(nm)):
▪ D[v]:= ∞, 𝜋[v]=NIL (undefined)
▪ D[s]=0, 𝜋[s]=s
▪ FOR k=1 to n-w DO
• ∀ edges (u,v) ∈E
o IF d[v]>d[u]+w(u,v) THEN
D[v]:= d[u]+w(u,v)
𝜋[v]=u
▪ After round i: d[v1] = d(s, vi)
▪ There is a negative cycle in G if and only if ∃ edge (u, v) ∈ E:
𝑑[𝑣] > 𝑑[𝑢] + 𝑤(𝑢, 𝑣). So, using n edges to get cheaper to v means there
is a negative cycle.
- Path P from s-t is a shortest path, then ∀ u, v ∈ P, uPv is a shortest u-v path in G (if
no negative weighted cycles in G).
▪ Keep d[v] upper-bound on d(s,v)
▪ Keep 𝜋[v] predecessor of v on a shortest s-v path
▪ Compute shortest s-v paths using at most k
edges (k=0,1,…,n-1)
▪ Example:
• K=0 d[s]=0 - d[v1] = d[v2] = d[v3] = d[t]= ∞
• K=1 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]= ∞ - d[t]=10
• K=2 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=9
• K=3 d[s]=0 - d[v1]=11 - d[v2]=8 - d[v3]=10 - d[t]=7
• diam(G): diameter is the largest distance between any two vertices u and v (so the largest
shortest path!)
• G is disconnected if there exists u and v such that there is no path from u to v.
• Alternating path: a path in G starting with an unmatched vertex and edges on the path
alternate with “∉ 𝑀” and “∈ 𝑀”.
• Augmenting path is a path P in a graph G= (V, E) with a matching M (improved idea of the
maximum matching algorithm).
- It starts and ends with an unmatched vertex.
- Every second edge in P is ∈ M.
- Then, augment matching along path P, i.e. flipping.
• The algorithm returns a maximum matching, because for any matching M of graph G:
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller FamkeNouwens. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.01. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
65507 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 15 years now