The Fibonacci Numbers And An Unexpected Calculation.

The Fibonacci Numbers And An Unexpected Calculation.

COMPSCI 230 Discrete Mathematics for Computer Science Graphs Whats a tree? A tree is a connected graph with no cycles

Tree Not aTree Not a Tree Tree How Many n-Node Trees? 1: 2:

3: 4: 5: Notation In this lecture: n will denote the number of nodes in a graph e will denote the number of edges in a graph Theorem: Let G be a graph with n nodes and e edges

The following are equivalent: 1. G is a tree (connected, acyclic) 2. Every two nodes of G are joined by a unique path 3. G is connected and n = e + 1 4. G is acyclic and n = e + 1 5. G is acyclic and if any two nonadjacent points are joined by adding a new edge, the resulting graph has exactly one cycle To prove this, it suffices to show

123451 1 2 1. G is a tree (connected, acyclic) 2. Every two nodes of G are joined by a unique path Proof: (by contradiction) Assume G is a tree that has two nodes connected by two different paths: Then there exists a cycle!

23 2. Every two nodes of G are joined by a unique path 3. G is connected and n = e + 1 Proof: (by induction) Assume true for every graph with < n nodes

Let G have n nodes and let x and y be adjacent G1 x y G2 Let n1,e1 be number of nodes and edges in G1

Then n = n1 + n2 = e1 + e2 + 2 = e + 1 3 43. G is connected and n = e + 1 4. G is acyclic and n = e + 1 Proof: (by contradiction) Assume G is connected with n = e + 1, and G has a cycle containing k nodes k nodes Note that the cycle has k nodes and k edges Starting from cycle, add other nodes and

edges until you cover the whole graph Number of edges in the graph will be at least n Corollary: Every nontrivial tree has at least two endpoints (points of degree 1) Proof: Assume all but one of the points in the tree have degree at least 2 In any graph, sum of the degrees =2e Then the total number of edges in the

tree is at least (2n-1)/2 = n - 1/2 > n - 1 How many labeled trees are there with three nodes? 1 2 3 1

3 2 2 1 3

How many labeled trees are there with four nodes? a c b d How many labeled trees are

there with five nodes? 5 labelings 3 4 5 2 2

labelings labelings 4 5 3 125 labeled trees

How many labeled trees are there with n nodes? 3 labeled trees with 3 nodes 16 labeled trees with 4 nodes 125 labeled trees with 5 nodes nn-2 labeled trees with n nodes Cayleys Formula The number of labeled trees on n nodes is nn-2

The proof will use the correspondence principle Each labeled tree on n nodes corresponds to A sequence in {1,2,,n}n-2 (that is, n-2 numbers, each in the range [1..n]) How to make a sequence from a tree?through i from 1 to n-2 Loop Let L be the degree-1 node

with the lowest label Define the ith element of the sequence as the label of the node adjacent to L Delete the node L from the tree Example: 5 1 8 4

3 2 6 1 3 3 4 4 4 7 How to reconstruct the unique tree

from a sequence S: Let I = {1, 2, 3, , n} Loop until S is empty Let i = smallest # in I but not in S Let s = first label in sequence S Add edge {i, s} to the tree Delete i from I Delete s from S Add edge {a,b}, where I = {a,b} S:

1 3 3 4 4 4 I: 1 2 3 4 5 6 7 8 5 1 8

4 3 2 6 7 Spanning Trees A spanning tree of a graph G is a tree that

touches every node of G and uses only edges from G Every connected graph has a spanning tree A graph is planar if it can be drawn in the plane without crossing edges Examples of Planar Graphs

= Faces A planar graph splits the plane into disjoint faces 4 faces Eulers Formula If G is a connected planar graph

with n vertices, e edges and f faces, then n e + f = 2 Rather than using induction, well use the important notion of the dual graph Dual = put a node in every face, and an edge between every adjacent face Let G* be the dual

graph of G Let T be a spanning tree of G Let T* be the graph where there is an edge in dual graph for each edge in G T Then T* is a spanning tree for G* n = eT + 1 n + f = eT + eT* + 2 =e+2

f = eT* + 1 Corollary: Let G be a simple planar graph with n > 2 vertices. Then: 1. G has a vertex of degree at most 5 2. G has at most 3n 6 edges Proof of 1 (by contradiction): In any graph, (sum of degrees) = 2e Assume all vertices have degree 6 Then e 3n Furthermore, since G is simple, 3f 2e

