Getting Started

Welcome Who am I? Coding Assessment

Introducing Mathematics

Course Introduction Challenges

Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Directed Graphs

Sometimes connections in a graph are one-way: imagine roads in a one-way system. Such a graph is called a directed graph. We will learn about directed graphs and different ways of formalising graphs.

Watch the video and then answer the questions below.

Eight-minute video

You can also view this video on YouTube

Key Points

Graphs can be directed or undirected.
A directed graph has edges that only go one way. Edges in an undirected graph go both ways
Edges can be written as an ordered tuple <n1,n2>, where n1 is the source node, and n2 is the destination node.

In-degree and Out-degree

While in a directed graph the degree of a node is still how many edges connect to it, there are also two more related concepts:

In-degree - the number of edges that go to this node
Out-degree - the number of edges that go from this node

Adjacency matrices for directed graphs see the example below (in-edges along top, out-edges down the side):

	n2	n3	n4
n1	1	1
n2		1
n3
n4			1

Questions

1. Check your knowledge

1. Graph 1

Look at the graph and answer the questions below

Cyclic Acyclic

Connected Unconnected

Directed Undirected

What is the degree of node n3?
What is the maximum degree Δ(G) of the graph?
What is the minimum degree δ(G)of the graph?

Check Answers

2. Adjacency Matrix

Look at the following adjacency matrix for a directed graph: ‘to’ nodes are along the top, ‘from’ nodes are down the side.

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

What is the degree of node n2?
What is the degree of node n3?
A loop is where a vertex connects to itself. There is a loop in this graph. On which node?

Check Answers

Summary

In this section we have learned about directed graphs.

You should know what it means for a graph to be directed.
You should be able to recognise and create directed and undirected graphs

In the next section we are going to see an application of graphs to the study of language.

Improve this page