Graphs

Overview

Recall questions on vertices and edges, weighted, directed and undirected graphs, and the trade-off between an adjacency matrix and an adjacency list.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a graph, and why is it used as a data structure?

   Model answer

   A graph is a set of vertices (also called nodes) connected by edges (also called arcs). It is used to represent relationships that are more complex than the simple linear or hierarchical orders that lists and trees can express, because any vertex may be connected to any number of others, and connections may run in either or both directions.

2. 2

   Define a vertex and an edge.

   Model answer

   A vertex, or node, is one of the objects in the graph — the things being connected, such as a town or a web page. An edge, or arc, is a connection between two vertices, representing a relationship between them, such as a road or a hyperlink.

3. 3

   What is a weighted graph?

   Model answer

   A graph in which every edge carries a value, called its weight, representing a cost associated with using that connection — for example a distance, a travelling time, a price or a bandwidth. Algorithms that find the cheapest route work on the total of the weights along a path rather than on the number of edges.

4. 4

   Explain the difference between an undirected graph and a directed graph.

   Model answer

   In an undirected graph an edge has no direction: an edge between A and B can be traversed from A to B and from B to A equally, so the relationship is symmetric. In a directed graph (a digraph) each edge has a direction and can only be traversed that way, so an edge from A to B does not imply one from B to A. A two-way road is an undirected edge; a one-way street is a directed one.

5. 5

   Give six typical uses of graphs.

   Model answer

   Road and rail networks, where vertices are places and weighted edges are the routes between them, used for journey planning. Computer networks, where vertices are devices and edges are the links, used for routing packets. Social networks, where vertices are people and edges are friendships. The World Wide Web, where vertices are pages and directed edges are hyperlinks. Also state transition diagrams and the dependency graphs used to schedule tasks.

6. 6

   Would you model a friendship network on a social media site as directed or undirected, and why?

   Model answer

   It depends on whether the relationship is mutual. A site where both people must agree to a friendship is best modelled by an undirected graph, because the relationship is symmetric. A site where one person can follow another without being followed back is best modelled by a directed graph, because the edge from follower to followed does not imply an edge the other way.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.