Search

1.2: Examples
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/01%3A_Fundamentals/1.02%3A_Examples
Suppose we have a chess board, and a collection of tiles, like dominoes, each of which is the size of two squares on the chess board. First we need to be clear on the rules: the board is covered if th...Suppose we have a chess board, and a collection of tiles, like dominoes, each of which is the size of two squares on the chess board. First we need to be clear on the rules: the board is covered if the dominoes are laid down so that each covers exactly two squares of the board; no dominoes overlap; and every square is covered. To make the problem more interesting, we allow the board to be rectangular of any size, and we allow some squares to be removed from the board.
Licensing
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/00%3A_Front_Matter/04%3A_Licensing
A detailed breakdown of this resource's licensing can be found in Back Matter/Detailed Licensing.
5.6: Optimal Spanning Trees
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/05%3A_Graph_Theory/5.06%3A_Optimal_Spanning_Trees
For example, if a graph represents a network of roads, the weight of an edge might be the length of the road between its two endpoints, or the amount of time required to travel from one endpoint to th...For example, if a graph represents a network of roads, the weight of an edge might be the length of the road between its two endpoints, or the amount of time required to travel from one endpoint to the other, or the cost to bury cable along the road from one end to the other.
4.E: Systems of Distinct Representatives (Exercises)
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/04%3A_Systems_of_Distinct_Representatives/4.E%3A_Systems_of_Distinct_Representatives_(Exercises)
An $n\times n$ Latin square $A$ is symmetric if it is symmetric around the main diagonal, that is, $A_{i,j}=A_{j,i}$ for all $i$ and $j$ . The transpose $A^\top$ of a Latin square $A$ is ...An $n\times n$ Latin square $A$ is symmetric if it is symmetric around the main diagonal, that is, $A_{i,j}=A_{j,i}$ for all $i$ and $j$ . The transpose $A^\top$ of a Latin square $A$ is the reflection of $A$ across the main diagonal, so that $A_{i,j}^\top=A_{j,i}$ . Show directly that that the size of a minimum vertex cover in $G$ is the minimum value of $n-k+|\bigcup_{j=1}^k A_{i_j}|$ , as mentioned above.
Front Matter
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/00%3A_Front_Matter
5.11: Directed Graphs
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/05%3A_Graph_Theory/5.11%3A_Directed_Graphs
Thus, the entire sum $S$ has value $\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e).\nonumber$ On the other hand, we can write the sum $S$ as \[ \sum_{v\in U}\sum_{e\in E_v^+}f(e)- \sum_{v\in U}\su...Thus, the entire sum $S$ has value $\sum_{e\in E_s^+} f(e)-\sum_{e\in E_s^-}f(e).\nonumber$ On the other hand, we can write the sum $S$ as $\sum_{v\in U}\sum_{e\in E_v^+}f(e)- \sum_{v\in U}\sum_{e\in E_v^-}f(e). \nonumber$ Every arc $e=(x,y)$ with both $x$ and $y$ in $U$ appears in both sums, that is, in $\sum_{v\in U}\sum_{e\in E_v^+}f(e),\nonumber$ when $v=x$ , and in $\sum_{v\in U}\sum_{e\in E_v^-}f(e),\nonumber$ when $v=y$ , and so the flow in such arcs contributes \(…
InfoPage
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/00%3A_Front_Matter/02%3A_InfoPage
The LibreTexts libraries are Powered by NICE CXOne and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the Californi...The LibreTexts libraries are Powered by NICE CXOne and are supported by the Department of Education Open Textbook Pilot Project, the UC Davis Office of the Provost, the UC Davis Library, the California State University Affordable Learning Solutions Program, and Merlot.
6.3: Burnside's Theorem
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/06%3A_PolyaRedfield_Counting/6.03%3A_Burnside's_Theorem
In cycle notation these permutations are: \[\eqalign{ r_0&=(1)(2)(3)(4)\cr r_{90}&=(1,4,3,2)\cr r_{180}&=(1,3)(2,4)\cr r_{270}&=(1,2,3,4)\cr f_H&=(1,4)(2,3)\cr f_V&=(1,2)(3,4)\cr f_D&=(1)(2,4)(3)\cr f...In cycle notation these permutations are: $\eqalign{ r_0&=(1)(2)(3)(4)\cr r_{90}&=(1,4,3,2)\cr r_{180}&=(1,3)(2,4)\cr r_{270}&=(1,2,3,4)\cr f_H&=(1,4)(2,3)\cr f_V&=(1,2)(3,4)\cr f_D&=(1)(2,4)(3)\cr f_A&=(1,3)(2)(4).\cr }\nonumber$ so the number of colorings is $f(k)={1\over 8}(k^4+k+k^2+k+k^2+k^2+k^3+k^3)={1\over8}(k^4+2k^3+3k^2+2k).\nonumber$ For example, $f(2)=6$ ; the six colorings are shown in Figure $\PageIndex{4}$ .
3.5: Recurrence Relations
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/03%3A_Generating_Functions/3.05%3A_Recurrence_Relations
A recurrence relation defines a sequence by expressing a typical term in terms of earlier terms. Note that some initial values must be specified for the recurrence relation to define a unique sequence...A recurrence relation defines a sequence by expressing a typical term in terms of earlier terms. Note that some initial values must be specified for the recurrence relation to define a unique sequence. The starting index for the sequence need not be zero if it doesn't make sense or some other starting index is more convenient.
6.1: Prelude to Pólya–Redfield Counting
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/06%3A_PolyaRedfield_Counting/6.01%3A_Prelude_to_P%C3%B3lya%E2%80%93Redfield_Counting
Suppose we want to consider colorings to be "the same'' if one can be produced from the other by a reflection, but not if one can be obtained from the other by rotation. For example, if we say a rotat...Suppose we want to consider colorings to be "the same'' if one can be produced from the other by a reflection, but not if one can be obtained from the other by rotation. For example, if we say a rotation by $54^\circ$ degrees produces a coloring that we consider to be the same, a rotation by $-54^\circ$ must be included as well (we may think of this as a rotation by $306^\circ$ ).
Glossary
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_and_Graph_Theory_(Guichard)/zz%3A_Back_Matter/20%3A_Glossary
Example and Directions Words (or words that have the same definition) The definition is case sensitive (Optional) Image to display with the definition [Not displayed in Glossary, only in pop-up on pag...Example and Directions Words (or words that have the same definition) The definition is case sensitive (Optional) Image to display with the definition [Not displayed in Glossary, only in pop-up on pages] (Optional) Caption for Image (Optional) External or Internal Link (Optional) Source for Definition "Genetic, Hereditary, DNA ...") (Eg. "Relating to genes or heredity") The infamous double helix CC-BY-SA; Delmar Larsen Glossary Entries Definition Image Sample Word 1 Sample Definition 1

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?