3-2-5 Graphs

Graph: a diagram consisting of circles, called vertices, joined by lines, called edges or arcs; each edge joins exactly two vertices.

Neighbours: two vertices are neighbours if they we connected by an edge.

Degree: of a vertex (singular of vertices) , the number of neighbours for that vertex.

E.g. Vertex A and vertex B are neighbours. Vertex A has degree 3 because it has three new ours: B, C, and D.


Labelled (weighted) Graph: a graph in which the edges are labelled or given a value called a weight.

Automation: turning an abstraction into a form that can be processed by computer.

Directed Graph (or digraph): diagram consisting of vertices joined by edges.
(e.g. A round-robin tournament [where every team plays every other team exactly
once])

Simple Graph: an undirected graph without multiple edges and in which each edge connects two different vertices.

Data Representation of a Graph:

An adjacency matrix and an adjacency list are two ways to represent a graph without multiple edges so that the graph can be processed by a computer.

Connectivity
Many applications of graphs involve getting from one vertex to another. For example, it may be required to find the shortest route between one place and another or a route out of a maze. Many problems like these can be modelled with paths formed by travelling along the edges of the graphs. A graph is connected if there is a path between each pair of vertices and is disconnected otherwise.

Path:
Informally, a path is a sequence of edges that begins at a vertex of a graph and travels form vertex to vertex along edges of a graph.

Explorer's Problem: the solution finds a route that traverses each road exactly once before returning to the starting point.
Traveller's Problem: the solution finds a route that visits each city once before retuning to the starting point.