Graphs as vertex-edge networks: terminology for vertices, edges and self-edges; adjacent vertices and edges; degree of a vertex; simple, complete and connected graphs; directed graphs with in-degree and out-degree; strongly connected graphs; and weighted graphs.
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.
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.
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).
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ā)
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.
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
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 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.
A directed graph is a special case where the edges have direction. These directions are represented by arrows on the graph.
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.
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.
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:
Exercises checked off