14.5: Activities
- Page ID
- 93223
\( \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}}} \)
Suppose \(G = (V,E)\) is a graph. Decide the truth of the following statement.
Every pair of a subset \(V' \subseteq V\) and a subcollection \(E' \subseteq E\) defines a subgraph \(G' = (V',E')\) of \(G\text{.}\)
Draw a graph where the nodes are students present in today's class. Draw edges between pairs of students that are in the same group today. Additionally, draw an edge between a member of your group and another student if that pair was in a group together last class.
For each of the following graphs, write out its formal definition as either a (regular) graph, a weigthed graph, or a directed graph, as appropriate.
-
Figure \(\PageIndex{1}\) -
Figure \(\PageIndex{2}\) -
Figure \(\PageIndex{3}\)
Consider the website Facebook as a graph where vertices are profiles and edges represent “friendship”.
- Should this graph be a directed graph? Why or why not?
- Is this graph simple? complete? Justify your answers.
- What does the degree of a vertex represent?
- Could this graph have isolated vertices?
- Suppose the following graph is a subgraph of the Facebook graph.
- What is the largest party one of these people could throw where each party-goer is Facebook friends with every other party-goer? Justify your answer.
- Assume all of the people in this graph live in the same geographic area. Which pair of non-friends are most likely to become friends in the future? Which pair of non-friends are least likely to become friends in the future? Justify your answers.