Flow network

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. In operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. A network is a graph G =, where V is a set of vertices and E is a set of V’s edges – a subset of V × V – together with a non-negative function c: V × V → ℝ∞, called the capacity function. Without loss of generality, we may assume that if ∈ E is a member of E, since if ∉ E we may add to E and set c = 0.

If two nodes in G are distinguished, a source s and a sink t is called a flow network. There are various notions of a flow function. Flow functions model the net flow of units between pairs of nodes, are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The simplest example of a flow function is known as a pseudo-flow. A pseudo-flow is a function f: V × V → ℝ that satisfies the following two constraints for all nodes u and v: Skew symmetry: Only encode the net flow of units between a pair of nodes u and v, that is: f = −f. Capacity constraint: An arc's flow cannot exceed its capacity, that is: f ≤ c. Given a pseudo-flow f in a flow network, it is useful to consider the net flow entering a given node v, that is, the sum of the flows entering v; the excess function xf: V → ℝ is defined by xf = ∑v ∈ V f. A node u is said to be active if xf > 0, deficient if xf < 0 or conserving if xf = 0. These final definitions lead to two strengthenings of the definition of a pseudo-flow: A pre-flow is a pseudo-flow that, for all v ∈ V \, satisfies the additional constraint: Non-deficient flows: The net flow entering the node v is non-negative, except for the source, which "produces" flow.

That is: xf ≥ 0 for all v ∈ V \. A feasible flow, or just a flow, is a pseudo-flow that, for all v ∈ V \, satisfies the additional constraint: Flow conservation: The net flow entering the node v is 0, except for the source, which "produces" flow, the sink, which "consumes" flow; that is: xf = 0 for all v ∈ V \. The value of a feasible flow f, denoted | f |, is the net flow into the sink t of the flow network; that is, | f | = xf. In the context of flow analysis, there is only an interest in considering how units are transferred between nodes in a holistic sense. Put another way, it is not necessary to distinguish multiple arcs between a pair of nodes: Given any two nodes u and v, if there are two arcs from u to v with capacities 5 and 3 this is equivalent to considering only a single arc between u and v with capacity 8 — it is only useful to know that 8 units can be transferred from u to v, not how they can be transferred. Again, given two nodes u and v, if there is a flow of 5 units from u to v, another flow of 3 units from v to u, this is equivalent to a net flow of 2 units from u to v, or a net flow of −2 units from v to u — it is only useful to know that a net flow of 2 units will flow between u and v, the direction that they will flow, not how that net flow is achieved.

For this reason, the capacity function c: V × V → ℝ∞, which does not allow for multiple arcs starting and ending at the same nodes, is sufficient for flow analysis. It is enough to impose the skew symmetry constraint on flow functions to ensure that flow between two vertices is encoded by a single number, a sign — by knowing the flow between u and v you implicitly, via skew symmetry, know the flow between v and u; these simplifications of the model aren't always intuitive, but they are convenient when it comes time to analyze flows. The capacity constraint ensures that a flow on any one arc within the network cannot exceed the capacity of that arc; the residual capacity of an arc with respect to a pseudo-flow f, denoted cf, is the difference between the arc's capacity and its flow. That is, cf = c - f. From this we can construct a residual network, denoted Gf, which models the amount of available capacity on the set of arcs in G =. More formally, given a flow network G, the residual network Gf has the node set V, arc set Ef = and capacity function cf.

This concept is used in Ford -- Fulkerson algorithm. Note that there can be a path from u to v in the residual network though there is no path from u to v in the original network. Since flows in opposite directions cancel out, decreasing the flow from v to u is the same as increasing the flow from u to v. An augmenting path is a path in the residual network, where u1 = s, uk = t, cf > 0. A network is at maximum flow if and only. Sometimes, when modeling a network with more than one source, a supersource is introduced to the graph; this consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink

F. W. J. Palmer

Frederick William J. Palmer, CE, known professionally as F. W. J. Palmer, was an English civil engineer, structural engineer and surveyor. From 1891 he was Surveyor to Herne Bay Urban District Council; as Town Surveyor between at least 1891 and 1915 he was responsible for digging up a great deal of Herne Bay. He reconstructed all the main roads, rebuilt the council offices and Hampton Pier and constructed a new sea wall, he sewered the East Cliff and nine miles of private roads at the east end of Herne Bay. His crowning achievement was his design of both phases of Herne Bay, his extensive works helped to make the town what it is today. Archaeological artefacts turned up by his constant digging contributed to the collection now in Herne Bay Museum, he was articled to Alexander William Conquest, borough engineer and surveyor of Ramsgate and of Folkestone, and, the son of William Conquest, secretary to Joseph Bazalgette who created the London sewerage system. Palmer was appointed assistant borough engineer and surveyor of Folkestone, remaining in that position until 1886, when he became assistant surveyor of the Vestry of the Parish of Fulham.

