Graphsv includes Graphs (Definition, Applications, Terminology, Properties, ADT); Data structures for graphs (Edge list structure, Adjacency list structure, Adjacency matrix structure). | Graphs SFO LAX Graphs ORD DFW 1 Outline and Reading Graphs (§) Definition Applications Terminology Properties ADT Data structures for graphs (§) Edge list structure Adjacency list structure Adjacency matrix structure Graphs 2 Graph A graph is a pair (V, E), where V is a set of nodes, called vertices E is a collection of pairs of vertices, called edges Vertices and edges are positions and store elements Example: A vertex represents an airport and stores the three-letter airport code An edge represents a flight route between two airports and stores the mileage of the route PVD ORD SFO LGA HNL LAX DFW Graphs MIA 3 Edge Types (u,v) Directed edge ordered pair of vertices (u,v) first vertex u is the origin second vertex v is the destination ., a flight Undirected edge unordered pair of vertices (u,v) ., a flight route Weighted edge Directed graph (Digraph) all the edges are directed ., route network u v flight ORD AA 1206 DFW 802 miles ORD flight DFW route 802 miles Undirected graph all the edges are undirected ., flight network Weighted graph all the edges are weighted Graphs 4 Applications cslab1a cslab1b Electronic circuits Printed circuit board Integrated circuit Transportation networks Highway network Flight network Computer networks Local area network Internet Web John Databases Paul David Entity-relationship .
