Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; plgContentJComments has a deprecated constructor in /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php on line 25 Call Stack: 0.0001 361928 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.1006 1210560 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.1006 1210560 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.3399 4103552 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.3414 4131056 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.3423 4148768 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.3423 4165776 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.3431 4173512 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.3431 4173512 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.4351 4402720 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.4367 4420120 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.4373 4441048 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.4472 4506616 13. Joomla\CMS\Plugin\PluginHelper::importPlugin() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:189 0.4472 4506872 14. Joomla\CMS\Plugin\PluginHelper::import() /var/www/astarmathsandphysics/libraries/src/Plugin/PluginHelper.php:182

Flow Augmentation

An initial flow through a network can be found by inspection, and a maximum flow through the network can be found by flow augmentation once this initial flow has been found. We do this by labelling the arcs of a network with their corresponding flows and capacities as shown below.

Each arc is now labelled with an excess capacity, equal to capacity minus flow, and a back capacity, equal to the flow, as shown below.

We can find a flow augmenting path by looking at the capacities.

Along soqt we can increases the flow by 1, but no more since the excess capacity along so and qt are both 1.

Along soprt and sprt the flow cannot be increased at all, since pr has no excess capacity (it is saturated).

Along spoqt there are excess and back capacities of 1 and 4, so the flow can be increased by 1.

Proceeding in this manner, we see that the flow can be increased by 1, along soqt for example, to give the flow below.

We can cut the network as shown. There is no excess capacity across the cut, so the maximum flow is 1+3=4.

Add comment

Security code
Refresh