Graph Theory Fundamentals
Graph
Theory
and
Complex
Networks
by
Maarten
van Steen
What is a planar embedding?
http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/planar_plane_straight_line.png
K
4
drp.math.umd.edu/Project-Slides/Characteristics of Planar Graphs.pptx
Kuratowski’s Theorem (1930)
A graph is planar if and only if it does not
contain a subdivision of K
5
or K
3,3
.
http://www.math.ucla.edu/~mwilliams/pdf/petersen.pdf
Kuratowski Subgraphs
K
5
K
3,3
http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/k_5_and_k_3_3.png
http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g83.gif
http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g82.gif
Kuratowski Subgraphs
What is a subdivision?
Euler characteristic (simple form):
= number of vertices – number of edges + number of faces
Or in short-hand,
= |V| - |E| + |F|
where V = set of vertices
E = set of edges
F = set of faces = set of regions
& the notation |X| = the number of elements in the set X.
For a planar connected graph
|V| - |E| + |F| = 2
Defn: A
tree
is a connected graph that does
not
contain a cycle.
A
forest
is a graph whose components are trees.
Lemma 2.1: Any tree with
n
vertices has
n-1
edges.
χ
= 8 – 7 + 1 = 2
χ
= 8 – 8 + 2 = 2
χ
= 8 – 9 + 3= 2
= 1 – 0 + 1 = 2
= 2 – 1 + 1 = 2
= 3 – 2 + 1 = 2
= 4 – 3 + 1 = 2
= 5 – 4 + 1 = 2
= 8 – 7 + 1 = 2
= 8 – 8 + 2 = 2
Not a tree.
= 8 – 9 + 3 = 2
Not a tree.
For the brave of heart, consider graphs drawn
on other surfaces such as a torus or Klein bottle.
For fun, see
http://youtu.be/Q6DLWJX5tbs
or
www.geometrygames.org
.
Euler’s fomula:
For a planar connected graph
|V| - |E| + |F| = 2
where V = set of vertices, E = set of edges, F = set of faces = set of
regions
Defn:
A
tree
(or
acyclic graph
) is a connected graph that does
not
contain a cycle.
A
forest
is a graph whose components are trees.
Lemma 2.1:
Any tree with
n
vertices has
n-1
edges.
Thm 2.9:
For any connected planar graph with |V| ≥ 2,
|E| ≤ 3|V| - 6
Cor 2.4:
K
5
is nonplanar.
Thm 2.10:
K
3,3
is nonplanar.
Cor:
A graph is planar if and only if it does not contain a subdivision of
K
5
or K
3,3
.
Delve into the basics of graph theory with topics like graph embeddings, graph plotting, Kuratowski's theorem, planar graphs, Euler characteristic, trees, and more. Explore the principles behind graphs, their properties, and key theorems that define their structure and connectivity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Drawing a graph http://mathworld.wolfram.com/GraphEmbedding.html
https://reference.wolfram.com/language/ref/GraphPlot.html Graph Theory and Complex Networks by Maarten van Steen
Graph Theory and Complex Networks by Maarten van Steen
https://proxy.duckduckgo.com/ip3/drp.math.umd.edu.ico drp.math.umd.edu/Project-Slides/Characteristics of Planar Graphs.pptx What is a planar embedding? K4 http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/planar_plane_straight_line.png
Kuratowskis Theorem (1930) A graph is planar if and only if it does not contain a subdivision of K5 or K3,3. http://www.math.ucla.edu/~mwilliams/pdf/petersen.pdf
Kuratowski Subgraphs K5 K3,3 http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/figs/k_5_and_k_3_3.png What is a subdivision? Kuratowski Subgraphs http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g83.gif http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/Diagrams/g82.gif
Euler characteristic (simple form): = number of vertices number of edges + number of faces Or in short-hand, = |V| - |E| + |F| where V = set of vertices E = set of edges F = set of faces = set of regions & the notation |X| = the number of elements in the set X. For a planar connected graph |V| - |E| + |F| = 2
Defn: A tree is a connected graph that does not contain a cycle. A forest is a graph whose components are trees. = 8 7 + 1 = 2 = 8 8 + 2 = 2 = 8 9 + 3= 2 Lemma 2.1: Any tree with n vertices has n-1 edges.
= |V| |E| + |F| = 1 0 + 1 = 2
= |V| |E| + |F| = 2 1 + 1 = 2
= |V| |E| + |F| = 3 2 + 1 = 2
= |V| |E| + |F| = 4 3 + 1 = 2
= |V| |E| + |F| = 5 4 + 1 = 2
= |V| |E| + |F| = 8 7 + 1 = 2
= |V| |E| + |F| = 8 8 + 2 = 2 Not a tree.
= |V| |E| + |F| = 8 9 + 3 = 2 For the brave of heart, consider graphs drawn on other surfaces such as a torus or Klein bottle. For fun, see http://youtu.be/Q6DLWJX5tbs or www.geometrygames.org. Not a tree.
Eulers fomula: For a planar connected graph |V| - |E| + |F| = 2 where V = set of vertices, E = set of edges, F = set of faces = set of Defn: A tree (or acyclic graph) is a connected graph that does not contain a cycle. regions A forest is a graph whose components are trees. Lemma 2.1: Any tree with n vertices has n-1 edges. Thm 2.9: For any connected planar graph with |V| 2, |E| 3|V| - 6 Cor 2.4: K5 is nonplanar. Thm 2.10: K3,3 is nonplanar. Cor: A graph is planar if and only if it does not contain a subdivision of K5 or K3,3.
