http:^^www.cs.cornell.edu^info^courses^fall-96^cs681^h3.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 65 行
HTML
65 行
MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 24-Nov-96 22:41:36 GMT
Content-Type: text/html
Content-Length: 1645
Last-Modified: Friday, 27-Sep-96 00:34:17 GMT
<html><head><title>CS 681: Homework 3</title><link rev="made" href="mailto:ronitt@cs.cornell.edu"></head><body BGCOLOR="#ffffff"><h1> CS681 Homework 3</h1> September 20, 1996 <p><ol><li> Consider the following problem:A town has r residents R<sub>1</sub>,...,R<sub>r</sub>; q clubs C<sub>1</sub>,...,C<sub>q</sub>;and p political parties P<sub>1</sub>,...,P<sub>p</sub>.Each resident is a member of at least one club and belong to exactlyone political party. Each club must nominateone of its members to represent it on the town's governing council so that thenumber of council members belongingto the political party P<sub>k</sub> is at most u<sub>k</sub> (for given u<sub>1</sub>,...,u<sub>p</sub>). It is not ok for two or more clubs to nominate the same person.The problem is to determine whether it is possible tofind a council that satisfies this "balancing" property.<p>Given r, R<sub>1</sub>,...R<sub>r</sub>,q,C<sub>1</sub>,...C<sub>q</sub>,p,P<sub>1</sub>,...,P<sub>p</sub>,u<sub>1</sub>,...u<sub>p</sub>,show how to solve this problem by solving a single max flow problem.<p><li> You are given a graph and a max flow on the graph. Show how tofind a minimum cut in O(m) additional time.<p><li>Show how to transform a maximum flow problem havingseveral source nodes and several sink nodes to one with only one source node and one sink node.<p><li>Construct an easy to describe family of flow graphs (the i<sup>th</sup> flow graph is a graphon i nodes) with the number of cuts of minimum capacity growing exponentially with i.<p></ol><p>Due September 27 in class.</body></html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?