Week 12
Adjacency Matrix, A(G) vs Incidence Matrix, I(G).
Let G=<N,L> a graph on |N| nodes having |L| lines.
example: G=K3
A(G) = [[0,1,1],[1,0,1],[1,1,0]]
I(G) = [[1,2],[0,2],[0,1]]
Space and time issues.
Algorithms for calculating degree of node -- time complexity using A(G) versus I(G)
Algorithm for determining two-colorability of node. Assume connected graph (why?). Start at any node, q. for all nodes p in N, calculate
distance (q,p). Run time of this process? How to color nodes based on distance? How to show that this algorithm two colors any 2-colorable graph and fails for any graph for which chromatic number x(G) is greater than two.
Use cross-over graph to reduce 3-colorability to 3-colorability of planar graphs.
How to color a planar regular graph (start with connected graph-- why?).
1-regular
2-regular
3-regular (Brooks' theorem)
6-regular
Reduction of 3-colorability of planar graphs to 3-colorability of planar four-regular graphs.
Σ: an alphabet is a set of characters Σ = { a1, a2, a3, ..., an } where n = |Σ| .
Σ* is the set of all strings (including the empty string) that can be formed by elements of Σ.
L , a language over Σ, is defined as any specified subset of Σ* .
A grammar for L is a system for "producing" strings of L.
A machine M is a function that recognizes statements of L. That is, for all α in Σ* , M(α) =1 if α is in L and is 0 otherwise.
Homework: (due Monday April 27th)
Build a program that takes any graph as input, and either produces a 2-coloring or answers that none exists.
2nd Quiz: Wednesday April 22nd -- everything covered to date.
Homework (due Monday April 27th) :
1. construct a finite state automaton to recognize the language consisting of exactly those strings that begin with a 1, end with a zero, and have an even number of 0's. Examples: 100, 10111000, 10000. Nonexamples : 10010, 00, 10010100
2. construct a grammar that produces the same language.