transportation network analysis lecture 5

connectivity, walks and paths

1. Connectivity, Walks, paths,
cycles
CE 529-Lecture 5

2. Learning Objectives
•Define and use basic network terminology:
•Tail and head node
•Incidence, Adjacency list
•Degree
•Walk
•Path
•Cycle

3. Physical Problem Requirements
•All size demands should be met
•Total cost of policy should be minimum
•Decision Variables: Which sizes should be
stored?

4. Policy
•E.g. say n = 4
•Policy 1: store all sizes: L1, … L4
•Policy 2: L2 and L4
•Policy 3: L1, L3, L4
•Optimal policy is one which has least cost of
both inventory as well as cutting

5. Network
•Sizes: 1, … N
•Nodes: 0, 1,… , N
•Arcs: connect every node i to node j if j > i.
•Arc (i,j) implies i and j are in inventory and in
between sizes are obtained from j.
•Any path from 0 to N is a policy on this network

6. Network parameters
•Cost (rij) = kj + Di+1 Ci+1,j + …. Dj Cjj
•B(0) = 1
•B(N) = -1
•Uij = infinity

7. Model Formulation
•Any path on the network is a feasible
inventory policy
•Cost of path is total cost of feasible policy
•Find shortest path from source 0 to sink N

8. The Bridges of Koenigsberg:
•Euler 1736
•"Graph Theory" began in 1736
•Leonard Eüler Visited Koenigsberg
•People wondered whether it is possible
to take a walk, end up where you
started from, and cross each bridge in
Koenigsberg exactly once

9. The Bridges of Koenigsberg:
Euler 1736
B
C
Is it possible to start in A, cross over each bridge exactly
once, and end up back in A?
1 2
A
D
5 6
3
4
7

10. The Bridges of Koenigsberg:
Euler 1736
B
C
Conceptualization: Land Masses are Nodes
1 2
A
D
5 6
3
4
7

11. Koenigsberg: Euler 1736
1 2
B
5
4
3
C
6
D
7
Is there a "walk" starting at A and ending at A and
passing through each arc exactly once? Eulerian Cycle!
Walksare paths that can repeat nodes and arcs
A

12. Koenigsberg: Euler 1736
1 2
B
5
4
3
C
6
D
7
Is there a "walk" starting at A and ending at A and
passing through each arc exactly once on this Network?
A
9
8

13. Thought Problem
•What are the conditions for an eulerian
tour to exist?
•What can we say about:
•Number of arcs at each node?
•Connectivity between nodes?

14. An Undirected Graph or
Undirected Network
NetworkG = (N, A)
A Directed Graph or
Directed Network
Node setN = {1, 2, 3, 4}
Arc SetA = {(1,2), (1,3), (3,2), (3,4), (2,4)}
In an undirected graph, (i,j) = (j,i)
Notation and Terminology
Network terminology as used in AMO.
1 2
3 4
1
3
2
4
b
c
d
a e a
b
c
d
e

15. Tail and Head Nodes
•Directed arcs –direction is important.
•i->j and i<-j are different arcs
•For i -> j, i is the tail node, and j is the
head node
i j
i j

16. Incidence and Adjacence
•Incoming and outgoing arcs to a node are
said to be incident to that node
•Outgoing arcs from a node are said to be
adjacent to that node

17. Arcs
•Incident nodes to i:
j1, j2, j3, j4
•Adjacent arcs to i
j3, j4
Node i is adjacent to
j1 and j2
Adjacency list (i): set of arcs that
are leaving node i
i
j2
j3
j1
j4

18. Indegree and Outdegree
•Indegree(i): No. of incoming arcs into i
•Outdegree(i): No. of outgoing arcs from I
•Outdegree(i) = | Adj list(i) |
•Degree(i) = Indegree(i) + Outdegree(i)
•Sum
i Indegree(i) = No. of arcs

19. Walks
•Sequence of nodes connected to each other
•[i1, i2, i3,… ir]
•Such that ik-> ik+1 is an arc or ik+1->ik is an arc
•Note directionality does not matter, only
connection does
•Repetition of nodes is allowed
•Directed walk: direction matters, but repetition is
allowed

20. Sub-graph
•Subset of Nodes and Arcs G’ = (N’, A’)
if N’ subset of N and A’ subset of A
Acyclic graph if graph contains no directed
cycle

21. Connectivity
•Nodes i and j are connected if there is at least one path
from I to j.
•A graph is connected if every pair of its nodes is
connected, otherwise it is disconnected
•Strong connectivity: if connected with directed paths
•Bipartite graph: If nodes partitionable into mutually
exclusive sets N1 and N2 such that every arc has tail
node in N1 and head node in N2 or vice-versa

22. Properties of trees
•Definition: Tree -connected graph with no cycle
•Tree of n nodes has exactly ____ arcs
•Node with degree 1 is called a leaf node
•A tree has at least ___ leaf nodes
•Any two nodes are connected by a unique path

23. Path:Example: 5, 2, 3, 4.
(or 5, c, 2, b, 3, e, 4)
•No node is repeated.
•Directions are ignored.
Directed Path. Example: 1, 2, 5, 3, 4
(or 1, a, 2, c, 5, d, 3, e, 4)
•No node is repeated.
•Directions are important.
Cycle (or circuit or loop)
1, 2, 3, 1. (or 1, a, 2, b, 3, e)
•A path with 2 or more nodes, except
that the first node is the last node.
•Directions are ignored.
Directed Cycle:(1, 2, 3, 4, 1) or
1, a, 2, b, 3, c, 4, d, 1
•Directions are important.
1
2 3
5
4
1
2 3
5
4
1
2
4
3
1
2
3
4
c
b e
d
a
a
b
e
c
d
a
b
c
d
a
b
c
d
e