aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--tech-math/ws2.tex48
1 files changed, 47 insertions, 1 deletions
diff --git a/tech-math/ws2.tex b/tech-math/ws2.tex
index 28c5da8..0251a1d 100644
--- a/tech-math/ws2.tex
+++ b/tech-math/ws2.tex
@@ -1,4 +1,5 @@
\input ws-form.tex
+\input tikz.tex%have to draw graphs
{\bf \noindent\line{Math 3012-QHS \hfil Name: \rm \underline{Holden Rohrer}}
Fall 2019\par\noindent
@@ -7,7 +8,7 @@ Due 09/10/2019}
\smallskip \hrule \medskip
\question{
-Q1 - Consider the set $X={1,2,3,4,5}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the 2-element subsets of X. Can you put these 10 pigeons into the two holes in a way that there is no 3-element subset $S={a,b,c} \subset X$ for which all pigeons from $S$ go in the same hole? Then answer the same question if $X={1,2,3,4,5,6} with $15=C(6,2)$ pigeons.
+Q1 - Consider the set $X={1,2,3,4,5}$ and suppose you have two holes. Also suppose that you have 10 pigeons: the 2-element subsets of X. Can you put these 10 pigeons into the two holes in a way that there is no 3-element subset $S={a,b,c} \subset X$ for which all pigeons from $S$ go in the same hole? Then answer the same question if $X={1,2,3,4,5,6}$ with $15=C(6,2)$ pigeons.
}{
Each 3-element subset has 3 2-element subsets, so $m=3$. Treating the number of holes as $n$, we have greater than $mn+1=3\cdot 2+1=7$ pigeons, so there is no way to satisfy the condition. By the same calculus, a 6-element set cannot be organized in such a way to fulfil this condition.
}\vfil
@@ -20,9 +21,54 @@ Communicating such information would be impossible unless another symbolic defin
For example, $N = x \in S : 0 \notin x$ is easily communicable, as any set I have a hunch about would likely be, but most sets satisfying these solutions cannot---in general---be easily communicated.
}\vfil\eject
\question{
+Considering graph G in Figure 5.47,
+a) Let $V_1 = {g,j,c,h,e,f}$ and $E_1={ge,jg,ch,ef}$. Is $(V_1,E_1)$ a subgraph of $\bf G$?
+
+c) Let $V_3 = {a,d,c,h,b}$ and $E_3={ch,ac,ad,bc}$. Is $(V_3,E_3)$ an induced subgraph of $\bf G$?
+
+e) Draw the subgraph of $\bf G$ induced by {c,h,f,i,j}
+
+f) Draw a subgraph of $\bf G$ having vertex set ${e,f,b,c,h,j}$ that is {\it not} an induced subgraph.
+
+g) Draw a spanning subgraph of $\bf G$ with exactly 10 edges.
}{
+a) Yes because $V_1 \subset V_G$ and $E_1 \subset E_G$.
+
+c) No because $dh \in V_G$ but $dh \notin V_3$ and $d, h \in E_3, E_G$
+
+e) \tikzpicture
+ \draw (2,0) -- (1,0) -- (0,0) -- (0, 1); %ifhc
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {i};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {f};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {h};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (3,1) {j};
+ \endtikzpicture
+
+f) \tikzpicture
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {c};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,0) {h};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {f};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,1) {e};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (2,0) {b};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {j};
+ \endtikzpicture
+g) \tikzpicture
+ %abcdghij
+ \draw (0,0) -- (0,1) -- (0,2) -- (1,2) -- (3,2) -- (0,1);%bchdac
+ \draw (1.75,3) -- (3,2) -- (1,5) -- (0,2);%gaih
+ \draw (1.75,3) -- (0.75,3) -- (1,2);%gjd
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,0) {b};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,1) {c};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0,2) {h};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,2) {d};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (3,2) {a};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1.75,3) {g};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (1,5) {i};
+ \node[draw,circle,inner sep=0.1cm,fill=white] () at (0.75,3) {j};
+ \endtikzpicture
}
\bye