So 3n + 3f 3e, 3n + 3f = 3e + 6, and 3e + 6 3e Graph Coloring A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same color Graph Coloring Arises surprisingly often in CS Register allocation: assign temporary

variables to registers for scheduling instructions. Variables that interfere, or are simultaneously active, cannot be assigned to the same register Theorem: Every planar graph can be 6colored Proof Sketch (by induction): Assume every planar graph with less than n vertices can be 6-colored Assume G has n vertices Since G is planar, it has some

node v with degree at most 5 Remove v and color by Induction Hypothesis Not too difficult to give an inductive proof of 5-colorability, using same fact that some vertex has degree 5 4-color theorem remains challenging! Implementing Graphs Adjacency Matrix

Suppose we have a graph G with n vertices. The adjacency matrix is the n x n matrix A=[aij] with: aij = 1 if (i,j) is an edge aij = 0 if (i,j) is not an edge Good for dense graphs! Example 0 A= 1 1

1 1 0 1 1 1 1 0 1

1 1 1 0 Counting Paths The number of paths of length k from node i to node j is the entry in position (i,j) in the matrix Ak 0

A2 = 1 1 1 1 0 1 1 1 1

0 1 1 1 1 0 3 = 2 2

2 2 3 2 2 2 2 3 2

2 2 2 3 0 1 1 1

1 0 1 1 1 1 0 1 1

1 1 0 Adjacency List Suppose we have a graph G with n vertices. The adjacency list is the list that contains all the nodes that each node is adjacent to Good for sparse graphs!

Example 1 3 2 4 1:

2: 3: 4: 2,3 1,3,4 1,2,4 2,3 Trees Counting Trees

Different Characterizations Planar Graphs Definition Eulers Theorem Coloring Planar Graphs Heres What You Need to Know

Adjacency Matrix and List Definition

Recently Viewed Presentations

  • Program Evaluation: What Method Works for You?

    Program Evaluation: What Method Works for You?

    Adapting Evidence-Based Practices to Meet the Mental Health Needs of Immigrant and Refugee Communities Olga Acosta Price, George Washington University Mark Sander, MN Public Schools/Hennepin County Joshua Kaufman, LA Unified School District
  • Presentation Name

    Presentation Name

    (For example, a vocabulary activity is extended to draw attention to some syntactic patterning.) Types of material adaptation rewriting/modification : teacher may occasionally decide to rewrite material, especially exercise material, to make it more appropriate, more "communicative", more demanding, more...
  • CYSTIC FIBROSIS - Oregon High School

    CYSTIC FIBROSIS - Oregon High School

    How do we explain: great diversity of organisms? organisms that are well-adapted to their environment? similarities and relationships of organisms (all use same basic genetic information)? Jean-Baptiste Lamarck (1744-1829) Inheritance of Acquired Characteristics - Traits developed during your life can...
  • Simulated Life Test System Team 8

    Simulated Life Test System Team 8

    Design Considerations Temperature Chamber GDO Variable Voltage Supply +24V DC 16V Regulator 14.5V Regulator 9V Regulator Solid State Relay GDOs Solid State Relay Solid State Relay TTL Control Inputs Test Control Design Challenges Summary * * Setup Considerations ... Try...
  • CHAPTER 24 THE ORIGIN OF SPECIES Different Species

    CHAPTER 24 THE ORIGIN OF SPECIES Different Species

    Temporal changes in development that differ between species--heterochrony Homeosis = alteration in basic body design controlled by small sets of gene in developmentā€”homeotic genes (Hox complex) Evolution is not goal-oriented--species selection produces an evolutionary trend * * Darwin recognized that...
  • Reframing Environmental Health:

    Reframing Environmental Health:

    On the left side is the original introductory paragraph of the second swamp drop we just saw. On the right is a reframed version of it. Left side cues up health individualism by focusing on household-level (smoking, pets, dust), individual...
  • Deserts - kaimhill.aberdeen.sch.uk

    Deserts - kaimhill.aberdeen.sch.uk

    What is a desert? - A desert is only called a desert if it gets 10 inches of rain in a year.-Deserts are very dangerous because there is not much water.
  • 15_Roy - IPPC

    15_Roy - IPPC

    a. to support the Member Governments in their aim of assuring plant health, while preserving human and animal health and the environment b. to pursue and develop, by cooperation between the Member Governments, the protection of plants and plant products...