﻿ 离散数学问题代写 Discrete  Mathematics代写 - 作业代写, 数学代写

# 离散数学问题代写 Discrete  Mathematics代写

2021-09-17 15:51 星期五 所属： 作业代写 浏览：43 ## Assignment 2

### Question 1 (20 marks)

In how  many ways  can the numbers 0 through (2– 1) be arranged in 2 rows of length n in such a way such that each row and each column is increasing? Examples (with n = 5):

and Hint:  Catalan Numbers.

### Question 2 (20 marks)  离散数学问题代写

A periodic point of a function f X → X is a point x∈ X for which there is a number p (a period ) with f p(x) = x (f p denotes the composite (f º. .  f ) of f with itself p times ）. A xpoint is a periodic point with minimal period p = 1, that is, a point x∈ X such that f (x) = x.

For X ={ 1, 2, . . . n}, count the number of functions f : X→ X such that each periodic point is a xpoint.

Hint: What kind of vertebrate do you get when you apply Joyal’s bijection on a function like this?

### Question 3 (20 marks)  离散数学问题代写

The chromatic polynomial of a graph G is the function PG(k) that gives the number of ways to color the vertices of G using k colors, such that no two adjacent vertices have the same color.

a）If L is a path (linear graph) with n vertices, show that PL(k) = k(k 1)n1.

b）Let Cnbe the cyclic graph with n Find PC3(k).

c）Show that for n > 3, PCn (k) satis es therecurrence:

PCn (k) = k(k 1)n1 PCn1 (k) .

d）Solve the recurrence above to nd a short expression forPCn (k).

### Question 4 (20 marks)  离散数学问题代写

In this problem, we investigate the edge-chromatic number χE(Kn) of complete graphs Kn.

a）Show that coloring the edge ij with color i + j (mod n) gives a valid edge coloring ofKn.

b）Show that if n is odd, then χE(Kn) =n.

c）Show that if n is even, then χE(Kn) = n 1.

Hint: Kn is Kn1 with one extra vertex, and n 1 is odd…

### Question 5 (20 marks)  离散数学问题代写

The goal of this problem is to prove some of the many cases of the 4-colors theorem. Let our four colors be: red, blue, green and yellow.

Assume that the 4-colors theorem is proven for all planar graphs with less than n vertices and that G is a graph with n vertices that contains the following subgraph. We remove the four vertices w, x, y, z in the middle, resulting in a smaller planar graph, and let the induction hypothesis give us a coloring of the six outer vertices a, b, c, d, e, f . We call such a coloring a con guration. Then…

a）Suppose that the induction hypothesis gave us the following con guration. Conclude that G is4-colorable.

b）Suppose instead that we have the following con guration. Use the Kempe-Chain argument to modify the coloring on G so that you can complete it and conclude  that G is4-colorable. Hint: Consider the possible connected components of Red-Yellow subgraph GRY or the Green-Blue subgraph GttB

c）Now, say that the induction hypothesis gave us the following con guration. Use another Kempe-Chain argument to modify the coloring in order to end up with the coloringin part (a) or (b). Deduce that G is 4-colorable again in that case.

Note: Now you have a fairly good idea of how the 4-colors theorem was originally proved. The idea is to build a tree (actually, a forest) of con gurations that are reducible to one another by a Kempe-Chain argument, so that the leaves of this forest can be completed directly like in (a). The issue is that the forest built by Appel and Haken’s program has 1936 nodes rather than just the 3 nodes you just checked, which is why the help of a computer was required. 