{"id":8293,"date":"2023-09-29T14:31:27","date_gmt":"2023-09-29T14:31:27","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=8293"},"modified":"2025-08-29T04:36:39","modified_gmt":"2025-08-29T04:36:39","slug":"graph-theory-basics-apply-it-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-basics-apply-it-1\/","title":{"raw":"Graph Theory Basics: Apply It 1","rendered":"Graph Theory Basics: Apply It 1"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\r\n\t<li><span data-sheets-value=\"{&quot;1&quot;:2,&quot;2&quot;:&quot;Identify both a path and a circuit through a graph&quot;}\" data-sheets-userformat=\"{&quot;2&quot;:5057,&quot;3&quot;:{&quot;1&quot;:0},&quot;9&quot;:0,&quot;10&quot;:0,&quot;11&quot;:3,&quot;12&quot;:0,&quot;15&quot;:&quot;Arial&quot;}\">Identify both a path and a circuit through a graph<\/span><\/li>\r\n\t<li>Determine whether a graph is connected or disconnected<\/li>\r\n\t<li>Find the shortest path through a graph using Dijkstra's Algorithm<\/li>\r\n<\/ul>\r\n<\/section>\r\n<h2 data-type=\"title\">Analyzing Geographical Maps with Graphs<\/h2>\r\n<div id=\"fig-00014\" class=\"os-figure\"><center>\r\n[caption id=\"\" align=\"aligncenter\" width=\"1803\"]<img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/8409e8c5bc6c94b2f34779dda479cae7f3dcfafa\" alt=\"A map shows dots representing the flight connections from a particular airport.\" width=\"1803\" height=\"500\" data-media-type=\"image\/jpg\" \/> Figure 1. Commercial airlines' route systems create a global network[\/caption]\r\n<\/center><\/div>\r\n<p>&nbsp;<\/p>\r\n<p id=\"para-00016\">When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in\u00a0the figure below. Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In\u00a0the figure below, the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex [latex]FYW[\/latex] has\u00a0<strong>degree\u00a0<\/strong> [latex]3[\/latex]. The degree of a vertex is the number of edges that connect to that vertex.<\/p>\r\n<div id=\"fig-00005\" class=\"os-figure\"><center>\r\n[caption id=\"\" align=\"aligncenter\" width=\"500\"]<img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/4f830857b9a1c450c19eb1786d7c5735f2e4b656\" alt=\"A graph represents the direct flights between South Florida airports. The graph has five vertices. Edges from the vertex, Tampa T P A connect with Key West E Y W, Miami M I A, Fort Lauderdale F L L, and West Palm Beach P B I. An edge connects Fort Lauderdale with Key West. An edge connects Miami with Key West.\" width=\"500\" height=\"601\" data-media-type=\"image\/png\" \/> Figure 2. Direct Flights between South Florida Airports[\/caption]\r\n<\/center>\r\n<div class=\"os-caption-container\" style=\"text-align: center;\">\u00a0<\/div>\r\n<div>\r\n<section class=\"textbox tryIt\">\r\n<p>[ohm2_question hide_question_numbers=1]13897[\/ohm2_question]<\/p>\r\n<\/section>\r\n<p>Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the \u201cFour Corners,\u201d which is shown in the map in below.<\/p>\r\n<center>\r\n[caption id=\"\" align=\"aligncenter\" width=\"500\"]<img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/4d8ab1704073aa122530401f30cd233a3e812b31\" alt=\"A map of the USA with the four corners region highlighted. It includes Utah, Colorado, Arizona, and New Mexico.\" width=\"500\" height=\"1068\" data-media-type=\"image\/png\" \/> Figure 3. Map of the Four Corners[\/caption]\r\n<\/center>\r\n<p style=\"text-align: center;\">\u00a0<\/p>\r\n<p>In the figure below, each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are not considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size and distance, toward the existence of the relationship of having a shared boundary.<\/p>\r\n<center>\r\n[caption id=\"\" align=\"alignnone\" width=\"473\"]<img src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/aeceeb372e6c22d2fe3570888f07db8a1eed68a3\" alt=\"A graph of four corner states. The graph shows four edges and four vertices forming a rectangle. The vertices are Utah, Colorado, Arizona, and New Mexico.\" width=\"473\" height=\"329\" data-media-type=\"image\/png\" data-width=\"473\" data-height=\"329\" \/> Figure 4. Graph of the Shared Boundaries of Four Corners States[\/caption]\r\n<\/center>\r\n<div class=\"os-caption-container\" style=\"text-align: center;\">\u00a0<\/div>\r\n<div>\r\n<section class=\"textbox tryIt\">\r\n<p>[ohm2_question hide_question_numbers=1]13898[\/ohm2_question]<\/p>\r\n<\/section>\r\n<section class=\"textbox watchIt\">\r\n<p><iframe src=\"\/\/plugin.3playmedia.com\/show?mf=12469709&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=CEMhO8T_6zw&amp;video_target=tpm-plugin-3hpad2ad-CEMhO8T_6zw\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\r\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory+-+Create+Graph+to+Represent+Common+Boundaries+on+a+Map.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Create Graph to Represent Common Boundaries on a Map\u201d here (opens in new window).<\/a><\/p>\r\n<\/section>\r\n<\/div>\r\n<\/div>\r\n<\/div>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Recognize graph components: vertices, edges, loops, and vertex degrees<\/li>\n<li><span data-sheets-value=\"{&quot;1&quot;:2,&quot;2&quot;:&quot;Identify both a path and a circuit through a graph&quot;}\" data-sheets-userformat=\"{&quot;2&quot;:5057,&quot;3&quot;:{&quot;1&quot;:0},&quot;9&quot;:0,&quot;10&quot;:0,&quot;11&quot;:3,&quot;12&quot;:0,&quot;15&quot;:&quot;Arial&quot;}\">Identify both a path and a circuit through a graph<\/span><\/li>\n<li>Determine whether a graph is connected or disconnected<\/li>\n<li>Find the shortest path through a graph using Dijkstra&#8217;s Algorithm<\/li>\n<\/ul>\n<\/section>\n<h2 data-type=\"title\">Analyzing Geographical Maps with Graphs<\/h2>\n<div id=\"fig-00014\" class=\"os-figure\">\n<div style=\"text-align: center;\">\n<figure style=\"width: 1803px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/8409e8c5bc6c94b2f34779dda479cae7f3dcfafa\" alt=\"A map shows dots representing the flight connections from a particular airport.\" width=\"1803\" height=\"500\" data-media-type=\"image\/jpg\" \/><figcaption class=\"wp-caption-text\">Figure 1. Commercial airlines&#8217; route systems create a global network<\/figcaption><\/figure>\n<\/div>\n<\/div>\n<p>&nbsp;<\/p>\n<p id=\"para-00016\">When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in\u00a0the figure below. Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In\u00a0the figure below, the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex [latex]FYW[\/latex] has\u00a0<strong>degree\u00a0<\/strong> [latex]3[\/latex]. The degree of a vertex is the number of edges that connect to that vertex.<\/p>\n<div id=\"fig-00005\" class=\"os-figure\">\n<div style=\"text-align: center;\">\n<figure style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/4f830857b9a1c450c19eb1786d7c5735f2e4b656\" alt=\"A graph represents the direct flights between South Florida airports. The graph has five vertices. Edges from the vertex, Tampa T P A connect with Key West E Y W, Miami M I A, Fort Lauderdale F L L, and West Palm Beach P B I. An edge connects Fort Lauderdale with Key West. An edge connects Miami with Key West.\" width=\"500\" height=\"601\" data-media-type=\"image\/png\" \/><figcaption class=\"wp-caption-text\">Figure 2. Direct Flights between South Florida Airports<\/figcaption><\/figure>\n<\/div>\n<div class=\"os-caption-container\" style=\"text-align: center;\">\u00a0<\/div>\n<div>\n<section class=\"textbox tryIt\">\n<iframe loading=\"lazy\" id=\"ohm13897\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=13897&theme=lumen&iframe_resize_id=ohm13897&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><br \/>\n<\/section>\n<p>Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the \u201cFour Corners,\u201d which is shown in the map in below.<\/p>\n<div style=\"text-align: center;\">\n<figure style=\"width: 500px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/4d8ab1704073aa122530401f30cd233a3e812b31\" alt=\"A map of the USA with the four corners region highlighted. It includes Utah, Colorado, Arizona, and New Mexico.\" width=\"500\" height=\"1068\" data-media-type=\"image\/png\" \/><figcaption class=\"wp-caption-text\">Figure 3. Map of the Four Corners<\/figcaption><\/figure>\n<\/div>\n<p style=\"text-align: center;\">\u00a0<\/p>\n<p>In the figure below, each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are not considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size and distance, toward the existence of the relationship of having a shared boundary.<\/p>\n<div style=\"text-align: center;\">\n<figure style=\"width: 473px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/openstax.org\/apps\/image-cdn\/v1\/f=webp\/apps\/archive\/20230828.164620\/resources\/aeceeb372e6c22d2fe3570888f07db8a1eed68a3\" alt=\"A graph of four corner states. The graph shows four edges and four vertices forming a rectangle. The vertices are Utah, Colorado, Arizona, and New Mexico.\" width=\"473\" height=\"329\" data-media-type=\"image\/png\" data-width=\"473\" data-height=\"329\" \/><figcaption class=\"wp-caption-text\">Figure 4. Graph of the Shared Boundaries of Four Corners States<\/figcaption><\/figure>\n<\/div>\n<div class=\"os-caption-container\" style=\"text-align: center;\">\u00a0<\/div>\n<div>\n<section class=\"textbox tryIt\">\n<iframe loading=\"lazy\" id=\"ohm13898\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=13898&theme=lumen&iframe_resize_id=ohm13898&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><br \/>\n<\/section>\n<section class=\"textbox watchIt\">\n<p><iframe loading=\"lazy\" src=\"\/\/plugin.3playmedia.com\/show?mf=12469709&amp;p3sdk_version=1.10.1&amp;p=20361&amp;pt=375&amp;video_id=CEMhO8T_6zw&amp;video_target=tpm-plugin-3hpad2ad-CEMhO8T_6zw\" width=\"800px\" height=\"450px\" frameborder=\"0\" marginwidth=\"0px\" marginheight=\"0px\"><\/iframe><\/p>\n<p>You can view the <a href=\"https:\/\/course-building.s3.us-west-2.amazonaws.com\/Quantitative+Reasoning+-+2023+Build\/Transcriptions\/Graph+Theory+-+Create+Graph+to+Represent+Common+Boundaries+on+a+Map.txt\" target=\"_blank\" rel=\"noopener\">transcript for \u201cGraph Theory: Create Graph to Represent Common Boundaries on a Map\u201d here (opens in new window).<\/a><\/p>\n<\/section>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":15,"menu_order":6,"template":"","meta":{"_candela_citation":"[{\"type\":\"cc-attribution\",\"description\":\"Contemporary Mathematics\",\"author\":\"Donna Kirk\",\"organization\":\"OpenStax\",\"url\":\"https:\/\/openstax.org\/books\/contemporary-mathematics\/pages\/12-1-graph-basics#fig-00013\",\"project\":\"12.1 Graph Basics\",\"license\":\"cc-by\",\"license_terms\":\"Access for free at https:\/\/openstax.org\/books\/contemporary-mathematics\/pages\/1-introduction\"},{\"type\":\"copyrighted_video\",\"description\":\"Graph Theory: Create Graph to Represent Common Boundaries on a Map\",\"author\":\"Quin Hearn (MsHearnMath.com)\",\"organization\":\"\",\"url\":\"https:\/\/youtu.be\/CEMhO8T_6zw\",\"project\":\"\",\"license\":\"arr\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"apply_it","content_attributions":[{"type":"cc-attribution","description":"Contemporary Mathematics","author":"Donna Kirk","organization":"OpenStax","url":"https:\/\/openstax.org\/books\/contemporary-mathematics\/pages\/12-1-graph-basics#fig-00013","project":"12.1 Graph Basics","license":"cc-by","license_terms":"Access for free at https:\/\/openstax.org\/books\/contemporary-mathematics\/pages\/1-introduction"},{"type":"copyrighted_video","description":"Graph Theory: Create Graph to Represent Common Boundaries on a Map","author":"Quin Hearn (MsHearnMath.com)","organization":"","url":"https:\/\/youtu.be\/CEMhO8T_6zw","project":"","license":"arr","license_terms":""}],"internal_book_links":[],"video_content":null,"cc_video_embed_content":{"cc_scripts":"","media_targets":[]},"try_it_collection":null,"_links":{"self":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8293"}],"collection":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/users\/15"}],"version-history":[{"count":22,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8293\/revisions"}],"predecessor-version":[{"id":15922,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8293\/revisions\/15922"}],"part":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/parts\/75"}],"metadata":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/8293\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=8293"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=8293"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=8293"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=8293"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}