1 Lesson 12 – 3 Directed GraphsPg. 616 #1–5, 7, 9, 11, 15, 17–20, 22–32 Lesson 12 – 3 Directed Graphs Pre-calculus Objective To create adjacency matrices for finite/directed graphs.

2 Learning Objective To create adjacency matrices for finite/directed graphs.

3 A finite graph is a set of points, called nodes, connected by a set of lines, called edges.We can represent the graph in an adjacency matrix. If the nodes are connected, you place a 1 in the matrix n2 1. n1 n3 TO: n4 𝑛 1 𝑛 2 𝑛 3 𝑛 4 𝑛 1 1 1 FROM: 𝑛 2 1 1 1 𝑛 3 1 1 𝑛 4 1

4 A finite graph may need to include info about direction.Directed Graph We get a directed graph. *Flights work this way. From Long Beach to Orlando on Jet Blue

5 Directed Graph 2. Create the adjacency matrix Chicago New YorkSt. Louis TO: 𝐶 𝑁 𝑆 𝐶 1 1 FROM: 𝑁 1 𝑆 1 1

6 3. What options do you have if you are making 2 flights?Directed Graph Chicago New York St. Louis You would have the same matrix, but there would be two of them. TO: FROM 𝐶 𝑁 𝑆 𝑥 𝐶 = 𝑁 𝑆

7 Directed Graph A= 0 1 1 1 0 0 1 1 0 Want [𝐴] 2 = 2 1 0 0 1 1 1 1 1If we continued this, it would be a lot of multiplying. Directed Graph We can use our graphing calculators to speed things up! Step 1: 2nd 𝒙 −𝟏 is MATRIX A= Step 2:  EDIT choose 1: [A] Step 3: Enter dimensions 3 x 3 Step 4: Now enter each element. Hit enter each time. Want [𝐴] 2 Step 5: When done, go 2nd MODE to QUIT = Step 6: Calculate [𝐴] 2 MATRIX  NAME  1: [A]  Enter Should match #3!

8 4. Suppose the nodes in the diagram represent people and the directed edges mean the first person knows the second person’s phone number. Directed Graph a) Interpret the diagram in a matrix. Betty Al Charles David Fred Ellen

9 Directed Graph Betty Al Charles David Fred Ellen 2nd person: 𝐴 𝐵 𝐶 𝐷 𝐸𝐹 𝐴 1 𝐵 1 1 1st Person: 𝐶 1 1 𝐷 1 1 𝐸 1 1 𝐹 1 1

10 Directed Graph Find B (1 call) 𝐵 2 (2 calls) 𝐵 3 (3 calls)4. b) In how many ways can a message get from Betty to Ellen in 3 or fewer calls? (*Use your graphing calculator!) Directed Graph 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐵= 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 1 call Find B (1 call) 𝐵 2 (2 calls) 𝐵 3 (3 calls) No (0) ways Right now, in one call, Betty can’t get a message (no message) to Ellen in 3 or fewer calls.

11 #4b Cont’d. In how many ways can a message get from Betty to Ellen in 3 or fewer calls? (*Use your calculator!) Directed Graph 2 calls 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐵 2 = 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 2 ways Now, through two calls, Betty can get a message to Ellen in 3 or fewer calls two different ways.

12 #4b Cont’d. In how many ways can a message get from Betty to Ellen in 3 or fewer calls? (*Use your calculator!) Directed Graph 3 calls 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐵 3 = 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 1 way Now, through three calls, Betty can get a message to Ellen in 3 or fewer calls in one way. B = 1 call = No way 𝐵 2 = 2 calls = 2 ways 𝐵 3 = 3 calls = 1 ways so 3 different ways TOTAL

13 4. c) Is it possible to get a message from Fred to Charles4. c) Is it possible to get a message from Fred to Charles? If yes, what is the minimum number of calls? Directed Graph 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐵= 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 1 call No way Yes, 2 calls minimum 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝐵 2 = 𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 2 calls 1 way

14 Assignment Pg. 616 #1–5, 7, 9, 11, 15, 17–20, 22–32