What is a graph?

What is a graph?
How can we lay a cable at minimum cost to make every telephone reachable from every
other?
What is the fastest route from the national capital to each state capital?
How can n jobs be filled by n people with maximum total utility?
What is the maximum flow per unit time from source to sink in a network of pipes?
How many layers does a computer chip need so that wires in the same layer don’t cross?
How can the season of a sports league be scheduled into the minimum number of
weeks?
In what order should a traveling salesman visit cities to minimize travel time?
Can we color the regions of every map using four colors so that neighboring regions
receive different colors?
These and many other practical problems involve graph theory.
1.1 Introduction
In recent years, graph theory has established itself as an important mathematical tool
in a wide variety of subjects.
The basic ideas of graph theory were introduced c.1736 by Euler, a Swiss
mathematician, in his solution of the now famous K ?onigsberg bridge problem. The city
of K ?onigsberg (now Kaliningrad) was divided into four sections by the Pregel River,
with seven bridges connecting the sections.
It is said that residents spent their Sunday afternoons trying to find a way to walk
around the city crossing each bridge exactly once and returning to where they started.
Euler was able to solve this problem by constructing a graph of the city and
investigating the features of this graph.
Chapter one Graph Theory Dr. Ahmed Abed Ali @ Dr. Manal Najy
Basic Definitions and Concepts University of Babylon - -University of Technology
2
Graph theory has many applications and has proven to be an extremely useful tool in
analyzing various practical problems. For instance, graphs can be used to represent
electrical or telecommunications networks, traffic systems, pipelines and flow charts.
Graph theory has also been found to be useful when working with biological
evolutionary trees, chemical compounds, organizational charts, computer data structures
etc.
Graph theory is major area of combinatorics, and during recent decades, graph theory
has developed into a major area of mathematics. In addition to its growing interested
and importance as a mathematics subject, it has applications to many fields, including
computer science and chemistry.
Many real-world situations can conveniently be described by means of a diagram
consisting of a set of points together with lines joining certain pairs of these points. For
example, the points could represent people, with lines joining pair of friends; or the
points might be communication centers, with lines representing communication links.
Notice that in such diagrams one is mainly interested in whether or not two given points
are joined by a line; the manner in which they are joined is immaterial. A mathematical
abstraction of situations of this type gives rise to the concept of a graph.