- A graph is simply a set of points called vertices (or nodes) connected by lines called edges (or arcs)
- Graphing theory is very important in mathematics and computing because it allows us to represent a number of concepts in a clear way
- Through abstraction, we can use graphs to model all sorts of different relationships. For example, there is a graph showing the Internet:
- Each page is a vertex
- Each hypertext link is an edge
Key Terms
- Graph
- A graph is an abstraction used to model a system that contains discrete, interconnected elements. The elements are represented by Vertices (also called nodes) and the interconnections are represented by edges (or arcs)
- Abstraction
- A process of removing unnecessary detail to leave only the elements necessary for creating a solution.
- Neighbour
- Two vertices connected by an edge
- Degree of a vertex
- The number of neighbours connected to a certain vertex
Types of Graph
Labelled graph (aka weighted graph)
- A labelled graph is one where its edges are given a label.
Directed graph (or digraph)
- A standard graph, but where each edge has a direction
- These directions, depending on the graph, can be used to convey additional information (such as one-way travel, sender/receiver, etc.)
- The opposite of a directed graph, is an undirected graph.
Multigraph
- A multigraph is a graph is allowed to have multiple edges between the same nodes
- They can be directed or undirected
- An example of a directed multigraph could be an airlines flight plan
Cycles & Closed Paths
-
A cycle is a circuit in which no vertex except the first (which is also the last) appears more than once
-
A closed path is where any two successive edges share a vertex I.E. You can go from one to the other without a dead end
