Welcome back to classes! We will be kicking off the semester this week with an introduction to graph theory. A graph is a collection of vertices (think dots) and edges (think lines) between the vertices. We can use graphs to study many things in the world around us. For example, a graph can represent streets and intersections from a map (see The Traveling Salesperson Problem), computer networks, social networks, or even be used to study DNA (see A Graph Theoretical Approach to DNA Fragment Assembly). By the end of this week, you should know what a graph is and be able to describe several properties of a graph.
Challenge Problem: Sketch several examples of graphs. Determine the degree of the vertices in each graph. When you add the degrees of all the vertices, you will always get an even number. Why is that?
No comments:
Post a Comment