{"id":155,"date":"2016-01-25T22:05:39","date_gmt":"2016-01-25T22:05:39","guid":{"rendered":"https:\/\/courses.candelalearning.com\/math4libarts\/?post_type=chapter&#038;p=155"},"modified":"2020-07-24T21:56:10","modified_gmt":"2020-07-24T21:56:10","slug":"graph-theory","status":"publish","type":"chapter","link":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/chapter\/graph-theory\/","title":{"raw":"Elements of Graph Theory","rendered":"Elements of Graph Theory"},"content":{"raw":"<div class=\"textbox learning-objectives\">\r\n<h3>Learning Outcomes<\/h3>\r\n<ul>\r\n \t<li>Identify the vertices, edges, and loops of a graph<\/li>\r\n \t<li>Identify the degree of a vertex<\/li>\r\n \t<li>Identify and draw both a path and a circuit through a graph<\/li>\r\n \t<li>Determine whether a graph is connected or disconnected<\/li>\r\n<\/ul>\r\n<\/div>\r\nIn the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.\r\n\r\nThis field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (we\u2019ll look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.\r\n<div class=\"textbox examples\">\r\n<h3>mathematical vocabulary<\/h3>\r\nIn mathematics, familiar words are often used in ways that are not familiar to you. That's because,\u00a0 as a new branch of mathematics is developed,\u00a0 a new vocabulary is built to describe it using the vernacular of the place and time in which it was developed. Graph theory is a relatively young branch of mathematics so it borrowed from words that are used commonly in our language.\r\n\r\nA good way to make new mathematical usages familiar is by using flashcards. Write the word on one side and the definition on the other. Work your way through the pile once by looking at the definition, trying to give the proper word. Then, shuffle the cards and work through them again by looking at the word and trying to give the proper definition.\r\n\r\nAfter working through the flashcards to memorize the new usages, build long-term memory by using the words in context. Read the text sections and try the examples and Try It problems, being careful to use the words in context. If possible, look for opportunities to use the vocabulary aloud in class.\r\n\r\nThis section contains a large number of new word usages. Don't gloss over these words and their mathematical definitions!\r\n\r\n<\/div>\r\n<h2>Drawing Graphs<\/h2>\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nHere is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.\r\n\r\n<img class=\"alignnone size-full wp-image-134\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"Fig2_5_1\" width=\"574\" height=\"438\" \/>\r\n\r\nNaturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.\r\n\r\nTo do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.\r\n\r\n<img class=\"aligncenter wp-image-135 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"A graph made from a map of streets by drawing an edge where each street is and a vertex where every intersection is.\" width=\"700\" height=\"264\" \/>\r\n\r\n<\/div>\r\nThis type of simplified picture is called a <strong>graph<\/strong>.\r\n<div class=\"textbox\">\r\n<h3>Graphs, Vertices, and Edges<\/h3>\r\nA <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.\r\n\r\n<\/div>\r\nWhile we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above.\r\n\r\n<img class=\"aligncenter wp-image-136 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"Two examples of graphs.\" width=\"700\" height=\"264\" \/>\r\n\r\nYou probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.\r\n\r\nWatch the video below to get another perspective of drawing a street network graph.\r\n\r\nhttps:\/\/youtu.be\/gyQhW24Dr2E\r\n<div class=\"textbox exercises\">\r\n<h3>Example<\/h3>\r\nBack in the 18th century in the Prussian city of K\u00f6nigsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture below.[footnote]Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png[\/footnote]\r\n\r\n<img class=\"wp-image-137 aligncenter\" style=\"font-size: 16px; orphans: 1;\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155115\/Fig2_5_4.png\" alt=\"Fig2_5_4\" width=\"300\" height=\"235\" \/>As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.\r\n\r\n<\/div>\r\nIn the following video we present another view of the K\u00f6nigsberg bridge problem.\r\n\r\nhttps:\/\/youtu.be\/yn-OD8OBSDM\r\n\r\nLeonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:\r\n\r\n<img class=\"alignnone wp-image-138\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155116\/Fig2_5_5.png\" alt=\"Fig2_5_5\" width=\"500\" height=\"193\" \/>\r\n\r\nSince the size of each land mass it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:\r\n\r\n<img class=\"alignnone size-full wp-image-139\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155117\/Fig2_5_6.png\" alt=\"Fig2_5_6\" width=\"226\" height=\"199\" \/>\r\n\r\nNotice that in this graph there are <em>two<\/em> edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.\r\n\r\nWhile we haven\u2019t answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.\r\n<h2>Definitions<\/h2>\r\nWhile we loosely defined some terminology earlier, we now will try to be more specific.\r\n<div class=\"textbox\">\r\n<h3>Vertex<\/h3>\r\nA vertex is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Edges<\/h3>\r\nEdges connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight.\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Loop<\/h3>\r\nA loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.\r\n\r\n<img class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Three vertices connected to each other by edges. One vertex has a loop connecting itself to itself.\" width=\"245\" height=\"147\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Degree of a vertex<\/h3>\r\nThe degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.\r\n<table>\r\n<thead>\r\n<tr>\r\n<th>Degree 0<\/th>\r\n<th>Degree 1<\/th>\r\n<th>Degree 2<\/th>\r\n<th>Degree 3<\/th>\r\n<th>Degree 4<\/th>\r\n<\/tr>\r\n<\/thead>\r\n<tbody>\r\n<tr>\r\n<td><img class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"A dot.\" width=\"30\" height=\"30\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"A dot with one line attached to it.\" width=\"90\" height=\"46\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"A dot with two lines attached to it.\" width=\"140\" height=\"57\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"A dot with three lines attached to it.\" width=\"140\" height=\"93\" \/><\/td>\r\n<td><img class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"A dot with four lines attached to it.\" width=\"140\" height=\"96\" \/><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Path<\/h3>\r\nA path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.\r\n\r\n<img class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A path is drawn from A to M going though the points B, F, G, and H.\" width=\"350\" height=\"148\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Circuit<\/h3>\r\nA circuit is a path that begins and ends at the same vertex. A circuit starting and ending at vertex A is shown below.\r\n\r\n<img class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A circuit is drawn, going through the points A, B, F, G, L, L, J, and E.\" width=\"350\" height=\"150\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Connected<\/h3>\r\nA graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.\r\n\r\n<img class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"A 3x4 graph where there is not a path from every vertex to every other vertex.\" width=\"350\" height=\"137\" \/>\r\n\r\n<\/div>\r\n<div class=\"textbox\">\r\n<h3>Weights<\/h3>\r\nDepending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\n1.The graph below shows 5 cities. The weights on the edges represent the airfare for a one -way flight between the cities.\r\n<p style=\"padding-left: 30px;\">a. How many vertices and edges does the graph have?\r\nb. Is the graph connected?\r\nc. What is the degree of the vertex representing LA?\r\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?\r\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.<\/p>\r\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\"><img class=\" wp-image-1202 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM-300x150.png\" alt=\"\" width=\"494\" height=\"247\" \/><\/a><\/p>\r\n[reveal-answer q=\"942356\"]Show Solution[\/reveal-answer]\r\n[hidden-answer a=\"942356\"]\r\n\r\nSolution\r\n\r\na. 5 vertices, 10 edges\r\n\r\nb. yes\r\n\r\nc. 4\r\n\r\nd. path\r\n\r\ne. circuit\r\n\r\n[\/hidden-answer]\r\n\r\n<\/div>\r\n<div class=\"textbox key-takeaways\">\r\n<h3>Try It<\/h3>\r\n[ohm_question]6883[\/ohm_question]\r\n\r\n[ohm_question]6885[\/ohm_question]\r\n\r\n<\/div>","rendered":"<div class=\"textbox learning-objectives\">\n<h3>Learning Outcomes<\/h3>\n<ul>\n<li>Identify the vertices, edges, and loops of a graph<\/li>\n<li>Identify the degree of a vertex<\/li>\n<li>Identify and draw both a path and a circuit through a graph<\/li>\n<li>Determine whether a graph is connected or disconnected<\/li>\n<\/ul>\n<\/div>\n<p>In the modern world, planning efficient routes is essential for business and industry, with applications as varied as product distribution, laying new fiber optic lines for broadband internet, and suggesting new friends within social network websites like Facebook.<\/p>\n<p>This field of mathematics started nearly 300 years ago as a look into a mathematical puzzle (we\u2019ll look at it in a bit). The field has exploded in importance in the last century, both because of the growing complexity of business in a global economy and because of the computational power that computers have provided us.<\/p>\n<div class=\"textbox examples\">\n<h3>mathematical vocabulary<\/h3>\n<p>In mathematics, familiar words are often used in ways that are not familiar to you. That&#8217;s because,\u00a0 as a new branch of mathematics is developed,\u00a0 a new vocabulary is built to describe it using the vernacular of the place and time in which it was developed. Graph theory is a relatively young branch of mathematics so it borrowed from words that are used commonly in our language.<\/p>\n<p>A good way to make new mathematical usages familiar is by using flashcards. Write the word on one side and the definition on the other. Work your way through the pile once by looking at the definition, trying to give the proper word. Then, shuffle the cards and work through them again by looking at the word and trying to give the proper definition.<\/p>\n<p>After working through the flashcards to memorize the new usages, build long-term memory by using the words in context. Read the text sections and try the examples and Try It problems, being careful to use the words in context. If possible, look for opportunities to use the vocabulary aloud in class.<\/p>\n<p>This section contains a large number of new word usages. Don&#8217;t gloss over these words and their mathematical definitions!<\/p>\n<\/div>\n<h2>Drawing Graphs<\/h2>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Here is a portion of a housing development from Missoula, Montana. As part of her job, the development\u2019s lawn inspector has to walk down every street in the development making sure homeowners\u2019 landscaping conforms to the community requirements.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-134\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155110\/Fig2_5_1.png\" alt=\"Fig2_5_1\" width=\"574\" height=\"438\" \/><\/p>\n<p>Naturally, she wants to minimize the amount of walking she has to do. Is it possible for her to walk down every street in this development without having to do any backtracking? While you might be able to answer that question just by looking at the picture for a while, it would be ideal to be able to answer the question for any picture regardless of its complexity.<\/p>\n<p>To do that, we first need to simplify the picture into a form that is easier to work with. We can do that by drawing a simple line for each street. Where streets intersect, we will place a dot.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-135 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"A graph made from a map of streets by drawing an edge where each street is and a vertex where every intersection is.\" width=\"700\" height=\"264\" \/><\/p>\n<\/div>\n<p>This type of simplified picture is called a <strong>graph<\/strong>.<\/p>\n<div class=\"textbox\">\n<h3>Graphs, Vertices, and Edges<\/h3>\n<p>A <strong>graph<\/strong> consists of a set of dots, called <strong>vertices<\/strong>, and a set of <strong>edges<\/strong> connecting pairs of vertices.<\/p>\n<\/div>\n<p>While we drew our original graph to correspond with the picture we had, there is nothing particularly important about the layout when we analyze a graph. Both of the graphs below are equivalent to the one drawn above.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-136 size-full\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155111\/Fig2_5_2.png\" alt=\"Two examples of graphs.\" width=\"700\" height=\"264\" \/><\/p>\n<p>You probably already noticed that we are using the term<em> graph<\/em> differently than you may have used the term in the past to describe the graph of a mathematical function.<\/p>\n<p>Watch the video below to get another perspective of drawing a street network graph.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-1\" title=\"Drawing a street network graph\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/gyQhW24Dr2E?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<div class=\"textbox exercises\">\n<h3>Example<\/h3>\n<p>Back in the 18th century in the Prussian city of K\u00f6nigsberg, a river ran through the city and seven bridges crossed the forks of the river. The river and the bridges are highlighted in the picture below.<a class=\"footnote\" title=\"Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png\" id=\"return-footnote-155-1\" href=\"#footnote-155-1\" aria-label=\"Footnote 1\"><sup class=\"footnote\">[1]<\/sup><\/a><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-137 aligncenter\" style=\"font-size: 16px; orphans: 1;\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155115\/Fig2_5_4.png\" alt=\"Fig2_5_4\" width=\"300\" height=\"235\" \/>As a weekend amusement, townsfolk would see if they could find a route that would take them across every bridge once and return them to where they started.<\/p>\n<\/div>\n<p>In the following video we present another view of the K\u00f6nigsberg bridge problem.<\/p>\n<p><iframe loading=\"lazy\" id=\"oembed-2\" title=\"Drawing a graph for bridges\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/yn-OD8OBSDM?feature=oembed&#38;rel=0\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n<p>Leonard Euler (pronounced OY-lur), one of the most prolific mathematicians ever, looked at this problem in 1735, laying the foundation for graph theory as a field in mathematics. To analyze this problem, Euler introduced edges representing the bridges:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-138\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155116\/Fig2_5_5.png\" alt=\"Fig2_5_5\" width=\"500\" height=\"193\" \/><\/p>\n<p>Since the size of each land mass it is not relevant to the question of bridge crossings, each can be shrunk down to a vertex representing the location:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-139\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155117\/Fig2_5_6.png\" alt=\"Fig2_5_6\" width=\"226\" height=\"199\" \/><\/p>\n<p>Notice that in this graph there are <em>two<\/em> edges connecting the north bank and island, corresponding to the two bridges in the original drawing. Depending upon the interpretation of edges and vertices appropriate to a scenario, it is entirely possible and reasonable to have more than one edge connecting two vertices.<\/p>\n<p>While we haven\u2019t answered the actual question yet of whether or not there is a route which crosses every bridge once and returns to the starting location, the graph provides the foundation for exploring this question.<\/p>\n<h2>Definitions<\/h2>\n<p>While we loosely defined some terminology earlier, we now will try to be more specific.<\/p>\n<div class=\"textbox\">\n<h3>Vertex<\/h3>\n<p>A vertex is a dot in the graph that could represent an intersection of streets, a land mass, or a general location, like \u201cwork\u201d or \u201cschool\u201d. Vertices are often connected by edges. Note that vertices only occur when a dot is explicitly placed, not whenever two edges cross. Imagine a freeway overpass\u2014the freeway and side street cross, but it is not possible to change from the side street to the freeway at that point, so there is no intersection and no vertex would be placed.<\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Edges<\/h3>\n<p>Edges connect pairs of vertices. An edge can represent a physical connection between locations, like a street, or simply that a route connecting the two locations exists, like an airline flight.<\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Loop<\/h3>\n<p>A loop is a special type of edge that connects a vertex to itself. Loops are not used much in street network graphs.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-140\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155118\/Fig2_5_7.png\" alt=\"Three vertices connected to each other by edges. One vertex has a loop connecting itself to itself.\" width=\"245\" height=\"147\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Degree of a vertex<\/h3>\n<p>The degree of a vertex is the number of edges meeting at that vertex. It is possible for a vertex to have a degree of zero or larger.<\/p>\n<table>\n<thead>\n<tr>\n<th>Degree 0<\/th>\n<th>Degree 1<\/th>\n<th>Degree 2<\/th>\n<th>Degree 3<\/th>\n<th>Degree 4<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-141\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_8.png\" alt=\"A dot.\" width=\"30\" height=\"30\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-142\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155119\/Fig2_5_9.png\" alt=\"A dot with one line attached to it.\" width=\"90\" height=\"46\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-143\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_10.png\" alt=\"A dot with two lines attached to it.\" width=\"140\" height=\"57\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-144\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155120\/Fig2_5_11.png\" alt=\"A dot with three lines attached to it.\" width=\"140\" height=\"93\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-145\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155121\/Fig2_5_12.png\" alt=\"A dot with four lines attached to it.\" width=\"140\" height=\"96\" \/><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<div class=\"textbox\">\n<h3>Path<\/h3>\n<p>A path is a sequence of vertices using the edges. Usually we are interested in a path between two vertices. For example, a path from vertex A to vertex M is shown below. It is one of many possible paths in this graph.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-146\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155122\/Fig2_5_13.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A path is drawn from A to M going though the points B, F, G, and H.\" width=\"350\" height=\"148\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Circuit<\/h3>\n<p>A circuit is a path that begins and ends at the same vertex. A circuit starting and ending at vertex A is shown below.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-147\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155123\/Fig2_5_14.png\" alt=\"Rectangular graph with 12 vertices labeled A through M (without I). A circuit is drawn, going through the points A, B, F, G, L, L, J, and E.\" width=\"350\" height=\"150\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Connected<\/h3>\n<p>A graph is connected if there is a path from any vertex to any other vertex. Every graph drawn so far has been connected. The graph below is <strong>disconnected<\/strong>; there is no way to get from the vertices on the left to the vertices on the right.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-148\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images-archive-read-only\/wp-content\/uploads\/sites\/282\/2016\/01\/20155124\/Fig2_5_15.png\" alt=\"A 3x4 graph where there is not a path from every vertex to every other vertex.\" width=\"350\" height=\"137\" \/><\/p>\n<\/div>\n<div class=\"textbox\">\n<h3>Weights<\/h3>\n<p>Depending upon the problem being solved, sometimes weights are assigned to the edges. The weights could represent the distance between two locations, the travel time, or the travel cost. It is important to note that the distance between vertices in a graph does not necessarily correspond to the weight of an edge.<\/p>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p>1.The graph below shows 5 cities. The weights on the edges represent the airfare for a one -way flight between the cities.<\/p>\n<p style=\"padding-left: 30px;\">a. How many vertices and edges does the graph have?<br \/>\nb. Is the graph connected?<br \/>\nc. What is the degree of the vertex representing LA?<br \/>\nd. If you fly from Seattle to Dallas to Atlanta, is that a path or a circuit?<br \/>\ne. If you fly from LA to Chicago to Dallas to LA, is that a path or a circuit.<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1202 aligncenter\" src=\"https:\/\/s3-us-west-2.amazonaws.com\/courses-images\/wp-content\/uploads\/sites\/1141\/2017\/01\/24020234\/Screen-Shot-2017-01-23-at-6.02.20-PM-300x150.png\" alt=\"\" width=\"494\" height=\"247\" \/><\/a><\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><span class=\"show-answer collapsed\" style=\"cursor: pointer\" data-target=\"q942356\">Show Solution<\/span><\/p>\n<div id=\"q942356\" class=\"hidden-answer\" style=\"display: none\">\n<p>Solution<\/p>\n<p>a. 5 vertices, 10 edges<\/p>\n<p>b. yes<\/p>\n<p>c. 4<\/p>\n<p>d. path<\/p>\n<p>e. circuit<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"textbox key-takeaways\">\n<h3>Try It<\/h3>\n<p><iframe loading=\"lazy\" id=\"ohm6883\" class=\"resizable\" src=\"https:\/\/ohm.lumenlearning.com\/multiembedq.php?id=6883&theme=oea&iframe_resize_id=ohm6883&show_question_numbers\" width=\"100%\" height=\"150\"><\/iframe><\/p>\n<p><iframe loading=\"lazy\" id=\"ohm6885\" class=\"resizable\" src=\"https:\/\/ohm.lumenlearning.com\/multiembedq.php?id=6885&theme=oea&iframe_resize_id=ohm6885&show_question_numbers\" width=\"100%\" height=\"150\"><\/iframe><\/p>\n<\/div>\n\n\t\t\t <section class=\"citations-section\" role=\"contentinfo\">\n\t\t\t <h3>Candela Citations<\/h3>\n\t\t\t\t\t <div>\n\t\t\t\t\t\t <div id=\"citation-list-155\">\n\t\t\t\t\t\t\t <div class=\"licensing\"><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Original<\/div><ul class=\"citation-list\"><li>Revision and Adaptation. <strong>Provided by<\/strong>: Lumen Learning. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><\/ul><div class=\"license-attribution-dropdown-subheading\">CC licensed content, Shared previously<\/div><ul class=\"citation-list\"><li>Graph Theory. <strong>Authored by<\/strong>: David Lippman. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\">http:\/\/www.opentextbookstore.com\/mathinsociety\/<\/a>. <strong>Project<\/strong>: Math in Society. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Pleasant View housing development. <strong>Authored by<\/strong>: Sam Beebe. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/flic.kr\/p\/5kTroZ\">https:\/\/flic.kr\/p\/5kTroZ<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Drawing a street network graph. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/gyQhW24Dr2E\">https:\/\/youtu.be\/gyQhW24Dr2E<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/about\/pdm\">Public Domain: No Known Copyright<\/a><\/em><\/li><li>Drawing a graph for bridges. <strong>Authored by<\/strong>: OCLPhase2. <strong>Located at<\/strong>: <a target=\"_blank\" href=\"https:\/\/youtu.be\/yn-OD8OBSDM\">https:\/\/youtu.be\/yn-OD8OBSDM<\/a>. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em><\/li><li>Question ID 6885, 6883. <strong>Authored by<\/strong>: Lippman, David. <strong>License<\/strong>: <em><a target=\"_blank\" rel=\"license\" href=\"https:\/\/creativecommons.org\/licenses\/by\/4.0\/\">CC BY: Attribution<\/a><\/em>. <strong>License Terms<\/strong>: IMathAS Community License, CC-BY + GPL<\/li><\/ul><\/div>\n\t\t\t\t\t\t <\/div>\n\t\t\t\t\t <\/div>\n\t\t\t <\/section><hr class=\"before-footnotes clear\" \/><div class=\"footnotes\"><ol><li id=\"footnote-155-1\">Bogdan Giu\u015fc\u0103. http:\/\/en.wikipedia.org\/wiki\/File:Konigsberg_bridges.png <a href=\"#return-footnote-155-1\" class=\"return-footnote\" aria-label=\"Return to footnote 1\">&crarr;<\/a><\/li><\/ol><\/div>","protected":false},"author":276,"menu_order":19,"template":"","meta":{"_candela_citation":"[{\"type\":\"cc\",\"description\":\"Graph Theory\",\"author\":\"David Lippman\",\"organization\":\"\",\"url\":\"http:\/\/www.opentextbookstore.com\/mathinsociety\/\",\"project\":\"Math in Society\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Pleasant View housing development\",\"author\":\"Sam Beebe\",\"organization\":\"\",\"url\":\"https:\/\/flic.kr\/p\/5kTroZ\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Drawing a street network graph\",\"author\":\"\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/gyQhW24Dr2E\",\"project\":\"\",\"license\":\"pd\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Drawing a graph for bridges\",\"author\":\"OCLPhase2\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/yn-OD8OBSDM\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"},{\"type\":\"cc\",\"description\":\"Question ID 6885, 6883\",\"author\":\"Lippman, David\",\"organization\":\"\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"IMathAS Community License, CC-BY + GPL\"},{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","CANDELA_OUTCOMES_GUID":"013ca704-c6d8-4857-b3fe-aadd66b385db","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-155","chapter","type-chapter","status-publish","hentry"],"part":1193,"_links":{"self":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/155","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/wp\/v2\/users\/276"}],"version-history":[{"count":27,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/155\/revisions"}],"predecessor-version":[{"id":5326,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/155\/revisions\/5326"}],"part":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/parts\/1193"}],"metadata":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapters\/155\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/wp\/v2\/media?parent=155"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/pressbooks\/v2\/chapter-type?post=155"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/wp\/v2\/contributor?post=155"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/courses.lumenlearning.com\/mathforliberalartscorequisite\/wp-json\/wp\/v2\/license?post=155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}