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

- Choose an action for
- Edit or Add
- Move Up
- Move Down
- Discussion
- Notation
- Versions
- Axiomatic Method

(none)

(none)

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.