## 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 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*

## 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

## 10.Flows

## 11.Matchings

## 12.Network Design and Routing

## 13.Infinite Graphs

## 14.Extremal Problems in Graph Theory

(none)

(none)

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.