Loading...
Discussion 2A
1. Graph Basics
graph
:
G
=
(
V
,
E
)
G = (V, E)
G
=
(
V
,
E
)
consists of vertices
V
V
V
connected by edges
E
E
E
directed
: edges have directions
connected
: there is a path between any two vertices
adjacent
/
neighboring
: two vertices with an edge between them
degree
: number of edges on a vertex in an undirected graph
indegree
/
outdegree
: number of edges going into and out of a vertex, respectively, in a directed graph
path
: sequence of edges connected by endpoints
in this class paths are
simple paths
, which means vertices are not reused
cycle
: path that begins and ends on same vertex
walk
: sequence of edges connected by endpoints, which can be repeated
tour
: walk that begins and ends on same vertex
2. Planarity
planar
: a graph that can lie on a plane without edges crossing
complete graph
:
K
n
K_n
K
n
graph on
n
n
n
vertices where an edge exists between every pair
K
1
K_1
K
1
,
K
2
K_2
K
2
,
K
3
K_3
K
3
, and
K
4
K_4
K
4
are planar
K
5
K_5
K
5
is not planar
complete bipartite graph
:
K
m
,
n
K_{m,n}
K
m
,
n
is a bipartite graph where an edge exists between every pair of vertices on different sides
K
3
,
3
K_{3,3}
K
3
,
3
is not planar
(it
can be drawn on a donut without edges crossing)
A graph containing
K
5
K_5
K
5
or
K
3
,
3
K_{3,3}
K
3
,
3
is not planar
3. Bipartite Graph
Proof Structure
b
i
p
a
r
t
i
t
e
⇒
n
o
t
o
u
r
s
o
f
o
d
d
l
e
n
g
t
h
\text{bipartite} \Rightarrow \text{no tours of odd length}
bipartite
⇒
no tours of odd length
prove that if there is a tour, then it must have even length
n
o
t
o
u
r
s
o
f
o
d
d
l
e
n
g
t
h
⇒
b
i
p
a
r
t
i
t
e
\text{no tours of odd length} \Rightarrow \text{bipartite}
no tours of odd length
⇒
bipartite
prove that you can partition the vertices into two sets
L
L
L
and
R
R
R
such that within in each set, there are no edges
Please turn on JavaScript to use Paper in all of its awesomeness. ^_^
1. Graph Basics
2. Planarity
3. Bipartite Graph
Proof Structure