discrete math 2 exam 3

planar drawing

graph in which the polygonal arcs corresponding to two edges intersect only at a point corresponding to which they are both incident

face

region bounded by edges and vertices and not containing any other vertices

euler’s formula

let G be a connected planar graph with n vertices and m edges. every planar drawing of G has f faces where f satisifes n-m+f=2.

a planar graph on n vertices has at most ___ edges when n>=3

3n-6

two graphs G_1 and G_2 are homeomorphic if

they can be obtained from the same graph by a sequenced of elementary subdivisions where vertices of edges are replaced by paths

kuratowski’s theorem

a graph is planar if and only if it does not contain a subgraph homeomorphic to either K_5 or K_3,3.

girth

length of the shortest cycle in the graph. 2m>= gf

4 color theorem

every planar grpah has chromatic number at most 4.

gallery

polygonal region in the plane

camera position

point in the polygon (art gallery)

if we have a convex polygon, we need __ camera(s)

1 camera needed

how do we guard an art gallery

for a non-convex polygon, we decompose P into pieces that are easy to guard, namely into triangles by drawing diagonals that connects two vertices of P and lies in the interior of P

triangulation

decomposition of a polygon into triangles by a maximal set of non-intersecting diagonals

every simple polygon admits a triangulation, and any triangulation of a simple polygon with n vertices consists of exactly ___ triangles

n-2

art gallery theorem

for a simple polygon with n vertices, floor(n/3) cameras are occasionally necessary and always sufficient to have every point in the polygon visible from at least one of the cameras.

pick’s theorem

i + b/2 - 1 = A(P)

voronoi diagram

a partition of a plane into regions close to each of a given set of sites

if all sites are ____, Vor(P) consists of ___ parallel lines. otherwise, Vor(P) is connected and its edges are ____

collinear, n-1, line segments or half lines.

convex

any pair of points p,q \in S \overline{pq} is completely contained in S

convex hull (CH(S))

is the smallest convex set that contains S; the intersection of all convex sets that contains S

coloring of a graph G with k>= 1 colors is a

function f: V(G) → {1,2,…,k}

proper coloring

if f(x)≠f(y) for any adjacent vertices x and y

the chromatic number of a graph G

smallest k such that G has a proper coloring with k colors and is denoted by chi(G)

let G be a graph. G is bipartite iff contains ____ and iff the chromatic number of G is __

no odd cycles, 2

how do we set lower bounds for a chromatic number?

clique <= chromatic number

clique

largest complete subgraph of G

independence number

largest number of vertices that are pairwise non adjacent

lower bound using independence number

chi(G) >= |V(G)/ind(G)|

color critical (k-critical) if

chi(G) = k and chi(H) < k for any proper subgraph H of G