Question

TW 45 BOS ORD JFK SFO AA 1387 AA 49 (DFW LAX AA 523 MIA AA 411 Figure 13.2: Example of a directed graph representing a flight network. The end- points of edge UA 120 are LAX and ORD; hence, LAX and ORD are adjacent. The in-degree of DFW is 3, and the out-degree of DFW is 2. a. Give the indegree and outdegree of each vertex (5 points) b. Draw an edge-list representation for this graph (as discussed on pp. 600-602 of the text). (5 points) c. Draw an adjacency list representation (as discussed on pp. 603-604). Each edge should appear only on the list of its tail vertex. You don't need to show lists linking all the edges and vertices together - just the lists of edges associated with each vertex; and you don't need to show links from each edge back to the tail and head vertices. (I.e. just show the main idea - if you try to show all the details you'll end up with a bowl of spaghetti!). (5 points) d. Draw an adjacency matrix representation (as discussed on pp. 605-606). You can represent information about the edge (e.g. the flight number) in the matrix rather than using separate nodes. (5 points)

Answer 1

A) In degree and Out degree of every vertex

Node name	in degree	out degree
SFO	1	0
ORD	2	1
BOS	0	2
JFK	1	3
LAX	2	1
DFW	3	2
MIA	2	2

B)Edge list representation

[ [JFK,SFO], [JFK,DFW], [JFK,MIA], [ORD,DFW], [BOS,JFK], [BOS,MIA], [LAX,ORD],[DFW,LAX],[DFW,ORD],[MIA,DFW], [MIA,LAX] ]

C) Adjacency list Representation

SFO ---> NOTHING ADJACENT

ORD ---> DFW

BOS ---> JFK -> MIA

JFK ---> SFO -> DFW -> MIA

LAX ---> ORD

DFW ---> LAX -> ORD

MIA ---> DFW -> LAX

D) Adjacency Matric Representation

	SFO	ORD	BOS	JFK	LAX	DFW	MIA
SFO	0	0	0	0	0	0	0
ORD	0	0	0	0	0	1	0
BOS	0	0	0	1	0	0	1
JFK	1	0	0	0	0	1	1
LAX	0	1	0	0	0	0	0
DFW	0	1	0	0	1	0	0
MIA	0	0	0	0	1	1	0