Welcome guest
You're not logged in.
205 users online, thereof 1 logged in

68Graph 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 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.

| | | | Contributors: bookofproofs

801.Basics Concepts in Graph Theory

962.Definition: Trees and Forests

1593.Paths, Cycles and Connectivity

1784.Planar Graphs

2265.Vertex Colourings and Decompositions

2386.Transitive Hull and Irreducible Kernels

3287.Graph Transformations

3638.Graph Traversing

3929.Shortest Paths

42510.Flows

44611.Matchings

46312.Network Design and Routing

47013.Infinite Graphs

48014.Extremal Problems in Graph Theory


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

This work is a derivative of:

(none)

Bibliography (further reading)

(none)
FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.