Verander de taal

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Log in bij Mathigon

of

Nieuw account     Wachtwoord opnieuw instellen     

Graphs and Networks
Introduction
The Bridges of Königsberg
Handshakes and Dating
Planar Graphs
Map Colouring
The Travelling Salesman Problem
Scheduling Problems
Graphs in Everyday Life

Delen

Voortgang resetten

Hierdoor worden je voortgang en chatgegevens voor alle hoofdstukken in deze cursus verwijderd en kan dit niet ongedaan worden gemaakt!

Woordenlijst

Selecteer een van de zoekwoorden aan de linkerkant ...

Graphs and NetworksIntroduction

Leestijd: ~10 min

Every day we are surrounded by countless connections and networks: roads and rail tracks, phone lines, the internet, electronic circuits and even molecular bonds. There are even social networks between friends and families. Can you think of any other examples?

Road and Rail Networks

Computer Chips

Supply Chains

Friendships

Neural Connections

The Internet

In mathematics, all these examples can be represented as graphs (not to be confused with the graph of a function). A graph consists of certain points called , some of which are connected by .

Graph theory is the study of graphs and their properties. It is one of the most exciting and visual areas of mathematics, and has countless important applications.

We can draw the layout of simple graphs using circles and lines. The position of the vertices and the length of the edges is irrelevant – we only care about how they are connected to each other. The edges can even cross each other, and don’t have to be straight.

In some graphs, the edges only go one way. These are called directed graphs.

Some graphs consist of multiple groups of vertices which are not connected with each other by edges. These graphs are disconnected.

Other graphs may contain multiple edges between the same pairs of vertices, or vertices which are connected to themselves (loops).

We can create new graphs from an existing graph by removing some of the vertices and edges. The result is called a subgraph. Here you can see a few more examples of graphs, with coloured edges and vertices indicating a possible subgraph:

We say that the order of a graph is the number of vertices it has. The degree of a vertex is the number of edges which meet at that vertex.

Order:

Order:

Degree:

Degree:

Graphs that consist of a single loop of vertices are called cycles. All cycles have .

Equipped with these new definitions, let’s explore some of the fascinating properties and applications of graphs.

Archie