TW 45 BOS ORD JFK SFO AA 1387 AA 49 (DFW LAX AA 523 MIA AA 411 Figure 13.2: Exam

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)

Explanation / Answer

A) In degree and Out degree of every vertex

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

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.