Graphs and Planar Graphs Homework Help, Assignment Help, Online Tutor, Tutoring

Submit Assignment

* *

Payment Online Assignment Help

Trigonometry Homework

Homework Help

sfsf

Graphs and Planar Graphs

There are many real life problems that can be abstracted as problems concerning sets of discrete objects and binary relations on them. For example, consider a series of public-opinion polls conducted to determine the popularity of the presidential candidates. In each oll, voters’ opinions were sought on two of the candidates, and a favorite was determined. The results of the polls will be interpreted as follows: Candidate a is considered to be running ahead of candidate b if one of the following conditions is true:

1. Candidate a was ahead of candidate b in a poll conducted between them.

2. Candidate a was ahead of candidate c in a poll, and candidate c was ahead of candidate b in another poll.

3. Candidate a was ahead of candidate b in three separate polls, and so on.

Given two candidates, we might want to know whether one of them is running ahead of the other. Let S = {a, b, c, …} be the set of candidates and R be binary relation on S such that (a, b) is in R if a poll between a and b was conducted and a was chosen the favorite candidate. We recall that a binary relation on a set can be represented in tabular form, or in graphical form. Suppose that the binary relation and the result of the polls conducted. We observe that candidate a is more popular than candidate e because of the ordered pairs (a, b), (b, d), (d, e) in R. One probably would agree that the graphical representation of the binary relation R is quite useful in comparing the popularity of two candidates, since there must be “a sequence of arrows” leading from the point corresponding to the more popular candidate to that corresponding to the less popular one.

As another example, consider a number of cities connected by highways. Given a map of the highways, we might want to determine whether there is a highway route between two cities on the map. Also, consider all the board positions in a chess game. We might want to know whether a given board position can be reached from some other board position through a sequence of legal moves. It is clear that both of these examples are again concerned with discrete objects and binary relations on them. In the example of the highway map, let S = {a, b, c, ..} be the set of cities and R be a binary relation on S such that (a, b) is in R if there is a highway from city a to city b. In the chess game example, let S = {a, b, c, …} be the set of all board positions and R be a binary relation on S such that (a, b) is in R if board position a can be transformed into board position b in one legal move. Furthermore, in both of these cases as in the example on the popularity of the presidential candidates, we want to know whether, for given a and b in S, there exist c, d, e, …, h in S such that {(a, c), (c, d), (d, e), …, (h, b) ⊆ R.