本文是一篇研究数学图文和概率的文章。图论-英文名Graph Theory是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有某种关系。作者将通过数学建模解决几个实际性问题。如果您有数学Mathematics Essay代写、Math Assignment代写需求，请联系我们的网站客服！hotessay为您提供高效有保障的学术论文以及作业代写服务。
Introduction
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
Graph Coloring
The assignment of labels or colors to the edges or vertices of a graph. The most common types of graph colorings are edge coloring and vertex coloring.
Two types:
- Vertex Coloring
- Edge Coloring
Vertex Coloring
A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize the number of colors for a given graph.
A vertex coloring of a graph with kor fewer colors is known as a k-coloring. The only one-colorable graphs are empty graphs, and two-colorable graphs are exactly bipartite graphs.
Edge Coloring
An edge coloring of a graph is a coloring of the edges of such that adjacent edges (or the edges bounding different regions) receive different color.
Chromatic Number
The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color i.e., the smallest value of possible to obtain a k-coloring.
A graph with chromatic number two is said to be bicolorable, and a graph with chromatic number three is said to be three-colorable. In general, a graph with chromatic number kis said to be an k-chromatic graph, and a graph with chromatic number is said to be k-colorable.
Edge Chromatic Number
The fewest number of colors necessary to color each graph edge of a graph so that no two graph edges incident on the same graph vertex have the same color. The edge chromatic number of a graph must be at leastDelta, the largest vertex degree of the graph.
Methods to find out chromatic number of graph:
- Coloring
By coloring the graph using vertex coloring an using minimum number of colors.
- Chromatic polynomial
Let's look at a complete graph on 3 points which looks like a triangle. We can color the first vertex in x ways, the second is x-1 ways and the third in x-2 ways. So the chromatic polynomial is
C(x) =x(x-1) (x-2) not the smallest natural number, N, such that C (N) is not equal to zero is the chromatic number. So in this case it is 3. This number tells us that we can color the graph with 3 different colors and have no adjacent vertices with the same color. Any smaller number of colors, say 2 would not work.
So the answer is finding C(x) the chromatic polynomial and then find the smallest natural number such that C(x) is not zero. There are many other methods to find it, but that one is sometimes the simplest.
Some Applications
There are several interesting practical problems that can be modeled by graph coloring.
- Scheduling
Assume that we have to schedule a set of interfering jobs, it has to be determined when each job is executed. Let be the conflict graph of the jobs: the vertices of the graph corresponds to the jobs, two vertices are connected by an edge if the corresponding two jobs cannot be executed at the same time (for example, they use a shared resource or interfere in some other way). The colors correspond to the available time slots; every job requires one time slot. There is a one-to-one correspondence between the feasible scheduling of the jobs and the colorings of the graph: vertex v receives color i if and only if the corresponding job is executed in time slot i. Clearly, the graph has a k-coloring if and only if the jobs can be done in k time slots such that interfering jobs are not executed simultaneously. Therefore the chromatic number of the graph equals the minimum makespan of the scheduling problem, the minimum time required to finish the jobs.
- Aircraft Scheduling
Assume that we have k aircrafts, and we have to assign them to n flights, where the i th flight is during the time interval (ai; bi). Clearly, if two flights overlap, then we cannot assign the same aircraft to both flights. The vertices of the conflict graph correspond to the flights, two vertices are connected if the corresponding time intervals overlap. Therefore the conflict graph is an interval graph, which can be colored optimally in polynomial time.
- Biprocessor tasks
Assume that we have a set of processors (machines) and a set of tasks, each task has to be executed on two preassigned processors simultaneously. A processor cannot work on two jobs at the same time. For example, such biprocessor tasks arise when we want to schedule file transfers between processors or in the case of mutual diagnostic testing of processors. Consider the graph whose vertices correspond to the processors, and if there is a task that has to be executed on processors i and j, then we add an edge between the two corresponding vertices. Now the scheduling problem can be modeled as an edge coloring of this graph: we have to assign colors to the edges in such a way that every color appears at most once at a vertex. Edge coloring is NP-hard , but there are good approximation algorithms. The maximum degree (d) of the graph is an obvious lower bound on the number of colors needed to color the edges of the graph. On the other hand, if there are no multiple edges in the graph (there are no two tasks that require the same two processors), then Vizing's Theorem gives an efficient method for obtaining a (d + 1)-edge coloring. If multiple edges are allowed, then the algorithm of gives an 1:1-approximate solution.
- Frequency assignment
Assume that we have a number of radio stations, identified by x- and y- coordinates in the plane. We have to assign a frequency to each station, but due to interferences, stations that are "close" to each other have to receive different frequencies. Such problems arise in frequency assignment of base stations in cellular phone networks. At first sight, one might think that the conflict graph is planar in this problem, and the Four Color Theorem can be used, but it is not true: if there are lots of stations in small region, then they are all close to each other, therefore they form a large clique in the conflict graph. Instead, the conflict graph is a unit disk graph, where each vertex corresponds to a disk in the plane with unit diameter, and two vertices are connected if and only if the corresponding disks intersect. A 3-approximation algorithm for coloring unit disk graphs is given in, yielding a 3-approximation for the frequency assignment problem.
- Register Allocation
One very active application for graph coloring is register allocation. The register allocation problem is to assign variables to a limited number of hardware registers during program execution. Variables in registers can be accessed much quicker than those not in registers. Typically, however, there are far more variables than registers so it is necessary to assign multiple variables to registers. Variables conflict with each other if one is used both before and after the other within a short period of time (for instance, within a subroutine). The goal is to assign variables that do not conflict so as to minimize the use of non-register memory.
A simple approach to this is to create a graph where the nodes represent variables and an edge represents conflict between its nodes. A coloring is then a conflict-free assignment. If the number of colors used is less than the number of registers then a conflict-free register assignment is possible.
In Computer Science, compilers - computer programs which translate one formal language to another - can employ vertex coloring to determine a satisfactory solution to the problem of register allocation. Vertex coloring is the most popular approach, and is one of the most effective.
Typically, a compiler will translate a source written in a high-level language (HLL) to a target in assembly language or machine code. There are a few critical differences between the source and target languages. In particular, HLLs allow for a large or unlimited number of variables, while the typical microprocessor only allows for efficient access to a small number of variables, called registers, and inefficient access to main memory. Since only a small percentage of the variables within a computer program are used at one time, there is an opportunity to place multiple variables into the same register - but only if those variables are not used at the same time.
The register allocation problem can be viewed as a vertex coloring problem as follows: every variable in a program is treated as a vertex in an undirected graph. Then, if at any point during program execution two variables each hold some value that will later be read, then those two variables are said to interfere, and an edge is drawn between them. Unfortunately, it is not always possible to determine if two variables interfere (a consequence of the halting problem), and thus a compiler must act conservatively and assume that they do interfere unless they can be shown not to. This graph is called the interference graph.
As was mentioned earlier, determining a-coloring for a graph is NP-Hard. Nonetheless, the compiler must solve such a problem. Thus, a compiler uses a heuristic algorithm to produce a non-optimal solution to the vertex coloring problem, attempting to minimize the number of colors used. If, ultimately, the number of colors used is greater than the number of registers in the target language, then the graph must be transformed to reduce the number of necessary colors. A compiler accomplishes this by spilling one or more variables, storing them in a memory location instead of a register.
- Pattern Matching
An interesting application involving pattern recognition. Given a "target" picture and an input picture (which involve only a set of points), a related compatibility graph is created whose vertices correspond to pairs of points. There is an edge between two vertices if the corresponding pairs are "mutually consistent" (where this can depend on a variety of restrictions, including angular relationships as well as the requirement that no point be matched with more than one other). A large clique represents a large number of mutually consistent pairs, and its size can be used as a measure of the corresponding fit. This model seems to correctly recognize affine transformations as well as moderately nonlinear transformations.
BIBLIOGRAPHY
- http://pubs.acs.org/doi/abs/10.1021/ci025546e
- http://www.slideshare.net/JuanManuelGutierrez/graph-coloring-for-enforcing-password-identification
- http://www.springerlink.com/content/qaaantfkp5n3926a/XXX
- http://www.math.lsa.umich.edu/mmss/coursesONLINE/graph/graph6/index.html
- http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
