代做2023-24 Discrete Systems–Summative代做Python编程

日期：2024-04-05 04:41

2023-24 Discrete Systems–Summative

Submission date and time: 23/04/2024, 2:00pm

Submission format: one single PDF file and one Python (.py) file

This summative assessment is about matchings and vertex covers in graphs. You must carefully and clearly justify all your answers.

In the following let G = (V ,E) be an undirected graph. An edge e ∈ E which has the vertices u and v as endpoints is denoted by e = uv.

A matching in the undirected graph G = (V ,E) is a set of non-adjacent edgesin G. Let μ(G) be the maximum (i.e. the largest possible) number of edges in a matching in G. For instance, the cycle Cn  on n vertices satisfies μ(Cn ) = ⌊n/2⌋ .

A vertex cover in the undirected graph G = (V ,E) is a subset of vertices S which intersects any edge: for any e = uv ∈ E, either u or v (or both) is in S. Let τ(G) be the minimum size of a vertex cover in G. For instance, the cycle Cn  satisfies τ(Cn ) = ⌈n/2⌉ .

Question 1 (30 marks). Express μ(G) and τ(G) as optimal values of two integer programs whose relax- ations are dual to each other. Justify your answer.

Recall that a graph G is bipartite if its vertex set can be partitioned into two independent sets.

Question 2 (20 marks). Prove that if G is bipartite, then μ(G) = τ(G). Hint: you may use the max-flow min-cut theorem.

A fractional matching of G is any feasible solution of the linear relaxation of the integer program above for matching (see Question 1). The maximum value of a fractional matching is denoted as μ∗(G), it is the optimal value of the relaxation of either integer programs for matching and for vertex cover in Question 1. For instance, μ∗(Cn ) = n/2.

Question 3 (20 marks). Using the IP and LP formulations of Question 1, write a Python program, which for a given graph G computes a maximum matching, a minimum vertex cover, and a maximum fractional matching of G.

You must use the CBC solver available from the Python package MIP. The program input should be a Graph object from the Python package networkx, and the output should be printed to the screen.

For every vertex v ∈ V, we denote by N(v) = {u ∈ V : uv ∈ E} the neighborhood of v, i.e. N(v) is the set of all vertices u in the graph such that there is an edge between u and v. Note that no vertex v can belong to its own neighborhood,i.e. v ∉ N(v) for every v ∈ V.

A vertex cover S of a graph G is minimal if there is no vertex cover T of G such that T ⊂ S.

Question 4 (20 marks). Let G = (V ,E) be a graph on the vertices V = {1, . . . , n}. For every vertex i ∈ V let xi ∈ {0, 1} be a binary variable, and denote by x = (x1 , x2 , . . . , xn) the n-vector of these binary values.  For any i ∈ V, define the function fi  : {0, 1}n → {0, 1} such that, for every x = (x1 , x2 , . . . , xn) ∈ {0, 1}n, we have:

fi(x) = ， (¬xj).

j∈N(i)

Then define the function f : {0, 1}n  → {0, 1}n  (a generalized cellular automaton) such that, for every x = (x1 , x2 , . . . , xn) ∈ {0, 1}n, we have:

f(x) = (f1 (x), . . . , fn (x)).

Prove that the fixed points off are in one-to-one correspondence with the minimal vertex covers ofG.

Hint: Recall that x = (x1 , x2 , . . . , xn) is a fixed point of the function f if and only if we have that f(x) = x, i.e. f(x1 , x2 , . . . , xn) = (x1 , x2 , . . . , xn).

A dominating set of G is a set of vertices D ⊆ V such that for any v ∈ D , N(v) UD ≠ Q.

Question 5 (10 marks). Exhibit another generalized cellular automaton whose fixed points are in one- to-one correspondence with the dominating sets of G.