L7 - Max Flow Problems Flashcards
What is a graph?
A graph consists of vertices [nodes] which are connected by edges [arcs].
What is a subgraph?
A sub graph is a part of a graph.
How is Weighted Graph defined?
A graph in which there is a number associated with each edge [its weight].
- also know as a network
How is Digraph/Directed edges defined?
A graph in which the edges have a direction associated with them – the edges are known as directed edges.
- a directed graph
How Degree of Valency/Order defined?
The number of edges incident to a vertex.
What is a Path?
A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once.
How is Cycle/Circuit defined?
A closed ‘path’ i.e. the end vertex of the last edge is the start vertex of the first edge.
How is Connected defined?
Two vertices are ‘connected’ if there is a path between them. A graph is connected if all its vertices are connected.
How is Loop defined?
An edge that starts and finishes at the same vertex.
How is Simple Graph defined?
A graph in which there are no loops and not more than one edge connecting any pair of vertices.
How is Tree defined?
A connected graph with no cycles.
How is Spanning Tree defined?
A subgraph of a graph which includes all the vertices of the graph and is also a tree.
How is Minimum Spanning Tree defined?
A spanning tree such that the total length of its arcs is as small as possible.
What is capacity utilisation of an arc?
is the ratio of the flow on the arc to its maximum capacity
