Find all numbered angles below:

1. How many odd vertices are in each of the graphs below? 2. Is the graph below traversable? Can you find an Euler path? 3. Is the graph below traversable? Can you find an Euler path?

Which turn block(s) will make the pink arrow to point to the strawberry? 2. Which turn block(s) will make the pink arrow to point to the strawberry? 3. What number will you put in the turn block to make the arrow point to the strawberry? the butterfly? the beetle? the apple? Try in Scratch to prove you are correct.

A. Notes A cycle is a path, which is simple except that the first and last vertex are the same (a path from a point back to itself). ADCBA is a cycle because only the first and last vertex are the same. ABCD is a simple path but not a cycle because the path does not go back to the starting point. CDABEA is a path, but not a simple path because vertex A repeats. It's not a cycle because the starting and ending vertices are not the same. BCDAEB is a cycle because only the starting and ending vertices are the same. Changing only the starting and ending vertex of a cycle will NOT create a new cycle, for example, ABCDA, BCDA, DABC and CDAB are the same cycle, so they count as 1 cycle. The degree of a vertex is the number of edges connected to that vertex. So in the blue graph, vertex A has a degree of 3, vertex B has a degree of 3, vertex C has a degree of 5, and vertex D also has a degree of 3. In 1735 Leonard Euler found that if a graph is traversable, the graph either has no vertex of odd degrees, or has only two vertices of odd degrees. And if a graph has no vertex of odd degrees, you can start at any vertex to traverse the graph; but if the graph has two vertices of odd degrees, you have to start at one odd-degree vertex and end at the other odd-degree vertex. The path to traverse a graph is called a Euler Path. The blue graph has 4 odd-degree vertices, so it is NOT traversable. The black graph above is traversable because it has two odd-degree vertices. B. HW Can you find three different cycles in the blue graph? Can you find more than three? Can you find the Euler Path of the black graph above? Can you find an Euler Path of the graph below?

A. Notes A path between two vertices in a graph is a list of vertices, in which successive vertices are connected by edges in the graph. The length of a path is the number of edges on the path. A simple path is a path with no vertex repeated. A graph is connected if if there is a path from every vertex to every other vertex in the graph. A graph is traversable if you can draw a path (not simple path) covering all the vertices without retracing any edge. Obviously, a traversable graph is connected. B. HW 1. In the graph below, how many paths can you find from A to D? Is this graph connected? How many simple paths from A to F are there? Is this graph traversable? 2. In the graph below, what is the longest simple path? Is this graph traversable? If you can add an edge, can you make the graph traversable?

A. Notes We learned that graphs are made of vertices and edges. We use a set of all vertices and all edges to describe a graph. For the elementary division, we only study undirected graphs. B. HW Draw a graph using the first letters of each person’s name: Alice talks to Bob, Bob talks to Carol, Carol talks to Alice, Alice talks to Doug, and Doug talks to Eve. The graph shows all of the conversations. Draw an undirected graph that has vertices {P, Q, R, S, T} and edges {PQ, RS, ST, PT, QT, RQ, TR}. Can you give a meaning of this graph? Draw a graph to show the cleaning robot's trace according to the description below. Can you think of a different moving strategy to ensure that the robot will pick up all pieces of trash? 4. There are 5 pieces of toys showing below. How many ways are there to rearrange them?

HW: Review all the statements below, are they true or false? X + Y = Y * X X * Y = YX (X + Y) + Z = (Y + Z) + X AC + BC = (A+B)*C A + 0 = 0 A + 1 = A X * 0 = 0 Y * 1 = 1 X + ~Y + Z + 1 = 1 Y ~Y = 0 B + B = B ABC = CAB (D + ~D) ~~X = 1 2. Simplify the following boolean expressions ~A ( B + A~B ) A~B ( A + ~B ) ~A + B~A + ~BA + ~B ~A (B + ~A) + A 3. The question I showed you in the class:

A. Notes In this last lesson of boolean algebra, we learned some common identities. Identities refer to the things that are always the same. For instance, A+B and B+A are always the same, so A+B and B+A are identities, we write A+B=B+A. Some commonly used identities in Boolean Algebra are below. #9 above is also called Law of Tautology. We can use these identities to simplify compound boolean expressions. While applying these identities, please keep in mind: A * or a dot both means AND, and sometimes we even omit them. i.e. AB, A*B, A&&B all mean A AND B. A bar on top of a variable means NOT, just as ! and ~. A bar on top of a compound expression means to negate the whole expression. See the example below. Solution I and II both simplify this boolean expression. B. HW Simplify the following boolean expressions: 2. Use DeMorgan's Law to simplify the following:

Truth Tables

A. Notes In the computer, we use 1 to represent true and 0 to represent false. We need to use true and false to check facts such as if 100 is greater than 40 We also need and, or, as well as not to connect multiple facts such as "if 100 is greater than 40 or today is the Easter Sunday" We call true and false boolean values. We call and, or, not boolean operators. If we mix boolean values and boolean operators together, we get boolean expressions. B. Exercises