6.042J / 18.062J Mathematics for Computer Science (SMA by Nagpal, Radhika; Meyer, Albert R

By Nagpal, Radhika; Meyer, Albert R

Show description

Read Online or Download 6.042J / 18.062J Mathematics for Computer Science (SMA 5512), Fall 2002 PDF

Similar mathematics books

Additional resources for 6.042J / 18.062J Mathematics for Computer Science (SMA 5512), Fall 2002

Example text

2 The only completely general way known for finding the chromatic number of a graph is to ex­ haustively try all possible colorings; the exhaustive approach really is exhausting, and it becomes prohibitive even for graphs with only a few dozen vertices. Sometimes we can take advantage of the structure of special classes of graphs to get a better grip on their colorings. Also, we can at least put some general upper bounds on the chromatic number. For example, the chromatic number of an n-vertex graph is certainly at most n, since every vertex could be assigned a different color.

Note that a chain is just a path in the corresponding graph. Course Notes 3: Relations 17 Clearly, the parallel time is at least length of any chain. For if we used less time, then two tasks in the chain would have to be done at the same time. ) But by definition of chains this violates precedence constraints. A longest chain is also known as a critical path. So we need at least t steps, where t is the length of the longest chain. 20. Given any finite poset (A, �) for which the longest chain has length t, it is possible to partition A into t subsets, A1 , A2 , · · · , At such that � � (∀i ∈ {1, 2, .

Rewrite the proof more carefully as an induction on the number of edges in a simple graph. 1 to multigraphs. 1 to digraphs. Here is a puzzle that can be addressed with graphs. There is a party. Some people shake hands an even number of times and some shake an odd number of times. Show that an even number of people shake hands an odd number of times. We can represent the party by a graph. ) Each person is represented by a vertex. If two people shake hands, then there is an edge between the corresponding vertices.

Download PDF sample

Rated 4.26 of 5 – based on 22 votes