Summary
Graphs and Network Theory Summary
- Course
- Institution
A summary on all the important things to know for a graphs and network theory course. Definitions and tests, functions, links between
[Show more]
Seller
Follow
georgiamersh124
Content preview
GRAPHS AND NETWORKSAcyclic
• a graph that contains no cycles, e.g. a tree (a connected, acyclic graph)
• trees are maximally acyclic (taking away any edge makes it not acyclic anymore)
• a forest is a disconnected acyclic graph
• G a tree ⟺ any 2 vertices in G are connected by a unique path ⟺ G is acyclic and
|𝐸| = |𝑉| − 1
• used to prove Euler’s Formula
• Grőtzsch
Adjacency Matrix
1 𝑖𝑓 {𝑖, 𝑗} ∈ 𝐸
• 𝐴 is a 𝑛 × 𝑛 matrix with entries 𝐴𝑖𝑗 = {
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
1 𝑖𝑓 𝑖 → 𝑗 ∈ 𝐸
• directed graphs: 𝐴𝑖𝑗 = {
0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
• multigraphs: 𝐴𝑖𝑗 = number of edges between 𝑖 and 𝑗
• 𝐴𝑛 = the matrix of n-step walks
• Perron-Frobenius
[𝐴3 ]
• Clustering: if 𝑑(𝑖) ≥ 2 then 𝐶(𝑖) = 𝑑(𝑖)(𝑑(𝑖)−1)
𝑖𝑖
• Kirchhoff’s Matrix Tree Theorem: 𝐷 the diagonal matrix, then 𝐿 = 𝐷 − 𝐴 has evalues:
1
𝜇1 ≥ ⋯ ≥ 𝜇𝑛−1 ≥ 𝜇𝑛 = 0 and the # of spanning trees of G is ∏𝑛−1𝑖=1 𝜇𝑖
𝑛
• bipartite: iff the spectrum of 𝐴 is symmetric about zero
𝜆 (𝐴)
• Hoffman: 𝒳(𝐺) ≥ 1 − 𝜆1 (𝐴) (largest and smallest evalues of 𝐴)
𝑛
Art Gallery Theorem
• polygon: a planar region bounded by 𝑛 straight edges (also called an 𝒏-gon)
• 𝑥 in a polygon 𝑃 sees 𝑦 in 𝑃 if the straight line 𝑥𝑦 is contained in 𝑃
𝑛
• AGT: no more than 3 points are required to jointly see the whole of an 𝑛-gon
Bipartite Graphs
• bipartite if 𝑉 can be a disjoint union 𝑉 = 𝑋 ∪ 𝑌, where 𝑋 ∩ 𝑌 = ∅, every edge is of the form
𝑒 = 𝑥𝑦, 𝑥 ∈ 𝑋, 𝑦 ∈ 𝑌
• complete bipartite: 𝐾𝑛,𝑚 has |𝑋| = 𝑛, |𝑌| = 𝑚 and every possible edge
• trees are bipartite
• a graph is bipartite iff it contains no cycles of odd length
• 𝐴 must have a spectrum that is symmetric about zero
• chromatic number: bipartite iff 𝒳(𝐺) ≤ 2
Chromatic Numbers
• 𝒳(𝐺) is the smallest 𝑘 such that G is 𝑘-colourable
• for all 𝑘 ≥ 3 ∃ graphs with chromatic # at least 𝑘 and girth at least 𝑘
• 𝒳(𝐺) ≤ 1 + max 𝛿(𝐻)
𝐻⊆𝐺
𝜆 (𝐴)
• Hoffman: 𝒳(𝐺) ≥ 1 − 𝜆1 (𝐴) (largest and smallest evalues of 𝐴)
𝑛
, Clustering Coefficients
• local clustering coefficient:
# 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣 # 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣
𝐶(𝑣) = # 𝑜𝑓 𝑝𝑎𝑖𝑟𝑠 𝑜𝑓 𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑠 𝑜𝑓 𝑣 = # 𝑜𝑓 𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝑣 + # 𝑜𝑓 𝑛𝑜𝑛−𝑡𝑟𝑖𝑎𝑛𝑔𝑙𝑒𝑠 𝑤𝑖𝑡ℎ 𝑚𝑖𝑑𝑑𝑙𝑒 𝑣
1
• mean clustering coefficient: 𝐶(𝐺) = |𝑉| ∑𝑣∈𝑉 𝐶(𝑣)
[𝐴3 ]
• if 𝑑(𝑖) ≥ 2 then 𝐶(𝑖) = 𝑑(𝑖)(𝑑(𝑖)−1)
𝑖𝑖
𝑁𝑐
• ER-I random graphs: 𝑀 = so that 〈𝑑〉 = 𝑐, as 𝑁 → ∞, 𝐶(𝑖) → 0 zero clustering
2
• Configuration models: 𝐶(𝐺) ~ 𝑁 −1
Contagion Threshold
• contagion process: where transmissibility 𝑇 ∈ [0,1], initially one vertex infected, one
chance to infect each neighbour, repeated until no further transmission
1
• contagion threshold - 𝑇𝑐 ≔ 𝜆 and 𝒉 = 𝑇𝑐 𝐻𝒉 the top evalue
𝑚𝑎𝑥(𝐻)
i. if 𝑇 < 𝑇𝑐 then 𝑟𝑖 = 0 for all 𝑖
ii. if 𝑇 = 𝑇𝑐 + 𝜀 for 𝜀 ≪ 1 then 𝑟𝑖 ∝ 𝜀 ∑𝑗~𝑖 ℎ𝑗𝑖
iii. if 𝑇 = 1 − 𝜀 for 𝜀 ≪ 1 then 𝑟𝑖 ≈ 1 − 𝜀 𝑑(𝑖)
• model networks: G a config. model r.g with degree dist 𝑝𝑑 with 𝑔(𝑥) = ∑𝑑 𝑥 𝑑 𝑝𝑑 and
ℎ(𝑥) = ∑𝑑 𝑥 𝑑 𝑞𝑑
1
• contagion threshold (model networks): 〈𝑇𝑐 〉 = ℎ′ (1) = (∑𝑑 𝑑𝑞𝑑 )−1
Critical Graphs
• 𝒌-critical: a 𝑘-colourable graph G is 𝑘-critical if 𝒳(𝐺) = 𝑘
• 𝐾𝑛 is n-critical
• if G is 𝑘-critical, then it is connected and 𝛿(𝐺) ≥ 𝑘 − 1
Crossing Number
• crossing number: the number of pairs of edges that share interior points
• 𝑐𝑟(𝐺) is the smalled crossing number possible in a plane drawing of 𝐺
• if 𝑐𝑟(𝐺) = 0 then 𝐺 is planar, and a plane drawing with no crossing is called a plane graph
𝑚 𝑚−1 𝑛 𝑛−1
• 𝑐𝑟(𝐾𝑛,𝑚 ) = ⌊ 2 ⌋ ⌊ ⌋ ⌊2⌋ ⌊ ⌋
2 2
4|𝐸|3
• for all 𝐺 with 𝑑(𝐺) > 8: 𝑐𝑟(𝐺) ≥
243|𝑉|2
• for all 𝐺 with |𝑉| ≥ 3, |𝐸| ≥ 3 : 𝑐𝑟(𝐺) ≥ |𝐸| − 3|𝑉| + 6
Definitions
• ALL IN NOTES
Degree distributions
1
• 𝑖=1 𝛿𝑑(𝑖),𝑑 [the fraction of vertices of degree d]
𝑝𝑑 = 𝑁 ∑𝑁
(𝑑+1)𝑝(𝑑+1)
• excess degree dist: 𝑞𝑑 ≔ if randomly chosen 𝑢~𝑣 then ℙ(𝑑(𝑣) = 𝑑 + 1) = 𝑞𝑑
𝑑(𝐺)
𝑁𝑐 𝑐 𝑑 𝑒 −𝑐
• ER-I random graphs: 𝑀 = so that 〈𝑑〉 = 𝑐, as 𝑁 → ∞, 𝑝𝑑 → Poisson degree dist
2 𝑑!
• configuration model: 𝒢(𝑁, 𝑑) has given degree sequence d, or degree dist 𝑝𝑑
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 georgiamersh124. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.12. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78600 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now