Network Optimization

V. Balakrishnan

• Publisher: CRC Press
• Year: 2019
• Print ISBN: 9780412556708
• eBook ISBN: 9781000723083
• Edition: 1
• Topic: Mathematics
• Subtopic: Applied Mathematics
• Index: Mathematics

Problems in network optimization arise in all areas of technology and industrial management. The topic of network flows has applications in diverse fields such as chemistry, engineering, management science, scheduling and transportation, to name a few. Network Optimization introduces the subject to undergraduate and graduate students in computer science, mathematics and operations research. The focus is mainly on developing the mathematical underpinnings of the techniques that make it possible to solve the several optimization problems covered in the text. The text discusses such topics as optimal branching problems, transshipment problems, shortest path problems, minimum cost flow problems, maximum flow problems, matching in bipartite and nonbipartite graphs and many applications to combinatorics. Also included is a large number of exercises.

1

Trees, arborescences and branchings

1.1 SOME GRAPH THEORY CONCEPTS

Graphs and digraphs

A graph G = (V, E) consists of a finite nonempty set V and a collection E of unordered pairs from V (i.e. two-element subsets of V). Every element in V is called a vertex of the graph, and each unordered pair in E is called an edge of the graph. The edge e = {x, y} is an edge between the two vertices x and y which is incident to both x and y. Two vertices are adjacent to each other if there is an edge between them: the edge in that case is said to join the two vertices. Two or more edges that join the same pair of vertices are called parallel edges. A graph without any parallel edges is a simple graph, in which case the collection E is a set. Otherwise G is multigraph. A graph G′ is a subgraph of the graph G if every vertex of G′ is a vertex of G and every edge of G′ is an edge of G.

A directed graph or digraph consists of a finite set V of vertices and a collection A of ordered pairs from V called the arcs of the digraph. The digraph is a simple digraph if A is a set. If a = (x, y) is an arc, then a is an arc from the vertex x to the vertex y and is incident (adjacent) from x and incident (adjacent) to y. Two vertices are nonadjacent if there is no arc from one to the other. The underlying graph G of a digraph D is the graph G obtained from D by replacing each arc (x, y) by an edge {x, y}.

In this book, unless otherwise mentioned, all graphs are simple graphs and all digraphs are simple digraphs.

If we associate one or more real numbers with each edge (or arc) of a graph (or a digraph), the resulting structure is known as a weighted graph or a network.

Connectivity

A path between vertex x₁ and vertex x_r in a graph is a sequence x₁, e₁, x₂, e₂, x₃, e₃,…, e_{r − 1}, x_r where x₁, x₂, x₃,… are vertices and e_k is the edge between x_{k− 1} and x_k for k = 1,2,…, r. This path is represented as 〈 x₁, x₂, x₃, …,x_r〉 or as x₁—x₂—x₃ —⋯—x_r without mentioning the edges explicitly. If x₁ = x_r it is a closed path. It is a simple path between x₁ and x_r if x₁, x₂,…, x_r are distinct. A circuit in a graph is a closed path in which the edges are all distinct. A cycle is a circuit in which the vertices are all distinct. Obviously every cycle is a circuit. A cycle with k vertices (k ⩾ 3) has k edges and is called an even cycle if k is even. Otherwise it is an odd cycle.

Two vertices x and y in a graph are connected to each other if there is a path between them. A graph is a connected graph if there is a path between every pair of vertices in it. Otherwise it is a disconnected graph. A connected subgraph H of the graph G is called a component of G if there is no connected subgraph H′ (other than H) such that H is a subgraph of H′.

If G = (V, E) and E = E′∪ {e}, then G′ = (V, E′) is the subgraph of G obtained from G by deleting the edge e from G. An edge e in a connected graph G is a bridge if its deletion from G yields a disconnected subgraph.

A directed path from a vertex x₁ to a vertex x_r in a digraph is a sequence x₁, a₁, x₂, a₂,…, a_{r − 1}, x_r in which the x_i are vertices and a_i is the arc from x_i to x_{i + 1}, where i = 1,2,…,r − 1. This path may be represented as x₁→x₂→ …→x_r. This is a closed directed path if x₁ = x_r. A simple directed path from x to y is a directed path in which all the vertices are distinct. A directed circuit is a closed directed path with distinct arcs, and a directed cycle is a closed directed path with distinct vertices. Two vertices x and y in a digraph form a strongly connected pair if there is a directed path from x to y and a directed path from y to x. A digraph is a strongly connected digraph if every pair of vertices in the digraph is a strongly connected pair. A digraph is weakly connected if its underlying graph (multigraph) is connected.

A simple path in a graph is called a Hamiltonian path if it passes through every vertex of the graph. A closed Hamiltonian path is a Hamiltonian cycle. An Eulerian circuit in a graph is a circuit which contains every edge of the graph. The definitions in the case of digraphs are analogous.

Bipartite graphs and complete graphs

If the set V of vertices of a graph G = (V, E) is partitioned into two subsets X and Y such that every edge in E is between some vertex in X and some vertex in Y, then the graph is called a bipartite graph and is denoted by G = (X, Y, E).

Theorem 1.1

...

Table of contents

• Cover
• Title Page
• Dedication Page
• Copyright Page
• Table of Contents
• Preface
• 1. Trees, arborescences and branchings
• 2. Transshipment problems
• 3. Shortest path problems
• 4. Minimum cost flow problems
• 5. Matchings in graphs
• Further reading
• References
• Solutions to selected problems
• Index