In both positions he was working under A. W. Conquest. Subsequently, in 1891 he became the surveyor to Herne Bay Urban District Council, remained there until at least 1915, he became a member of the Institution of Civil Engineers on 25 April 1896. At Herne Bay between 1891 and 1915 he carried out numerous important engineering works; this involved excavating a large proportion of the town, this cannot have gone unnoticed by the inhabitants. However, by virtue of his duties as Surveyor to the Council, he contributed to a great extent in providing employment and in making the town what it is today. All this digging was appreciated by the acquisitive antiquarian, Dr Tom Bowes, who subsequently donated stone tools and artefacts, found by workmen and builders, to the collection, to become Herne Bay Museum and Gallery. Palmer was involved in the complete reconstruction of all the main roads before Kent County Council took them over, he oversaw the entire renovation of Herne Bay's Town Hall, including the erection of a new gallery, he directed the enlargement and construction of the Council Offices in Herne Bay High Street.

He was responsible for the 1903–1904 reconstruction of 350 feet of Hampton Pier "which sets as a protection against the inroads of sea along the whole front" of the town. Until at least the 1950s a local "concrete tomb" urban myth survived, suggesting that a construction worker had fallen into the poured concrete of Hampton Pier and was still there. During 1913 Palmer was responsible for the design and section-by-section construction of a new concrete sea wall, he designed the Tower Lavatories on the sea front. He prepared a scheme for laying out and scarping East Cliff, which cost £40,000, labour being supplied by the Central Unemployed Body For London, he "designed the scheme for sewering the whole of East Cliff including a 30-inch cast iron pipe sewer along the foot of the cliff and a 30-inch cast iron pipe up the face of the cliff." He "designed and supervised the construction of the sea defence works at the foot of the East Cliff, reaching from the old boathouse site to the eastern boundary of the district.

He "made up and sewered nearly nine miles of private streets, under the Private Street Works Act" on the West Cliff and East Cliff. This is a theatre, concert hall and dance hall, built as The Pavilion in 1903–1904 and developed as the King Edward VII Memorial Hall in 1913 in memory of the late king. Palmer designed both phases of the building. In 1903 to 1904 he planned and oversaw the building of the first phase of the Pavilion in his free time as a "labour of love." His plan consisted of a bandstand supported by a small building on a steep slope containing a tea room, rest rooms, a deckchair store and a small, covered auditorium to shelter 200 people and a band when it rained. There was no natural hollow ready and waiting. Palmer had to dig a hole:"6,000 cubic yards had to be removed, 12 inches by 12 inches pitch pine piles ranging from 10 feet to 20 feet long were driven at stated distances down into the clay, on the north and west sides of the site, connected together by means of 1 inch wrought iron tie rods passed through the piles, interlaced one with the other, connected together by means of 6 inches by 2.5 inches by 1 inch iron rings, through which the tie rods were passed, nuts placed in position, thus enabling the tie rods to be adjusted and tightened to a nicety.

The whole of the site was covered with a solid mass of Portland cement concrete 18 inches thick, which when finished left the ironwork embedded in the same. Upon this foundation the superstructure was erected." From a speech by F. W. J. Palmer at the opening of The Pavilion, 4 April 1904 The gracefulness of the building comes from the iron columns and ornamental ironwork manufactured to Palmer's design by MacFarlane & Co of Glasgow. In 1911 to 1913 he oversaw the building of the second phase of the King's Hall. For this, Palmer had to dig an bigger hole in October 1912: "many thousands of yards of London Clay" were removed to extend the building into the cliff; the 1904 phase remained as vestibule for the new Hall, dug into the cliff at its back, or south side. The Hall was intended to accommodate 1,500 people inside, plus an audience of 1,100 above, for the rooftop bandstand. So inside the Hall there we

44th Japan National University Championship

The 44th Japan National University Rugby Championship. Won by Waseda beating Keio 26 - 6. Kanto League A Waseda, Meiji University, Keio University, Teikyo University, University of TsukubaKanto League B Tokai University, Takushoku University, Hosei University, Daito University, Chuo UniversityKansai League Doshisha University, Kyoto Sangyo University, Osaka University of Health and Sport Sciences, Kwansei GakuinKyushu League Fukuoka Waseda Meiji University Keio University Teikyo University University of Tsukuba Tokai University Takushoku University Hosei University Daito University Chuo University Doshisha University Kyoto Sangyo University Osaka University of Health and Sport Sciences Ritsumeikan Kwansei Gakuin Fukuoka The 44th Japan University Rugby Championship - JRFU Official Page The 44th Japan University Rugby Championship Final - JRFU Official Page Rugby union in Japan