Graphs and NetworksIntroduction

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:

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.

שנה שפה

היכנס אל מתיגון

שתף

אפס התקדמות

מילון מונחים

Graphs and NetworksIntroduction