Round 7: Graphs, part I

Different kinds of graphs and networks appear everywhere:

  • ​ the processor of a computer is a network of logic gates

  • ​ the internet is a network of computers

  • ​ social networks are formed of people and different relations, such as friendship, between them

  • ​ maps

  • ​ dependency graphs (course prerequisites etc)

  • ​ etc and etc

As an example, a part of the internet in 2005 is shown below (figure: Matt Britt, Creative Commons license, source).

_images/Internet_map_1024_-_transparent.png

The network of European E roads (figure: public domain, source).

_images/International_E_Road_Network.png

In this round, we study some fundamental mathematical definitions for graphs and some elementary graph algorithms. Using the terms provided in the mathematical abstraction allows us to develop and use graph algorithms in many applications domains, irrespective of whether the vertices are cities or people and whether the edges are relations or roads.

Contents:

Material in Introduction to Algorithms (Aalto access):

  • ​ Sections 22.1–22.4

Some external links: