A graph represents data of discrete objects and shows the relationship between them using dots (vertices) joined by lines (edges). (p.130)
A network is part of a graph whose vertices and edges have their own characteristics; its data structure has a many-to-many relation. (p.130)
Examples: land transport network (vertices = towns/cities; edges = roads/railways); social network (vertices = individuals/groups; edges = types of relationship). (p.130)
A graph is denoted G = (V, E): V = set of vertices {v1, v2, …}; E = set of edges {e1, e2, …} or vertex pairs {(a1, b1), …}. (p.131)
Degree d(v) of a vertex = number of edges connecting it to other vertices. (p.131)
Sum of degrees = twice the number of edges: Σd(v) = 2E, v ∈ V. (p.131)
A simple graph has no loops and no multiple edges. The edge for pair (1, 2) is also the edge for (2, 1) in an undirected graph. (p.131)
Multiple edges: two vertices connected by more than one edge. A loop: an edge that starts and ends at the same vertex; each loop adds 2 to the degree. (p.132)
Vertex pair for a loop is (a, a); vertex pairs for multiple edges are repeated, e.g. (a, b), (a, b). (p.133)
A graph can be drawn from a list of degrees only if the sum of degrees is even. (p.133)
5.1 Directed and Undirected Graphs
Directed graph: a direction is assigned to each edge; each edge has an initial vertex and a terminal vertex. (p.135)
Undirected graph: a simple graph or a graph with loops and multiple edges, drawn without any direction. (p.135)
Directed graphs represent flows such as road maps, airline networks, electrical circuits, computer networks and organisation charts. (p.135)
In a directed graph, din = edges going into a vertex, dout = edges coming out; d = din + dout. (p.136)
Undirected: vertex pair order does not matter ((A, B) = (B, A)). Directed: order follows the direction ((B, A) and (A, B) are different edges). (p.136)
Sum of degrees is 2E for both directed and undirected graphs. (p.136)
5.1 Weighted and Unweighted Graphs
Weighted graph: each edge has a value or weight (e.g. distance, travelling time, current, cost). (p.137)
Unweighted graph: edges have no value; they only show relationships (e.g. organisation chart, flow map, tree map). (p.137)
An isolated vertex appears in set V but not in set E (not connected to any other vertex). (p.137)
Both directed and undirected graphs can be weighted or unweighted. (p.137)
5.1 Subgraphs and Trees
A subgraph is part of a graph, or the whole graph redrawn. (p.139)
Graph H is a subgraph of G if V(H) ⊆ V(G), E(H) ⊆ E(G), and the vertex pairs of the edges of H are the same as those in G. (p.139)
A vertex, an edge with its vertices, and G itself are all subgraphs of G. (p.139)
A tree is a subgraph that is a simple graph (no loops or multiple edges), with all vertices connected and each pair of vertices connected by only one edge. (p.139)
For a tree: number of edges = number of vertices − 1 (n vertices, n − 1 edges). (p.139)
The term “tree” was introduced by Arthur Cayley in 1857. (p.139)
To get a tree from a graph, remove edges until edges = vertices − 1 with no cycles. (p.141)
Tree with minimum total weight: remove the edges with the greatest weights while keeping all vertices connected with n − 1 edges; add up the remaining weights. (p.141)
5.1 Networks and Problem Solving
Networks can be drawn as directed or undirected, weighted or unweighted graphs. (p.143)
Transport network weights may be distance, time or cost; the GPS is a navigation system based on weighted transportation networks. (p.143)
Social networks are used for jobs, business, socialising, family, education and connecting communities; use them with caution and moderation. (p.144)
For a social-network graph, choose the information that is not repeated as the edges. (p.144)
Problem solving: compare options (time, cost, number of people) in a table or weighted graph, then justify the best choice. (p.146)