Graphs

What is a graph? A graph is a set of vertices (or nodes) joined by edges. Graphs are used as a simple way of thinking about more complex real-world systems such as road networks. By simplifying down to mathematical concepts we can find general solutions to all sorts of problems!

Watch the video and then answer the questions below.

Ten-minute video

You can also view this video on YouTube

Key Points

  1. A graph (G) includes a set of vertices (V) and a set of edges (E)
  2. We can represent all sorts of things as graphs: game levels, road networks, social networks, computer networks…
  3. A graph is connected if there is a path from every point to every other point
  4. A graph is cyclic if there are some paths that get you back where you started
  5. The degree of a node is the number of edges coming from that node.
  6. The maximum degree (Δ(G)) of a graph G is the highest degree of any node in the graph
  7. The minimum degree (δ(G)) of a graph G is the smallest degree of any node in the graph
  8. A loop is an edge that joins a node to itself

Graphs in Java

There is no inbuilt implementation of a graph in Java. There is too much variation in how you might want to use a graph for that to be useful. So you need to make your own to suit your specific purposes.

Adjacency Matrixes

An Adjacency matrix is a way of representing the number of connections between different nodes. For example, the adjacency matrix for the folowing graph is given below:

  n1 n2 n3 n4
n1   1 1  
n2 1   1  
n3 1 1    
n4        

Questions

1. Check your knowledge

1. Graph 1

Look at the graph and answer the questions below. You can manipulate the graph by dragging the nodes.

Check Answers

2. Graph 2

Look at the graph and answer the questions below

Check Answers

3. Degree

Let G be a graph, with vertexes of degree 2,3,2,0,1,2. Is G a connected graph?

Check Answers

4. Adjacency Matrix

Look at the following adjacency matrix for a graph.

  n1 n2 n3 n4
n1     1  
n2     1 1
n3 1 1    
n4   1    

Check Answers

Summary

In this section we have learned about graphs. In the next section we will discover what happens when you make edges only one-way. You get a directed graph.