class2.txt

Planar Graphs

Ex:
5 nodes
6 edges
3 regions

For any planar graph:
nodes - edges + regions = 2


edges <= 3*nodes - 6 (if we have at least 3 edges) (for planar graphs)

This is not true for complete graphs, where every node has an edge to every other node.



7.
#
# How many edges in a complete graph on n nodes? (n*(n-1))/2
# (quadratic)

def clique(n):
    # Return the number of edges
    # Try to use a mathematical formula...
    return (n*(n-1))/2

print clique(6)




HYPERCUBE GRAPHS

number of nodes needs to be a power of 2

every node is a bit pattern. only connect nodes that differ in 1 bit

nodes are n*log(n) edges (it's actually 0.5n*log(n), but in big theta we can ignore the 0.5)

in a hypercube every node has log(n) edges coming out of it (base 2) , so the degree of every node is log(n)






RECAP

Recurrence              graphs              edge growth
T(n) = 2T(n/2)+1        tree                O(n)
                        chain

T(n) = 2T(n/2)+O(n^2)   clique              O(n^2)
                        dense graph
                        
T(n) = 2T(n/2) + O(n)   hypercube           O(nlogn)
                        tangled hypercube
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
                        
HOMEWORK

1.
# Write a program that returns the number of edges
# in a star network that has `n` nodes 
#

def star_network(n):
    # return number of edges
    return n-1
    
    
    
    
    
    
7.

# Generate a combination lock graph given a list of nodes
#

def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = {}
    G[node1][node2] = 1
    if node2 not in G:
        G[node2] = {}
    G[node2][node1] = 1
    return G

def create_combo_lock(nodes):
    G = {}
    make_link(G, nodes[0], nodes[1])
    for i in range(2, len(nodes)):
        make_link(G, nodes[i-1], nodes[i])
        make_link(G, nodes[0], nodes[i])
    return G

print create_combo_lock([1, 2, 3, 4, 5])

##############
# Code for testing
#
def is_chain(graph, nodes):
    # find the first node with degree one
    start = (n for n, e in graph.iteritems() if len(e) == 1).next()
    count = 1
    # keep track of what we've seen to make
    # sure there are no cycles
    seen = set([start])
    # follow the edges
    prev = None
    current = start
    while True:
        nexts = graph[current].keys()
        # get rid of the edge back to prev
        nexts = [n for n in nexts if not n == prev]
        if len(nexts) > 1:
            # bad.  too many edges to be a chain
            return False
        elif len(nexts) == 0:
            # We're done following the chain
            # Did we get enough edges:
            return count == len(nodes)
        prev = current
        current = nexts[0]
        if current in seen:
            # bad.  this isn't a chain
            # it has a loop
            return False
        seen.add(current)
        count += 1

def is_combo_lock(graph, nodes):
    # first see if we have a star
    center = None
    degree = None
    for node, edges in graph.iteritems():
        if len(edges) > degree:
            center = node
            degree = len(edges)
    if not degree == len(nodes) - 1:
        return False
    # make a graph out of all the edges
    # not connected to the center
    chain = {}
    for node, edges in graph.iteritems():
        if node == center:
            continue
        for e in edges:
            if e == center:
                continue
            make_link(chain, node, e)
    return is_chain(chain, [n for n in nodes if n != center])

def test():
    for n in [5, 10, 20]:
        combo = create_combo_lock(range(n))
        if not is_combo_lock(combo, range(n)):
            return False
    return True