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
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