Welcome guest
You're not logged in.
271 users online, thereof 0 logged in

Graph Theory

There are many real-life problems, which can be reduced to graph-theoretic problems. Some examples are:

  1. Find the ‘best’ route between two places connected by different streets in a city.
  2. Given a time table of flight connections for a world tour, find the shortest time to go around the world and come back to the same city.
  3. Having a portfolio of stock shares of \(n\) different companies, find a sub-portfolio which is as much diversified as possible.
  4. When designing a microchip, find a way to connect \(n\) different electronic components with \(m\) other electronic components in such a way that the conducting strips printed directly on to a flat board of insulating material do not cross.
  5. In a given country, how many ways accessible by a car (streets, highways) are there between two cities \(A\) and \(B\), such that one can visit both cities exactly once, without visiting any of the cities in-between more than once?
  6. What is the smallest number of colors needed to color any given map of countries in such a way that none of the two countries have the same color?

By means of the graph theory, such problems can be reduced to structures known as graphs, flows and networks, with the properties of which graph theory deals. Methods developed in graph theory to solve analogous problems for graphs, flows, and networks can be used to solve the above real-life problems.

| | | | created: 2014-02-20 21:26:18 | modified: 2019-09-01 14:29:11 | by: bookofproofs

1.Basics Concepts in Graph Theory

2.Definition: Trees and Forests

3.Paths, Cycles and Connectivity

4.Planar Graphs

5.Vertex Colourings and Decompositions

6.Transitive Hull and Irreducible Kernels

7.Graph Transformations

8.Graph Traversing

9.Shortest Paths



12.Network Design and Routing

13.Infinite Graphs

14.Extremal Problems in Graph Theory

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:


Bibliography (further reading)