KONIGSBERG BRIDGE PROBLEM:
The Konigsberg bridge problem Is the perhaps the best known
example in graph theory. It was a long-standing problem until solved by Leonhard Euler(1907-1983) in 1736, by means
of a graph.
Two islands, C and D, formed by the Pergel River in Konigsberg
were connected to each other and to the banks A and B with seven bridges. The
problem was to start at any of the four land areas of the city A, B, C, or D,
walk over each of the seven bridges exactly ones, and return to the starting
point.
Euler represented this situation by means of a
graph. The vertices represent the land areas and the edges represent the
bridges. Euler proved that a solution for this problem does not exist.
The Kongsberg problem is the same as the problem of drawing figures
without lifting the pen from the paper and without retracing a line.
UTILITIES PROBLEM:
There are three houses H1, H2, H3, H4, each to be connected
to each of the three utilities- water(w), gas(G), and electricity(E) – by means
of conduits. Is it possible to make such a connections without any crossovers
of the conduits?
This problem can be represented by means of a graph- the
conduits are shown as edges while houses and utilities are shown as vertices. The
graph of the problem cannot be drawn in the plane without edge crossing over. Thus
the answer to this problem is no.
ELECTRICAL NETWORK PROBLEMS:
Properties of electrical network are functions of only two
factors:
1.
The nature and value of the elements forming the
network, such as resistors, inductors, transistors, and so forth.
2.
The way these elements are connected together,
that is, the topology of the network.
The topology of the network is studied by
means of its graph. In drawing a graph of an electrical network the junctions
are represented by vertices and branches are represented as edges, regardless
of the size and nature of the electrical elements.
SEATING PROBLEM:
Nine members of a new club meet each day for
lunch at around table. They decide to sit such that every member has different neighbor
at each lunch. How many days can this arrangement last?
This situation can be represented by a graph with nine vertices such that each
vertex represents a member, and an edge joining two vertices represents the
relationship of sitting next to each other.
Two possible seating arrangements- these are
1234567891(dark line), and 1352749681(thin line). It can be shown by
graph-theoretic considerations that there are only two more arrangements
possible. They are 1573928461 and 1795836241. In general it can be shown that
for N people the number of such possible arrangements is
N-1/2, if n is odd,
N-2/2,
if n is even.
No comments:
Post a Comment