Module 11 Vocab Flashcards
Undirected Graph (notation)
11.1
G = (V, E)
V = vertices/nodes and E = edges
Undirected Graph (words)
11.1
A pair of finite sets
first set represents vertices/nodes
second set represents edges
Vertices/Nodes
11.1
V: finite, non-empty set of vertices/nodes
.
Edges (notation)
11.1
E ⊆ 2^v
Edges (definition)
11.1
set of nodes of cardinality 2
Edges (words)
11.1
finite (possibly empty) set of edges consisting only of subsets of cardinality 2
Edges and Incident
11.1
Each edge is incident to exactly two vertices
If V = {1, 2, 3} how many possible edges can graph G have?
11.1
3 edges:
{1, 2} {1, 3} {2, 3}
u - v or v-u
11.1
represents the edge for {u, v}
tells us that u and v are linked by an edge
Vertices and u and v are — by —
11.1
linked
an edge
Incident
11.1
the edge is incident to its endpoints (vertices)
“the edge u-v is incident to u and v”
Adjacent/Neighbors
11.1
two vertices that share an edge
Ex: u-v are adjacent
Degree
11.1
degree of a vertex:
the number of neighbors of a vertex
Degree (notation)
11.1
deg(u)
the number of vertices adjacent to u
Isolated
11.1
a vertex of degree 0
no neighbors
Handshaking Lemma
11.1
the sum of the degrees of all nodes in a graph is twice the number of edges
Handshaking Lemma (notation)
11.1
Σ{v∈V} deg(v) = 2|E|
add up the degrees of all the nodes and it’s equal to 2 times the number of edges
11.1
Handshake Lemma
In the handshake lemma, what does every part of the metaphor represent?
11.1
people: nodes/vertices
number of people each person shakes hands with: degrees
handshake: edge
Handshake Lemma (proof)
11.1
since each edge is incident to exactly two vertices, each edge contributes two to the sum of degrees of the vertices
Number of vertices of odd degree proposition
11.1
in any graph there are an EVEN number of vertices of odd degree
Even number of vertices with odd degree proof
11.1
Σ{v∈V} deg(v) = Σ{v∈V_e} deg(v) + Σ{v∈V_o} deg(v)
LHS: handshaking RHS: rule of thumb
In the graph G = (V, E) all vertices have degree 1. How many vertices can G have?
11.1
since every vertex has 1 degree,
sum of all degrees = |V|
handshake says: |V| = 2|E|
so must have even number of vertices
What are two ways you can calculate the sum of degrees?
11.1
way 1: add degrees of all vertices
way 2: count edges and multiply by 2
G = (V, E) and all vertices have an even degree. Can G have as many vertices as we wish?
11.1
Yes with an endless graph where each of the n vertices has 0 edges (and thus 0 degree) since 0 is even
Edgeless Graphs
11.2
some vertices and no edges
|V| ≥ 1
E = ∅ and |E| = 0
Complete Graphs (notation)
11.2
K_n = (V, E) where |V| = n
and E = {{u,v} | u,v ∈ V u≠v}
Complete Graphs
11.2
- has edges between any two vertices
- has the maximum number of edges
- no isolated vertices
Complete Graphs (# of edges)
11.2
(n choose 2)
Path Graphs (notation)
11.2
P_n where there are n≥1 vertices
Path Graphs (# of edges)
11.2
n-1
Path Graphs
11.2
vertices are arranged “in a row”
for n≥2, 2 vertices have degree 1 (endpoints) and all other vertices have degree 2
Cycle Graphs (notation)
11.2
C_n where n≥1 vertices
Cycle Graphs (# of edges)
11.2
n = # of vertices = # of edges
Cycle Graphs
11.2
vertices are arranged “in a circle”
all vertices have degree 2
Note: C_1 and C_2 are not defined
Grid Graphs (notation)
11.2
m x n
m = # of rows
n = # of vertices
m,n ≥ 1
Grid Graphs (number of edges)
11.2
2mn - m - n
Grid Graphs
11.2
each vertex is linked by an edge to the vertices “closest” to it
Grid Graphs (# of vertices)
11.2
mn vertices
If all vertices in a graph G have degree 2, must G be a cycle graph?
11.2
No!
but it’s essentially made up of two (or more) cycles
Walks
11.3
a non-empty sequence of vertices consecutively linked by edges
Walks (notation)
11.3
u0 — u1— ··· — uk
Endpoints
11.3
u0 and uk of the walk
u0 — u1— ··· — uk
Connected
11.3
u0 and uk are connected by the walk
u0 — ··· — uk
Length
11.3
number of edges of the wal(k)
Paths
11.3
a walk with distinct vertices
walks of length 0 or 1 are also paths
ex: 1- 2 - 4 NON-ex: 1 - 2 - 3 - 4 - 2 - 5
Well-Ordering Principle
11.3
every non-empty set of natural numbers has a least element (smallest element)
Walk-Path Proposition I
11.3
for any walk, length n≥3 with distinct endpoints, there is a path with length ≤ n
Walk-Path Proposition I Implies
11.3
the shortest walk connecting u0 to un must be a path
Why is the shortest walk a path?
11.3
cut off the cycle from the walk and replace it with a node (walk length 0)
Walk-Path Proposition II
11.3
if there is a walk, with length n≥3 and distinct endpoints, there is a path whose sequence of nodes and edges is a subsequence of the sequence of nodes and edges of the walk
*subsequence preserves order but doesn’t have to be consecutive
What’s the maximum length of a path in Cn? In Kn?
11.3
Cn = cycle = n-1
Kn = complete = n-1
If u∈C1 and v∈C2 and u— ··· — v and C2 is maximally connected, why must u∈C2?
11.4
Since u is connected to v, C2 must incldue vertex u. If u wasn’t in C2, then there would be a bigger set of vertices C’ (C2 plus the element u) for which any two vertices are connected and thus C2 wouldn’t be maximally connected.
Connected (notation)
11.4
u — ··· — v
Connected (definition)
11.4
two vertices, u and v, are connected if there exists some walk/path with endpoints u and v
Connectivity Relaion
11.4
— ··· —
Reflexive (notation)
11.4
u — ··· — u
Reflexive (words)
11.4
a vertex is connected to itself by a walk/path of length 0
Symmetric (notation)
11.4
if u— ··· —v, then v— ··· —u
Symmetric (words)
11.4
if u is connected to v, then v is connected to u
Transitive (notation)
11.4
if u— ··· —v and v— ··· —w, then u— ··· —w
Transitive (words)
11.4
if u is connected to v and v is connected to w, then u is connected to w
think: concatenate
Concatenating walks and paths
11.4
the concatenation of walks is also a walk BUT the concatenation of paths need not be a path
Can A⟂A?
11.4
nope, impossible
justification: A∩A ≠ A x A
Connected Component
11.4
a set of vertices C∈V
1) any two vertices in C are connected
2) there is no strictly bigger set of vertices such that any two vertices of C’ are connected
Maximally Connected
11.4
set that contains all the vertices that are connected
(no other set contains more of the connected vertices)
ex: {1,2,4} vs. {1, 2, 3, 4}
Partition Proposition
11.4
any two distinct connected components are disjoint
(even if its just by itself)
Connected Graph
11.4
has exactly one connected component
ex: complete, path, cycle, mxn
Disconnected Graph
11.4
has two or more connected components
ex: edgeless (more than 1)
Distance
11.4
the length of the shortest path between two vertices
“Degree of separation”
11.4
(in social networks)
the number of intermediate nodes on the shortest path
ex: 6 degrees of separation = graph distance 7
Shortest Path
Self
in an mxn grid graph, every path of mininum length from (0,0) to (n-1, m-1) has length m+n-2 and traverses edges only upwards or rightwards
