Topics
Foundations of Graphs
0 of 0 exercises completed
Introduction to graphs: vertices, edges, degree and adjacency, and simple applications. Directed vs undirected graphs, connected and complete graphs.
Want a deeper conceptual understanding? Try our interactive lesson!
Terminology: Graph, vertices & edge
AHL AI 3.14
A graph is a type of diagram made up of vertices which are connected by edges.
An edge can connect any vertex to any vertex, including the same vertex. A self edge is an edge that connects a vertex to itself.
The graph to the right has vertices A,B,C and D, and edges between
A and A
A and B
A and C
B and C
B and D
C and D
Graphs are a powerful representation for understanding the connections or relationships between things.
Examples of things we can represent using graphs
Friendship graph
People are vertices, and edges represent friendships between people.
Bus connections between cities
Cities are vertices, and edges represent bus routes that connect them.
Adjacent vertices
AHL AI 3.14
When two vertices have an edge between them, we say that they are adjacent.
In the graph to the right, the vertices adjacent to D are C and B.
The vertices adjacent to C are all the other vertices: A,B and D.
The vertices adjacent to A are B,C and also A itself because it has a self edge (this sort of depends on convention, so the IB won't ask you this).
Adjacent edges
AHL AI 3.14
If two edges "connect" via a vertex, we say they are adjacent.
In the graph to the right, the edge AB is adjacent to the edges
DB (they share vertex B)
both edges CB (they share vertex B)
AC (they share vertex A)
AA (they share vertex A)
Degree of a vertex
AHL AI 3.14
The degree of a vertex is the total number of edges that connect to that vertex. To determine the degree of a vertex, count rhe
In the graph to the right, the vertex C has the incident edges:
CD
AC
CB twice
So the degree of C is 4.
Repeat edges are important, as when they exist the degree of a vertex is not the number of vertices it is connected to.
Self edges are tricky: In the graph above there is an edge between A, so that edge "connects" to A twice. It therefore counts 2 towards the degree of A, which is therefore 4 once we consider AC and AB.
Connected graphs
AHL AI 3.14
A graph is said to be connected if it is possible to get from any vertex to any other vertex by walking along the edges.
Connected
Not connected
Complete graphs
AHL AI 3.14
A graph where every vertex is connected by at least one edge to every other vertex is said to be complete.
Complete
Not complete - no edge BE
Weighted graphs
AHL AI 3.14
Weighted graph is one where each edge has a number which we call a weight. In applied settings, these represent important properties of the connection or relation between vertices.
The first graph below shows a weighted graph of bus connections between cities, where weighted graphs represent the driving distance, in kilometers, between the two cities.
The second graph shows a plumbing network between different junctions, with directed edges representing how water can move. Here the edge weights represent the volume of water that can move through the various pipes per second.
Directed Graphs
AHL AI 3.14
A directed graph is a special case where the edges have direction. These directions are represented by arrows on the graph.
In-degree and out-degree
AHL AI 3.14
For a directed graph, we can count the in-degree and out-degree. Both are similar to degree, but we only count edges pointing in for in-degree, and edges pointing out for out-degree.
On the graph to the right, the vertex C has
The edges D→C, A→C and B→C pointing in, so its in-degree is 3.
The edge C→B pointing out, so its out-degree is 1.
The vertex A has
the edge A→A pointing in, so an in-degree of 1.
the edges A→A,A→C and A→B pointing out, so an out-degree of 3.
Notice that self-edges count towards both the out-degree and in-degree, since they leave and enter the same vertex.
Strongly connected graphs
AHL AI 3.14
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from C to A.
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from D to A.
Simple Graphs
AHL AI 3.14
A simple graph is one where there are no
directed edges
self edges
repeated edges
Simple graph
Not simple graphs
Nice work completing Foundations of Graphs, here's a quick recap of what we covered:
Skills covered
Exercises checked off
I'm Plex, here to help you understand this concept!