All Branches

Branch: Graph Theory

Introduction

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 micro chip, 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 then once?
6. What is the smallest number of colors needed to color any given map of countries in such a way that none of two countries have the same color?

By means of the graph theory, such problems can be reduces 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.

Subordinated Structure:

Contribute to BoP:

add a new Part  N

add a new Motivation  N

add a new Example  N

add a new Application  N

add a new Explanation  N

add a new Interpretation  N

add a new Axiom  N

add a new Definition  N

add a new Proposition  N

add a new Lemma  N

add a new Theorem  N

add a new Algorithm  N

add a new Open Problem  N

add a new Bibliography (Branch)  N

add a new Comment (Branch)  N