definition and proofs, this course is intended for getting intuition with many examples and visualizations. More formal exposition can be found in great textbooks, e.g., • Diestel “Graph Theory” • Schrijver “Combinatorial Optimization: Polyhedra and Efficiency” 3 / 56
pair of vertices and edges, usually written as G = ( V vertex set , E edge set ) In this talk, we only consider finite graphs, i.e., |V |, |E| < +∞. 6 / 56
of G if H is contained in G. • H is an induced subgraph of G if V (H) = X and E(H) = {ij ∈ E(G) | i, j ∈ X} for some X ⊆ V (G). subgraph induced subgraph 12 / 56
• G is complete if ij ∈ E for all distinct i, j ∈ V . complete graph • G is bipartite if V can be partitioned into two sets V1 , V2 s.t. ij ∈ E implies i ∈ V1 and j ∈ V2 . • tripartite and k-partite graphs are defined similarly. V1 V2 bipartite graph 15 / 56
(v0 , v1 , . . . , vk ) s.t. vi−1 vi ∈ E (i = 1, . . . , k). k is the length of the walk. • Walk is closed if with v0 = vk . • Path is a walk with distinct vertices. • Cycle is a path of length ≥ 2 plus an edge between the two endpoints of the path. Walk Path Closed walk Cycle 16 / 56
if there is a path between any two distinct vertices. • Each maximal connected subgraph is called a connected component. connected disconnected 17 / 56
if it has no cycles. • A connected forest is called a tree. • A tree has vertices with degree 1 (leaves) • A tree is binary if non-leaf vertices have exactly two children. tree leaves forest binary tree 18 / 56
a path from a vertex s to a vertex t. • dist(s, t) = length of a shortest s–t path • Diameter is diam(G) := maxs,t∈V dist(s, t) s t dist(s, t) = 3 = diam(G) 19 / 56
a path from a vertex s to a vertex t. • dist(s, t) = length of a shortest s–t path • Diameter is diam(G) := maxs,t∈V dist(s, t) s t dist(s, t) = 3 = diam(G) Weighted graph • Each edge e ∈ E has a weight (length) w(e) ∈ R. • Then, the length of a path is the sum of edge lengths. s 3 2 1 2 −3 1 t 1 dist(s, t) = 1 19 / 56
= (V, E), edge weight w(e) ∈ R (e ∈ E), s, t ∈ V Find: shortest s–t path (if exists) Theorem For the shortest path problem, there are • O(n3)-time algorithm (Bellman-Ford) for general weight • O(m + n log n)-time algorithm (Dikstra) for nonnegative weight where n = |V | and m = |E|. 20 / 56
find NetworkX handy. • Python based (so you can try on e.g. Google’s Colab) • Easy to use and well-documented • Many graph families and algorithms implemented • Integrated with SageMath NetworkX Network Analysis in Python 22 / 56
graph • A subgraph H of G is spanning if V (G) = V (H). • A spanning tree is a tree in G that is spanning. Minimum spanning tree problem Given: connected graph G = (V, E), edge weight w(e) ∈ R (e ∈ E) Find: spanning tree T of G s.t. e∈T w(e) is minimized. A spanning tree 25 / 56
the empty forest on V 2: Sort edges in increasing order of weight: w(e1 ) ≤ · · · ≤ w(em ) (m = |E|). 3: for i = 1, . . . , m : 4: Add ei to T if it does not create a cycle. Otherwise, discard ei . 5: return T 27 / 56
the empty forest on V 2: Sort edges in increasing order of weight: w(e1 ) ≤ · · · ≤ w(em ) (m = |E|). 3: for i = 1, . . . , m : 4: Add ei to T if it does not create a cycle. Otherwise, discard ei . 5: return T Remark: Kruskal’s algorithm can be generalized to the greedy algorithm for mimumum weight base in matroids. Theorem Kruskal algorithm outputs a MST in O(m log m) time, where m = |E|. 27 / 56
is k-vertex-connected if it remains connected after removing any vertex subset X ⊆ V with |X| ≤ k − 1. 1-vertex connected but NOT 2-vertex connected 2-vertex connected but NOT 3-vertex connected 31 / 56
remains connected after removing any edge subset F ⊆ E with |F| ≤ k − 1. 1-edge connected but NOT 2-edge connected 2-edge connected but NOT 3-edge connected 32 / 56
graph G = (V, E), s, t ∈ V Find: Maximum set of vertex-disjoint s–t paths. s t vertex-disjoint s–t paths Edge disjoint s–t paths problem Given: Connected graph G = (V, E), s, t ∈ V Find: Maximum set of edge-disjoint s–t paths. s t edge-disjoint s–t paths 33 / 56
let the cut of X be E[X, ¯ X] = {uv ∈ E : u ∈ X, v ̸∈ X}. • For s, t ∈ V , an s–t cut is a cut for X s.t. s ∈ X and t / ∈ X. X E[X, ¯ X] Observation Maximum number of s–t paths ≤ minimum size of s–t cut. It’s actually tight! (Menger’s theorem) 34 / 56
edge-disjoint s–t paths = Minimum size of s–t cut. min s–t cut (size = 2) s t Connection to edge-connectivity Corollary G is k-edge-connected ⇐⇒ |E[X, ¯ X]| ≥ k for ∅ ̸= ∀X ⊊ V ⇐⇒ G has at least k edge-disjoint s–t paths for any distinct s, t ∈ V 35 / 56
vertex-disjoint s–t paths = min{|U| : U ⊆ V seperating s and t}. Max s–t paths ≤ min |U| is trivial. Menger’s theorem says it’s actually tight! min s–t separating set (size = 2) s t Connection to vertex-connectivity Corollary G is k-vertex-connected ⇐⇒ G has at least k vertex-disjoint s–t paths for any distinct s, t ∈ V 36 / 56
is planar if G can be drawn on R2 without edge crossings. • Such a drawing is called a planar embedding or a plane graph. planar graph (K4 ) planar embedding 38 / 56
planar graph with n vertices, m edges, and f faces. Then n − m + f = 2. n = 8, m = 12, f = 6 Corollary A planar graph with n ≥ 3 vertices has at most 3n − 6 edges. A bipartite planar graph with n ≥ 3 vertices has at most 2n − 4 edges. 42 / 56
m = 10 > 3n − 6 m = 9 > 2n − 4 They are minimial non-planar graphs, i.e., removing any edge makes them planar. Observation If G contains K5 or K3,3 as a subgraph, then G is not planar. Indeed, they characterize planarity! (Kuratowski’s theorem) 43 / 56
single vertex (and removes loops and parallel edges). • Edge Deletion: “delete” an edge (but keeps its end vertices). • H is a minor of G if H can be obtained from G by a sequence of edge contractions and edge deletions. ↓ ↓ 45 / 56
Theorem (Wagner) A graph G is planar ⇐⇒ G contains neither K5 nor K3,3 as a minor. K5 and K3,3 are called the forbidden minors for planar graphs. 46 / 56
planar Toroidal Taken from: https://commons.wikimedia.org/wiki/File:Toroidal_graph_sample.gif Theorem (Robertson and Seymour) Any minor-closed graph family can be characterized by a finite number of forbidden minors. • Planar: K5 , K3,3 • Outer planar: K4 , K2,3 • Toroidal: unknown (at least 17,523 graphs) 47 / 56
E is called a matching if any two edges in M do not share a vertex. • A matching M is perfect if 2|M| = |V |, i.e., M covers all vertices. • A matching M is maximum if |M| ≥ |M′| for any matching M′. A perfect matching 49 / 56
in G is called an augmenting path if 1 edges in P alternate between M and E \ M; and 2 P starts and ends with vertices exposed by M. ∈ M / ∈ M |M| = 3 51 / 56
in G is called an augmenting path if 1 edges in P alternate between M and E \ M; and 2 P starts and ends with vertices exposed by M. ∈ M / ∈ M |M| = 3 ↓ flip |M| = 4 51 / 56
in G is called an augmenting path if 1 edges in P alternate between M and E \ M; and 2 P starts and ends with vertices exposed by M. ∈ M / ∈ M |M| = 3 ↓ flip |M| = 4 So, M is maximum =⇒ there is no augmenting path. 51 / 56
augmenting path. Take arbitrary matchings M, M′ s.t. |M| < |M′|. Then, the connected components of M + M′ consist of alternating paths and even cycles. Since |M| < |M′|, there must be an alternating path in M + M′ that starts and ends with vertices exposed by M. 52 / 56
; E). Definition A vertex subset (S1 , S2 ) is called a vertex cover if i ∈ S1 or j ∈ S2 for each edge ij ∈ E. Obviously, max M: matching |M| ≤ min (S1 , S2 ): vertex cover |S1 | + |S2 |. S1 S2 53 / 56
; E). Definition A vertex subset (S1 , S2 ) is called a vertex cover if i ∈ S1 or j ∈ S2 for each edge ij ∈ E. Obviously, max M: matching |M| ≤ min (S1 , S2 ): vertex cover |S1 | + |S2 |. Theorem (König–Egerváry) max M: matching |M| = min (S1 , S2 ): vertex cover |S1 | + |S2 |. S1 S2 53 / 56
C3 has maximum matchings of size 1 but minimum vertex covers are of size 2. Theorem (Tutte–Berge formula) max M: matching |M| = 1 2 min U⊆V (|U| − odd(G \ U) + |V |), where odd(G \ U) is the number of the connected components with odd vertices in G \ U. 55 / 56
tasusu
bernhardsvt
signer
matleenalaakso
yosukemurata
terahide
hachama
ponponmikankan
totodo713
phodgson
afnizarnur
speakerdeck
palkan
addyosmani
bermonpainter
bluesmoon
pauljervisheath
thekraken
cromwellryan
morganepeng
carmenintech
