{
"nbformat_minor": 2,
"nbformat": 4,
"cells": [
{
"source": [
"$$\n",
"\\def\\CC{\\bf C}\n",
"\\def\\QQ{\\bf Q}\n",
"\\def\\RR{\\bf R}\n",
"\\def\\ZZ{\\bf Z}\n",
"\\def\\NN{\\bf N}\n",
"$$\n",
"# Max-flows and bipartite matchings\n",
"\n",
"Authors \n",
"- Vincent Delecroix\n",
"\n",
"License \n",
"CC BY-SA 3.0\n",
"\n",
"To learn about how to write a linear program in Sage you should have a look at the documentation:\n",
"\n",
"- \n",
"- \n",
"\n",
"Let $G$ be an oriented graph with non-negative weights $c: E \\to \\mathbb{R}^+$ on the edges. The weights have to be thought as a capacity, ie $c(e)$ is the maximum quantity of fluid that is allowed to pass through the edge $e$. Now let $s$ and $t$ be two vertices (source and target). We are interested in *flows* in this graph from $s$ to $t$ that is a function $f: E(G) \\to \\mathbb{R}_+$ so that $f(e) \\leq c(e)$ and for each vertex $v \\in V(G) \\setminus \\{s,t\\}$ we have\n",
"\n",
"$$\\sum_{e \\text{ incoming at } v} f(e) = \\sum_{v \\text{ outgoing at v}} f(e).$$\n",
"\n",
"Write a function using a linear program that solves the max-flow (the input is the weighted graph $G$ and two vertices $s$ and $t$)."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Note that linear programing is not the most efficient way to solve the max-flow problem. You might want to have a look in a book about \"combinatorial optimization\" for better algorithms to solve this. Could you find an alternative implementation available in Sage?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Now let $G$ be a (non-oriented) graph. A *matching* in $G$ is a set of edges $F\n",
"\\subset E(G)$ so that no pair of edges in $F$ shares a vertex. Write an integral linear program that find the matching with maximal cardinality on a graph."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"We will now consider the maximum matching on bipartite graph. Given a bipartite graph $G$ with bi-partition $V = V_1 \\cup V_2$ we consider the weighted oriented graph $G'$ whose vertex set is $V' := V \\cup \\{s,t\\}$ and the following edges:\n",
"\n",
"- for each $v \\in V_1$ an edge $s \\to v$\n",
"- for each (unoriented) edge $e = \\{v_1, v_2\\}$ in $G$ where $v_i \\in V_i$ an edge $v_1 \\to v_2$\n",
"- for each $v \\in V_2$ an edge $v \\to t$\n",
"\n",
"The capacity of each edge is $1$.\n",
"\n",
"Show that the maximum matching problem on $G$ can be solved by considering the max-flow in $G'$ from $s$ to $t$. Implement this approach for bipartite graphs"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"How does the performance compare with your integer program?"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"(*hint*: for comparing performance you might want to have a look at the `%time` and `%timeit` IPython magic command)\n",
"\n",
"Now, use the bipartite version of your program to solve the following weighted version of the Hall mariage problem. Let $M$ be a $n \\times n$ matrix with positive entries, compute\n",
"\n",
"$$\\max_{\\sigma \\in S_n} \\sum M_{i, \\sigma(i)}$$"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"How much is this quantity for the following matrix:"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"M = matrix(ZZ, [[5, 6, 5, 2, 5, 2],\n",
" [6, 7, 4, 2, 4, 7],\n",
" [2, 8, 3, 2, 6, 4],\n",
" [8, 2, 9, 9, 1, 2],\n",
" [6, 3, 4, 9, 1, 1],\n",
" [2, 6, 9, 4, 2, 8]])"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Now, let us consider a finite subset of $\\mathbb{Z}^2$. The question is whether this region can be tiled by $2 \\times 1$ dominos (with rotation allowed). Show how this can be reduced to a matching in a bipartite graph and implement a function that given a binary matrix $M$ (ie a matrix with entries in $\\{0,1\\}$) returns a domino tiling of the subset $\\{(i,j): M_{ij} = 1\\}$ when it exists and `None` otherwise"
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
},
{
"source": [
"Adapt your function to work in $\\mathbb{Z}^d$."
],
"cell_type": "markdown",
"metadata": {}
},
{
"execution_count": null,
"cell_type": "code",
"source": [
"# edit here"
],
"outputs": [],
"metadata": {}
}
],
"metadata": {
"kernelspec": {
"display_name": "sagemath",
"name": "sagemath"
}
}
}