Branch: Graph Theory
There are many real-life problems, which can be reduced to graph-theoretic problems. Some examples are:
- Find the 'best' route between two places connected by different streets in a city.
- 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.
- Having a portfolio of stock shares of \(n\) different companies, find a sub-portfolio which is as much diversified as possible.
- 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.
- 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?
- 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.
Table of Contents
- Part: Basics Concepts in Graph Theory
- Part: Paths, Cycles and Connectivity
- Definition: Trees and Forests
- Part: Planar Graphs
- Part: Vertex Colorings and Decompositions
- Part: Transitive Hull and Irreducible Kernels
- Part: Graph Transformations
- Part: Flows
- Part: Matchings
- Part: Network Design and Routing
- Part: Infinite Graphs
- Part: Extremal Problems in Graph Theory
- Part: Solving Strategies and Sample Solutions to Problems in Graph Theory
Mentioned in:
Motivations: 1
Parts: 2 3
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
