5.1: Discovering Graphs
- Page ID
- 88868
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Definitions are typically constructed after we work with new objects. The definition is constructed to match the properties we have observed and need. In this section we will practice this by developing a definition for a type of object known as a graph.
Checkpoint \(\PageIndex{3}\)
Based on the examples in Figure \(\PageIndex{1}\) and Figure \(\PageIndex{2}\) determine which of the following are graphs.
Each of these is a graph.
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_3\}\\ q_3 & = \{p_2,p_3\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3,p_4\}\\ Q & =\emptyset \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3,p_4\}\\ Q & =\{q_1,q_2\}\\ q_1 &= \{p_1,p_3\}\\ q_2 & = \{p_2,p_4\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3,p_4,p_5\}\\ L & =\{\ell_1,\ell_2,\ell_3,\ell_4,\ell_5,\ell_6\}\\ \ell_1 & = \{p_2,p_3\}\\ \ell_2 & = \{p_1,p_4\}\\ \ell_3 & = \{p_4,p_5\}\\ \ell_4 & = \{p_1,p_5\}\\ \ell_5 & = \{p_2,p_4\}\\ \ell_6 & = \{p_2,p_5\} \end{align*}
-
\begin{align*} V & =\{c,d,e,f\}\\ E & =\{\{c,d\}, \{d,e\}, \{e,f\},\\ & \{c,f\}\} \end{align*}
-
\begin{align*} V & =\{v_1,v_2,v_3,v_4\}\\ E & =\{\{v_1,v_2\}, \{v_1,v_3\}, \\ & \{v_2,v_3\}, \{v_2,v_4\}\} \end{align*}
-
\begin{align*} P & =\{p\}\\ Q & =\emptyset \end{align*}
-
\begin{align*} P & =\{q,r,s,t\}\\ Q &=\{\{q,r\}, \{r,t\}, \{q,t\}, \{r,s\}\} \end{align*}
None of these is a graph.
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_3,p_4\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_2\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 \&= (p_1,p_2)\\ q_2 & = (p_1,p_3)\\ q_3 & = (p_2,p_3) \end{align*}
-
\begin{align*} V & =\{x,y,z\}\\ E & =\{f,g,h\}\\ f & = (x,y)\\ g & = (y,x)\\ h & = (y,z) \end{align*}
-
\begin{align*} P & =\emptyset\\ Q & =\emptyset \end{align*}
-
\begin{align*} P \& =\{q,r,s,t\}\\ Q & =\{\{q,r\}, \{r,t\}, \{s\} \} \end{align*}
-
\begin{align*} V & =\{p_1,p_2,\ldots,p_n,\ldots\}\\ E & =\{\{p_1,p_2\}, \{p_2,p_4\}, \{p_1,p_3\}, \{p_4,p_6\}\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2,q_3\}\\ q_1 & = \{p_1,p_2\}\\ q_2 & = \{p_1,p_3\} \end{align*}
Checkpoint \(\PageIndex{6}\)
Based on the examples in Example 5.1.4 and Example 5.1.5 determine which of the following are graphs.
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1\}\\ q_1 & = \{p_1,p_3\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\{q_1,q_2\}\\ q_1 & = \{p_1,p_2\} \end{align*}
-
\begin{align*} V & =\{v_1,v_2,\ldots,v_n,\ldots\}\\ E & =\{e_1,e_2,\ldots,e_n,\ldots\}\\ e_1 & = (v_1,v_2)\\ \vdots\\ e_n & = (v_n,v_{n+1})\\ \vdots \end{align*}
-
\begin{align*} P & =\{p,q,r\}\\ Q & =\{t,u,v\}\\ t & = \{p,q\}\\ u & = \{p,r\}\\ v & = \{q,r\} \end{align*}
-
\begin{align*} P & =\{p_1,p_2,p_3\}\\ Q & =\emptyset \end{align*}
-
\begin{align*} V & =\{u_1,u_2,u_3,u_4\}\\ E & =\{(u_1,u_2), (u_2,u_1),\\ & (u_3,u_4)\} \end{align*}
-
\begin{align*} V & =\{v_1,v_2,v_3\}\\ E & =\{\{v_1,v_2\}, \{v_1,v_3\}, \{v_3\}\} \end{align*}
-
\begin{align*} P & =\{p,q,r,s\}\\ Q & =\{\{p,q\}, \{p,r\}, \{p,s\},\\ & \{q,r\}, \{q,s\}, \{r,s\}\} \end{align*}