0426notes.md · Indigo/Algorithm and Complexity

# 0426 Notes

[toc]

# Network Flow

## Introduction

### Background

![image-20200426111357521](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426111357521.png)

![image-20200426111440973](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426111440973.png)

### Concept

![image-20200426111731047](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426111731047.png)

![image-20200426111934379](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426111934379.png)

![image-20200426112025086](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426112025086.png)

![image-20200426112426374](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426112426374.png)

![image-20200426112600241](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426112600241.png)

![image-20200426112805791](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426112805791.png)

### Property

![image-20200426113122948](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113122948.png)

![image-20200426113248135](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113248135.png)

![image-20200426113423844](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113423844.png)

![image-20200426113455026](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113455026.png)

![image-20200426113644699](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113644699.png)

![image-20200426113656251](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113656251.png)

## Algorithm

### Idea

![image-20200426113830154](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113830154.png)

However, locally optimality $\ne$ global optimality.

![image-20200426113943630](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200426113943630.png)

![image-20200427100655455](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427100655455.png)

![image-20200427100739230](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427100739230.png)

![image-20200427101058152](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101058152.png)

![image-20200427101201115](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101201115.png)

### Ford-Fulkerson Algorithm

![image-20200427101500983](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101500983.png)

![image-20200427102041021](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102041021.png)

![image-20200427101624586](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101624586.png)

![image-20200427101802950](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101802950.png)

![image-20200427101900019](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101900019.png)

![image-20200427101943458](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427101943458.png)

![image-20200427102106352](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102106352.png)

![image-20200427102125412](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102125412.png)

![image-20200427102228396](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102228396.png)

![image-20200427102329676](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102329676.png)

![image-20200427102550061](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102550061.png)

![image-20200427102808031](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102808031.png)

![image-20200427102857013](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427102857013.png)

![image-20200427103307627](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427103307627.png)

![image-20200427103146570](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427103146570.png)

### Improvement Edmonds-Karp 1972

![image-20200427103609354](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427103609354.png)

![image-20200427103917082](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427103917082.png)

![image-20200427104111383](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104111383.png)

**Capacity Scaling**

![image-20200427104210450](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104210450.png)

![image-20200427104224684](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104224684.png)

![image-20200427104429406](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104429406.png)

![image-20200427104616043](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104616043.png)

![image-20200427104702005](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104702005.png)

![image-20200427104855070](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427104855070.png)

![image-20200427105004582](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427105004582.png)

![image-20200427105105431](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427105105431.png)

## Gephi Tutorial

![image-20200427112036383](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427112036383.png)

![image-20200427112107759](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427112107759.png)

![image-20200427112203303](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427112203303.png)

![image-20200427112435725](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427112435725.png)

![image-20200427113132505](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427113132505.png)

![image-20200427113514361](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427113514361.png)

![image-20200427113556420](https://gitee.com/sjtu_suyao/Algorithm-and-Complexity/raw/master/images/image-20200427113556420.png)

Indigo/Algorithm and Complexity

简介

发行版

贡献者

近期动态

Indigo/Algorithm and Complexity .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

Indigo/Algorithm and Complexity