QUESTION 13

What is a graph?

2 marks

Answer

A graph G = (V, E) consists of vertices and edges describing relationships. Edges may be directed or undirected according to the model.

Define graphs and explain common graph types.

5 marks

Answer in brief

Graphs represent general connections rather than a single rooted hierarchy.

Types

An undirected edge connects both endpoints without direction.
A directed edge has a source and destination.
A weighted graph assigns an edge value such as cost or distance.
A simple graph excludes parallel edges and loops under the usual convention.
A connected undirected graph has a path between every pair; a directed graph needs more precise reachability terminology.

Terminology

Adjacent vertices share a suitable edge. A path follows successive edges. A cycle returns to its starting vertex through the stated path convention. In an undirected graph, degree counts incident edges with loops treated by the chosen convention. A directed graph separates in-degree and out-degree.

Example

Cities can be vertices and flights directed edges. A flight from city 2 to city 3 does not imply a return flight unless a separate edge is supplied. If time or price matters, store it as a weight with a defined meaning.

Tree relationship

A finite connected undirected acyclic graph is a tree. A graph in general can contain cycles and disconnected components. Traversal therefore needs a visited record; merely following neighbours without one can revisit vertices indefinitely.

Storage and operations

The representation controls adjacency tests and neighbour enumeration. An adjacency matrix uses O(V²) space, while adjacency lists use O(V + E) space for the usual representation. The ADT should specify edge direction, duplicate-edge and weight rules.