diff options
| -rw-r--r-- | tech-math/ws2.tex | 48 |
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 |