Search

10: Trees
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/10%3A_Trees
In this chapter we will study the class of graphs called trees. Trees are frequently used in both mathematics and the sciences. Our solution of Example 2.1.1 is one simple instance. Since they are oft...In this chapter we will study the class of graphs called trees. Trees are frequently used in both mathematics and the sciences. Our solution of Example 2.1.1 is one simple instance. Since they are often used to illustrate or prove other concepts, a poor understanding of trees can be a serious handicap. For this reason, our ultimate goals are to: (1) define the various common types of trees, (2) identify some basic properties of trees, and (3) discuss some of the common applications of trees.
12.1: Posets Revisited
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/12%3A_Boolean_Algebra/12.01%3A_Posets_Revisited
Consider the poset $(\mathcal{P}(A),\subseteq)\text{,}$ where $A = \{1, 2, 3\}\text{.}$ The greatest lower bound of $\{1, 2\}$ and $\{1,3\}$ is $\ell = \{1\}\text{.}$ For any other element \...Consider the poset $(\mathcal{P}(A),\subseteq)\text{,}$ where $A = \{1, 2, 3\}\text{.}$ The greatest lower bound of $\{1, 2\}$ and $\{1,3\}$ is $\ell = \{1\}\text{.}$ For any other element $\ell'$ which is a subset of $\{a, b\}$ and $\{a, c\}$ (there is only one; what is it?), $\ell' \subseteq \ell\text{.}$ The least element of $\mathcal{P}(A)$ is $\emptyset$ and the greatest element is $A=\{a, b, c\}\text{.}$ The Hasse diagram of this poset is shown in Figure \(\PageInd…
TitlePage
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/00%3A_Front_Matter/01%3A_TitlePage
Applied Discrete Structures Al Doerr Ken Levasseur Department of Mathematical Sciences University of Massachusetts Lowell kenneth_levasseur@uml.edu May 25, 2021
Preface
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/00%3A_Front_Matter/07%3A_Preface
We had signed a contract for the second edition with Science Research Associates in 1988 but by the time the book was ready to print, SRA had been sold to MacMillan. The open source software movement ...We had signed a contract for the second edition with Science Research Associates in 1988 but by the time the book was ready to print, SRA had been sold to MacMillan. The open source software movement was just starting in the late 1980's and in 2005, the first version of Sage (later renamed SageMath), an open-source computer algebra system, was first released.
12.5: Some Applications
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/12%3A_More_Matrix_Algebra/12.05%3A_Some_Applications
\begin{equation*} \begin{split} e^Ae^B &= \left(\sum _{k=0}^{\infty } \frac{A^k}{k!}\right) \left(\sum _{k=0}^{\infty } \frac{B^k}{k!}\right)\\ & =\left(I + A+\frac{A^2}{2}+ \frac{A^3}{6}+ \cdots \rig...\begin{equation*} \begin{split} e^Ae^B &= \left(\sum _{k=0}^{\infty } \frac{A^k}{k!}\right) \left(\sum _{k=0}^{\infty } \frac{B^k}{k!}\right)\\ & =\left(I + A+\frac{A^2}{2}+ \frac{A^3}{6}+ \cdots \right)\left(I +B+\frac{B^2}{2}+ \frac{B^3}{6}+ \cdots \right)\\ &= I + A + B+ \frac{A^2}{2}+ A B + \frac{B^2}{2}+\frac{A^3}{6}+ \frac{A^2B}{2}+\frac{A B^2}{2}+ \frac{B^3}{6}+\cdots \\ &= I + (A+B) + \frac{1}{2}\left(A^2+ 2 A B + B^2\right)+ \frac{1}{6}\left(A^3+ 3A^2B+ 3A B^2+ B^3\right)+\cdots \\ &=I…
10.2: Spanning Trees
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/10%3A_Trees/10.02%3A_Spanning_Trees
The method that we have used (in Step 2.1) to select a bridge when more than one minimally weighted bridge exists is to order all bridges alphabetically by the vertex in $L$ and then, if further tie...The method that we have used (in Step 2.1) to select a bridge when more than one minimally weighted bridge exists is to order all bridges alphabetically by the vertex in $L$ and then, if further ties exist, by the vertex in $R\text{.}$ The first vertex in that order is selected in Step 2.1 of the algorithm.
12.2: Lattices
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/12%3A_Boolean_Algebra/12.02%3A_Lattices
\begin{equation*} \begin{array}{cc} \begin{array}{c|ccccc} \lor & \pmb{0} & a & b & c & \pmb{1} \\ \hline \pmb{0} & \pmb{0} & a & b & c & \pmb{1} \\ a & a & a & \pmb{1} & \pmb{1} & \pmb{1} \\ b & b & ...\begin{equation*} $\begin{array}{cc} \begin{array}{c|ccccc} \lor & \pmb{0} & a & b & c & \pmb{1} \\ \hline \pmb{0} & \pmb{0} & a & b & c & \pmb{1} \\ a & a & a & \pmb{1} & \pmb{1} & \pmb{1} \\ b & b & \pmb{1} & b & \pmb{1} & \pmb{1} \\ c & c & \pmb{1} & \pmb{1} & c & \pmb{1} \\ \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} & \pmb{1} \\ \end{array}$ & \begin{array}{c|ccccc} \land & \pmb{0} & a & b & c & \pmb{1} \\ \hline \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} & \pmb{0} \\ a & \pmb{0} & …
13.5: The Machine of a Monoid
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/13%3A_Monoids_and_Automata/13.05%3A_The_Machine_of_a_Monoid
Will we obtain a unit-time delay machine when we construct the machine of $U\text{?}$ We can't expect to get exactly the same machine because the unit-time delay machine is not a state machine and t...Will we obtain a unit-time delay machine when we construct the machine of $U\text{?}$ We can't expect to get exactly the same machine because the unit-time delay machine is not a state machine and the machine of a monoid is a state machine.
12.4: Atoms of a Boolean Algebra
https://math.libretexts.org/Courses/SUNY_Schenectady_County_Community_College/Discrete_Structures/12%3A_Boolean_Algebra/12.04%3A_Atoms_of_a_Boolean_Algebra
Certainly, the Boolean algebras $\left[D_{30}; \lor , \land, \land\bar{\hspace{5 mm}} \right]$ and $[\mathcal{P}(A); \cup , \cap, \hspace{1 mm}^c]$ have the same graph (that of Figure \(\PageIndex...Certainly, the Boolean algebras $\left[D_{30}; \lor , \land, \land\bar{\hspace{5 mm}} \right]$ and $[\mathcal{P}(A); \cup , \cap, \hspace{1 mm}^c]$ have the same graph (that of Figure $\PageIndex{1}$ ), the same number of atoms, and, in all respects, look the same except for the names of the elements and the operations.
15.4: Normal Subgroups and Group Homomorphisms
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/15%3A_Group_Theory_and_Applications/15.04%3A_Normal_Subgroups_and_Group_Homomorphisms
$\langle r\rangle =\left\{i,r,r^2,r^3\right\}$ is a normal subgroup of $D_4\text{.}$ To see you could use the table given in the solution of Exercise 15.3.5 of Section 15.3 and verify that \(a^{-1... $\langle r\rangle =\left\{i,r,r^2,r^3\right\}$ is a normal subgroup of $D_4\text{.}$ To see you could use the table given in the solution of Exercise 15.3.5 of Section 15.3 and verify that $a^{-1}h a \in \langle r\rangle$ for all $a\in D_4$ and $h\in \langle r\rangle\text{.}$ A more efficient approach is to prove the general theorem that if $H$ is a subgroup $G$ with exactly two distinct left cosets, than $H$ is normal. $\left\langle f_1\right\rangle$ is not a normal subgroup …
Colophon
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_Discrete_Structures_(Doerr_and_Levasseur)/00%3A_Front_Matter/04%3A_Colophon
Edition 3rd Edition - version 8 ©2021 Al Doerr, Ken Levasseur Applied Discrete Structures by Alan Doerr and Kenneth Levasseur is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike ...Edition 3rd Edition - version 8 ©2021 Al Doerr, Ken Levasseur Applied Discrete Structures by Alan Doerr and Kenneth Levasseur is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License. You are free to Share: copy and redistribute the material in any medium or format; Adapt: remix, transform, and build upon the material. You may not use the material for commercial purposes. The licensor cannot revoke these freedoms as long as you follow the license terms.

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?