{"id":2842,"date":"2023-05-16T13:08:12","date_gmt":"2023-05-16T13:08:12","guid":{"rendered":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/?post_type=chapter&#038;p=2842"},"modified":"2024-10-18T20:58:06","modified_gmt":"2024-10-18T20:58:06","slug":"graph-theory-background-youll-need-part-1","status":"web-only","type":"chapter","link":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/chapter\/graph-theory-background-youll-need-part-1\/","title":{"raw":"Graph Theory: Background You'll Need 1","rendered":"Graph Theory: Background You&#8217;ll Need 1"},"content":{"raw":"<section class=\"textbox learningGoals\">\r\n<ul>\r\n\t<li>Understand sets, including union, intersection, and subsets<\/li>\r\n<\/ul>\r\n<\/section>\r\n<h2>Set Theory<\/h2>\r\n<p>A movie lover might own a collection of movie posters, while a music lover might keep a collection of vinyl records. Any collection of items can form a <strong>set<\/strong>.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>set<\/h3>\r\n<p>A <strong>set<\/strong> is a collection of distinct objects, called <strong>elements<\/strong> of the set.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>A set can be defined by describing the contents, or by listing the elements of the set, enclosed in curly brackets separated by commas.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>Repeated elements in a set are only listed once. A set simply specifies the contents; order is not important.<\/p>\r\n<p>&nbsp;<\/p>\r\n<center>The set represented by [latex]\\{1, 2, 3\\}[\/latex] is equivalent to the set [latex]\\{3, 1, 2\\}[\/latex].<\/center><\/div>\r\n<\/section>\r\n<section class=\"textbox example\">Some examples of sets defined by describing the contents:\r\n\r\n\r\n<ol>\r\n\t<li>The set of all even numbers<\/li>\r\n\t<li>The set of all books written about travel to Chile<\/li>\r\n<\/ol>\r\n<p>Some examples of sets defined by listing the elements of the set:<\/p>\r\n<ol>\r\n\t<li>[latex]\\{1, 3, 9, 12\\}[\/latex]<\/li>\r\n\t<li>[latex]\\{\\text{red, orange, yellow, green, blue, indigo, purple}\\}[\/latex]<\/li>\r\n<\/ol>\r\n<\/section>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>set notation<\/h3>\r\n<p>Commonly, we will use a variable to represent a set, to make it easier to refer to that set later.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>The symbol [latex]\\in[\/latex]\u00a0means \u201cis an element of\u201d.<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>A set that contains no elements, [latex]\\{ \\}[\/latex], is called the <strong>empty set<\/strong> or null set and is notated [latex]\\emptyset[\/latex].<\/p>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox example\">Let [latex]A=\\{1,2,3,4\\}[\/latex]To notate that [latex]2[\/latex] is element of the set, we'd write [latex]2 \\in A[\/latex]<\/section>\r\n<p>Sometimes a collection might not contain all the elements of a set. For example, Marta owns ninety-five Pok\u00e9mon cards. While Marta\u2019s collection is a set, we can also say it is a <strong>subset<\/strong> of the larger set of all Pok\u00e9mon cards.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>subset<\/h3>\r\n<p>A <strong>subset<\/strong> of a set [latex]A[\/latex] is a set that consists solely of elements drawn from set [latex]A[\/latex].<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>It may include all, some, or none of set [latex]A[\/latex]'s elements. In other words, every element in the subset is also an element of set [latex]A[\/latex].<\/p>\r\n<p>&nbsp;<\/p>\r\n<center>If [latex]B[\/latex] is a subset of [latex]A[\/latex], we write [latex]B \\subseteq A[\/latex]<\/center><center><\/center>\r\n<p>&nbsp;<\/p>\r\n<p>A <strong>proper subset<\/strong> of a set [latex]A[\/latex] is a subset that contains some, but not all, of the elements of set [latex]A[\/latex].<\/p>\r\n<p>&nbsp;<\/p>\r\n<p>It is a subset that is not identical to the original set, meaning it must contain fewer elements than set [latex]A[\/latex].<\/p>\r\n<p>&nbsp;<\/p>\r\n<center>If [latex]B[\/latex] is a proper subset of [latex]A[\/latex], we write [latex]B \\subset A[\/latex]<\/center><\/div>\r\n<\/section>\r\n<section class=\"textbox seeExample\">Given the\u00a0set: [latex]A = \\{a, b, c, d\\}[\/latex]. List all of the subsets of [latex]A[\/latex]<br \/>\r\n[reveal-answer q=\"417709\"]Show Solution[\/reveal-answer]<br \/>\r\n[hidden-answer a=\"417709\"]\r\n<p style=\"text-align: center;\">[latex]\\{\\} (\\text{or } \\emptyset), \\{a\\}, \\{b\\}, \\{c\\}, \\{d\\}, \\{a,b\\}, \\{a,c\\}, \\{a,d\\}, \\{b,c\\}, \\{b,d\\}, \\{c,d\\}, \\{a,b,c\\},[\/latex][latex] \\{a,b,d\\}, \\{a,c,d\\}, \\{b,c,d\\}, \\{a,b,c,d\\}[\/latex]<\/p>\r\nYou can see that there are [latex]16[\/latex] subsets, [latex]15[\/latex] of which are proper subsets.[\/hidden-answer]<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]2201[\/ohm2_question]<\/section>\r\n<h2>Set Operations<\/h2>\r\n<p>Commonly, sets interact. For example, you and a new roommate decide to have a house party, and you both invite your circle of friends. At this party, two sets are being combined, though it might turn out that there are some friends that were in both sets.<\/p>\r\n<section class=\"textbox keyTakeaway\">\r\n<div>\r\n<h3>set operations: union, intersection, complement, and difference<\/h3>\r\n<ul>\r\n\t<li>The <strong>union<\/strong> of two sets contains all the elements contained in either set (or both sets).\r\n\r\n\r\n<ul>\r\n\t<li>The union is notated [latex]A \\cup B[\/latex].\u00a0More formally, [latex]x \\in A \\cup B[\/latex] if [latex]x \\in A[\/latex] or [latex]x \\in B[\/latex] (or both).<\/li>\r\n<\/ul>\r\n<\/li>\r\n\t<li>The <strong>intersection <\/strong>of two sets contains only the elements that are in both sets.\r\n\r\n\r\n<ul>\r\n\t<li>The intersection is notated [latex]A \\cap B[\/latex]. More formally, [latex]x \\in A \\cap B[\/latex] if [latex]x \\in A[\/latex] and [latex]x \\in B[\/latex].<\/li>\r\n<\/ul>\r\n<\/li>\r\n\t<li>The <strong>complement<\/strong> of a set [latex]A[\/latex] contains everything that is <em>not<\/em> in the [latex]A[\/latex].\r\n\r\n\r\n<ul>\r\n\t<li>The complement is notated [latex]A'[\/latex], or [latex]A^c[\/latex], or sometimes \u00a0~[latex]A[\/latex].<\/li>\r\n<\/ul>\r\n<\/li>\r\n\t<li>The <strong>difference<\/strong> of two sets is the list of all the elements that are in one set but not present in the other.\r\n\r\n\r\n<ul>\r\n\t<li>The difference between two sets is notated [latex]A \\setminus B[\/latex]. More formally, [latex]x \\in A \\setminus B[\/latex] if [latex]x \\in A[\/latex] &amp; [latex]x \\notin B [\/latex].<\/li>\r\n<\/ul>\r\n<\/li>\r\n<\/ul>\r\n<\/div>\r\n<\/section>\r\n<section class=\"textbox proTip\">Notice in the descriptions of the notation introduced above that the\u00a0<strong>complement<\/strong> of a set is denoted [latex]A^{c}[\/latex]. This superscript is\u00a0not an exponent. It is a decoration that denotes\u00a0<strong>the complement of a set<\/strong>.<\/section>\r\n<p>Let\u2019s try applying the set operations.<\/p>\r\n<section class=\"textbox seeExample\">Consider the sets: [latex]A = \\{\\text{red, green, blue}\\}[\/latex],\u00a0 [latex] B = \\{\\text{red, yellow, orange}\\}[\/latex],\u00a0 [latex]C = \\{\\text{red, orange, yellow, green, blue, purple}\\}[\/latex].\u00a0\r\n\r\n\r\n<p>Find the following:<\/p>\r\n<ol>\r\n\t<li>Find [latex]A \\cup B[\/latex]<\/li>\r\n\t<li>Find [latex]A \\cap B[\/latex]<\/li>\r\n\t<li>Find [latex]A^c \\cap C[\/latex]<\/li>\r\n<\/ol>\r\n\r\n\r\n[reveal-answer q=\"3541\"]Show Solution[\/reveal-answer] [hidden-answer a=\"3541\"]\r\n\r\n\r\n<ol>\r\n\t<li>The union contains all the elements in either set: [latex]A \\cup B = \\{\\text{red, green, blue, yellow, orange}\\}[\/latex] Notice we only list red once.<\/li>\r\n\t<li>The intersection contains all the elements in both sets: [latex]A \\cap B = \\{\\text{red}\\}[\/latex]<\/li>\r\n\t<li>Here we\u2019re looking for all the elements that are <em>not<\/em> in set [latex]A[\/latex] and are also in [latex]C[\/latex] . [latex]A^c \\cap C = \\{\\text{orange, yellow, purple}\\}[\/latex]<\/li>\r\n<\/ol>\r\n\r\n\r\n[\/hidden-answer]<\/section>\r\n<section class=\"textbox tryIt\">[ohm2_question hide_question_numbers=1]2203[\/ohm2_question]<\/section>","rendered":"<section class=\"textbox learningGoals\">\n<ul>\n<li>Understand sets, including union, intersection, and subsets<\/li>\n<\/ul>\n<\/section>\n<h2>Set Theory<\/h2>\n<p>A movie lover might own a collection of movie posters, while a music lover might keep a collection of vinyl records. Any collection of items can form a <strong>set<\/strong>.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>set<\/h3>\n<p>A <strong>set<\/strong> is a collection of distinct objects, called <strong>elements<\/strong> of the set.<\/p>\n<p>&nbsp;<\/p>\n<p>A set can be defined by describing the contents, or by listing the elements of the set, enclosed in curly brackets separated by commas.<\/p>\n<p>&nbsp;<\/p>\n<p>Repeated elements in a set are only listed once. A set simply specifies the contents; order is not important.<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\">The set represented by [latex]\\{1, 2, 3\\}[\/latex] is equivalent to the set [latex]\\{3, 1, 2\\}[\/latex].<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox example\">Some examples of sets defined by describing the contents:<\/p>\n<ol>\n<li>The set of all even numbers<\/li>\n<li>The set of all books written about travel to Chile<\/li>\n<\/ol>\n<p>Some examples of sets defined by listing the elements of the set:<\/p>\n<ol>\n<li>[latex]\\{1, 3, 9, 12\\}[\/latex]<\/li>\n<li>[latex]\\{\\text{red, orange, yellow, green, blue, indigo, purple}\\}[\/latex]<\/li>\n<\/ol>\n<\/section>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>set notation<\/h3>\n<p>Commonly, we will use a variable to represent a set, to make it easier to refer to that set later.<\/p>\n<p>&nbsp;<\/p>\n<p>The symbol [latex]\\in[\/latex]\u00a0means \u201cis an element of\u201d.<\/p>\n<p>&nbsp;<\/p>\n<p>A set that contains no elements, [latex]\\{ \\}[\/latex], is called the <strong>empty set<\/strong> or null set and is notated [latex]\\emptyset[\/latex].<\/p>\n<\/div>\n<\/section>\n<section class=\"textbox example\">Let [latex]A=\\{1,2,3,4\\}[\/latex]To notate that [latex]2[\/latex] is element of the set, we&#8217;d write [latex]2 \\in A[\/latex]<\/section>\n<p>Sometimes a collection might not contain all the elements of a set. For example, Marta owns ninety-five Pok\u00e9mon cards. While Marta\u2019s collection is a set, we can also say it is a <strong>subset<\/strong> of the larger set of all Pok\u00e9mon cards.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>subset<\/h3>\n<p>A <strong>subset<\/strong> of a set [latex]A[\/latex] is a set that consists solely of elements drawn from set [latex]A[\/latex].<\/p>\n<p>&nbsp;<\/p>\n<p>It may include all, some, or none of set [latex]A[\/latex]&#8216;s elements. In other words, every element in the subset is also an element of set [latex]A[\/latex].<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\">If [latex]B[\/latex] is a subset of [latex]A[\/latex], we write [latex]B \\subseteq A[\/latex]<\/div>\n<div style=\"text-align: center;\"><\/div>\n<p>&nbsp;<\/p>\n<p>A <strong>proper subset<\/strong> of a set [latex]A[\/latex] is a subset that contains some, but not all, of the elements of set [latex]A[\/latex].<\/p>\n<p>&nbsp;<\/p>\n<p>It is a subset that is not identical to the original set, meaning it must contain fewer elements than set [latex]A[\/latex].<\/p>\n<p>&nbsp;<\/p>\n<div style=\"text-align: center;\">If [latex]B[\/latex] is a proper subset of [latex]A[\/latex], we write [latex]B \\subset A[\/latex]<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox seeExample\">Given the\u00a0set: [latex]A = \\{a, b, c, d\\}[\/latex]. List all of the subsets of [latex]A[\/latex]<\/p>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q417709\">Show Solution<\/button><\/p>\n<div id=\"q417709\" class=\"hidden-answer\" style=\"display: none\">\n<p style=\"text-align: center;\">[latex]\\{\\} (\\text{or } \\emptyset), \\{a\\}, \\{b\\}, \\{c\\}, \\{d\\}, \\{a,b\\}, \\{a,c\\}, \\{a,d\\}, \\{b,c\\}, \\{b,d\\}, \\{c,d\\}, \\{a,b,c\\},[\/latex][latex]\\{a,b,d\\}, \\{a,c,d\\}, \\{b,c,d\\}, \\{a,b,c,d\\}[\/latex]<\/p>\n<p>You can see that there are [latex]16[\/latex] subsets, [latex]15[\/latex] of which are proper subsets.<\/p><\/div>\n<\/div>\n<\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm2201\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=2201&theme=lumen&iframe_resize_id=ohm2201&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n<h2>Set Operations<\/h2>\n<p>Commonly, sets interact. For example, you and a new roommate decide to have a house party, and you both invite your circle of friends. At this party, two sets are being combined, though it might turn out that there are some friends that were in both sets.<\/p>\n<section class=\"textbox keyTakeaway\">\n<div>\n<h3>set operations: union, intersection, complement, and difference<\/h3>\n<ul>\n<li>The <strong>union<\/strong> of two sets contains all the elements contained in either set (or both sets).\n<ul>\n<li>The union is notated [latex]A \\cup B[\/latex].\u00a0More formally, [latex]x \\in A \\cup B[\/latex] if [latex]x \\in A[\/latex] or [latex]x \\in B[\/latex] (or both).<\/li>\n<\/ul>\n<\/li>\n<li>The <strong>intersection <\/strong>of two sets contains only the elements that are in both sets.\n<ul>\n<li>The intersection is notated [latex]A \\cap B[\/latex]. More formally, [latex]x \\in A \\cap B[\/latex] if [latex]x \\in A[\/latex] and [latex]x \\in B[\/latex].<\/li>\n<\/ul>\n<\/li>\n<li>The <strong>complement<\/strong> of a set [latex]A[\/latex] contains everything that is <em>not<\/em> in the [latex]A[\/latex].\n<ul>\n<li>The complement is notated [latex]A'[\/latex], or [latex]A^c[\/latex], or sometimes \u00a0~[latex]A[\/latex].<\/li>\n<\/ul>\n<\/li>\n<li>The <strong>difference<\/strong> of two sets is the list of all the elements that are in one set but not present in the other.\n<ul>\n<li>The difference between two sets is notated [latex]A \\setminus B[\/latex]. More formally, [latex]x \\in A \\setminus B[\/latex] if [latex]x \\in A[\/latex] &amp; [latex]x \\notin B[\/latex].<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n<\/section>\n<section class=\"textbox proTip\">Notice in the descriptions of the notation introduced above that the\u00a0<strong>complement<\/strong> of a set is denoted [latex]A^{c}[\/latex]. This superscript is\u00a0not an exponent. It is a decoration that denotes\u00a0<strong>the complement of a set<\/strong>.<\/section>\n<p>Let\u2019s try applying the set operations.<\/p>\n<section class=\"textbox seeExample\">Consider the sets: [latex]A = \\{\\text{red, green, blue}\\}[\/latex],\u00a0 [latex]B = \\{\\text{red, yellow, orange}\\}[\/latex],\u00a0 [latex]C = \\{\\text{red, orange, yellow, green, blue, purple}\\}[\/latex].\u00a0<\/p>\n<p>Find the following:<\/p>\n<ol>\n<li>Find [latex]A \\cup B[\/latex]<\/li>\n<li>Find [latex]A \\cap B[\/latex]<\/li>\n<li>Find [latex]A^c \\cap C[\/latex]<\/li>\n<\/ol>\n<div class=\"qa-wrapper\" style=\"display: block\"><button class=\"show-answer show-answer-button collapsed\" data-target=\"q3541\">Show Solution<\/button> <\/p>\n<div id=\"q3541\" class=\"hidden-answer\" style=\"display: none\">\n<ol>\n<li>The union contains all the elements in either set: [latex]A \\cup B = \\{\\text{red, green, blue, yellow, orange}\\}[\/latex] Notice we only list red once.<\/li>\n<li>The intersection contains all the elements in both sets: [latex]A \\cap B = \\{\\text{red}\\}[\/latex]<\/li>\n<li>Here we\u2019re looking for all the elements that are <em>not<\/em> in set [latex]A[\/latex] and are also in [latex]C[\/latex] . [latex]A^c \\cap C = \\{\\text{orange, yellow, purple}\\}[\/latex]<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/section>\n<section class=\"textbox tryIt\"><iframe loading=\"lazy\" id=\"ohm2203\" class=\"resizable\" src=\"https:\/\/ohm.one.lumenlearning.com\/multiembedq.php?id=2203&theme=lumen&iframe_resize_id=ohm2203&source=tnh\" width=\"100%\" height=\"150\"><\/iframe><\/section>\n","protected":false},"author":16,"menu_order":2,"template":"","meta":{"_candela_citation":"[{\"type\":\"cc-attribution\",\"description\":\"Prealgebra\",\"author\":\"\",\"organization\":\"OpenStax\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"Download for free at http:\/\/cnx.org\/contents\/caa57dab-41c7-455e-bd6f-f443cda5519c@9.757\"},{\"type\":\"original\",\"description\":\"Revision and Adaptation\",\"author\":\"\",\"organization\":\"Lumen Learning\",\"url\":\"\",\"project\":\"\",\"license\":\"cc-by\",\"license_terms\":\"\"}]","pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"part":75,"module-header":"background_you_need","content_attributions":[{"type":"cc-attribution","description":"Prealgebra","author":"","organization":"OpenStax","url":"","project":"","license":"cc-by","license_terms":"Download for free at http:\/\/cnx.org\/contents\/caa57dab-41c7-455e-bd6f-f443cda5519c@9.757"},{"type":"original","description":"Revision and Adaptation","author":"","organization":"Lumen Learning","url":"","project":"","license":"cc-by","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\/2842"}],"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\/16"}],"version-history":[{"count":30,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2842\/revisions"}],"predecessor-version":[{"id":12793,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapters\/2842\/revisions\/12793"}],"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\/2842\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/media?parent=2842"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/pressbooks\/v2\/chapter-type?post=2842"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/contributor?post=2842"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/content.one.lumenlearning.com\/quantitativereasoning\/wp-json\/wp\/v2\/license?post=2842"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}