Module 12 Vocab Flashcards
Graph Isomorphism (notation)
12.1
G1 ≃ G2
Graph Isomorphism (definition)
12.1
bijection β: V1 → V2
such that for any u1v1 ∈ V1 we have
u1—v1∈E1 iff β(u1)—β(v1)∈E2
Graph Isomorphism (words)
12.1
match up the vertices based on their degree
How to write isomorphism
12.1
G1 ≃ G2 by the bijection
4→5, 2→6, 3→8, 1→7
Isomorphism Proposition I
12.1
ex path
any 2 complete/path/cycle/edgeless graphs are isomorphic iff they have the same number of vertices
Isomorphism Proposition II
12.1
ex grid
any 2 mxn grids are isomorphic, as well as isomorphic to any nxm grids
Isomorphism Proposition III
12.1
ex complete
any permutation of n vertices in Kn is n isomorphism
Subgraph (intuitive)
12.1
the part of a graph that can be in its own right, a graph
Subgraph (definition)
12.1
G1 is a subgraph of G2
when V1⊆V2 and E1⊆E2
if it actually makes a graph
(beware pointless edges)
Induced Subgraphs
12.1
the subgraph of G induced by V’∈V
is the graph G’ = (V’, E’)
where E’ consists of all the edges of G whose endpoints are both in V’
Counting Paths
12.1
to count paths of length n(edges),
count the subgraphs that are path graphs on n+1 vertices
Paths of length 2 in Cn
12.1
n paths of length 2 in Cn
Sujective
12.1
range = whole codomain
ex: every vertex fits some characteristic
Bijective
12.1
every element maps to a distinct element
ex: only maps to one path
Bijection Rule
12.1
|A| = |B|
domain = codomain
Closed Walk
12.2
walk where first and last vertex are the same
Cycle
12.2
closed walk of length ≥ 3 (edges)
in which all nodes are pairwise disjoint
except for the last/first
reminder: 4 nodes total for mininum 1-2-3-1
1-2-3-4-2-1
12.2
closed walk
(2 twice)
2
12.2
closed walk of length 0
2-3-4-2
12.2
cycle length 3
Counting Cycles
12.2
to count cycles of length n,
count subgraphs that are cycle graphs
on n vertices
How many cycles are there in K4?
12.2
length 3: 4 choose 3
length 4: induce last node from node 1, 3 choose 2
Cycle of length 3
(of Kn)
12.2
“the subgraph induced by any 3 vertices is a cycle subgraph”
n choose 3
Cycle of length 4
(of Kn)
12.2
step 1: pick 4 nodes
step 2: multiply by 3 (3 choose 2)
What is the total number of cycles in K5?
12.2
37
cc Partition
12.3
cc’s partition the set of vertices V
as well as the set of edges E
we can view — as — induced by a set of —
12.3
cc’s
subgraphs
vertices
Edge Partition Proposition
12.3
every edge {u,v}∈E belongs to
exactly one of the subgraphs
induced by the cc’s of G
cc’s as graphs proposition
12.3
to count the # of paths/cycles of length k
we add up the # of paths/cycles in each of its cc’s
Acyclic
12.3
a graph in which there are no cycles
Tree
12.3
a graph that is both connected and acyclic
Forest
12.3
an acyclic graph,
since all its cc’s are trees
3 Isomorphism Propositions
12.3
if G1 ≃ G2, then
G1 is acyclic iff G2 is acylic
G1 is connected iff G2 is connected
G1 is a tree iff G2 is a tree
Edges in Trees Proposition
12.3
a tree has one more vertex than edges
if tree, then |E| = |V| - 1
Edges in Forrests Corollary
12.3
the sum of a forrest’s edges is the difference between its nodes and cc’s
if forest, |E| = |V| - |CC|
Vertices in Trees Propositions
12.3
any tree with n vertices has n-1 edges
Leaf
12.3
a node of degree 1
Leaf Lemma I
12.3
every tree with edges has at least one leaf
Leaf Lemma II
12.3
removing a leaf from a tree with edges leaves again a tree
*removing a leaf means also removing its one incident edge
Maximally Connected Tree Proposition
12.4
removing any edge in a tree disconnects it
Maximally Acyclic Tree Proposition
12.4
adding an edge between any two non-adjacent vertices in a tree creates a cycle
Unique-Path Connected Tree Proposition
12.4
any two distinct vertices of a tree are connected by one unique path
Edge in Acyclic Graph Lemma
12.4
adding an edge to an acyclic graph creates at most one cycle
Cycle in Closed Walk Lemma
12.4
any closed walk of non-zero length that traverses at least one of its edges exactly once contains a cycle
Unique Path Connectivity Proposition
12.4
a graph such that any two distinct vertices are connected by a (1) unique path must be a tree
Cut Edge
Self
an edge that if removed gives us a graph with strictly more cc’s
Cut Edge Proposition
Self
removing a cut edge increases the number of cc’s by exactly 1
