Algorithmic graph theory

点击翻译按钮获取中文摘要

A graph is a mathematical object consisting of a set of nodes together with a set of edges, each joining a pair of nodes. Graphs can be used to model many different types of networks, for example social networks where the nodes are people and the edges represent friendship; thus there is an edge between the nodes representing Jack and Jill if and only if Jack and Jill are friends. Graphs can also have directed edges, for example suppose the nodes are jobs that have to be run on a computer and a directed edge from J1 to J2 indicates that job J1 must be completed before job J2 can start. Clearly, if there is an edge from Ji to Jj and an edge from Jj to Jk, then there must be an edge from Ji to Jk. Given a graph for some application, one then wants to construct algorithms that solve specific problems on the graph. In the "friendship network", we may want to find a largest set of people who are mutually friends; in the second example we may want to find a fastest possible schedule that will assign each job to one of two computers such that if there is an edge from Ji to Jj, then both jobs must be on the same computer and Ji must be scheduled before Jj. When one is faced with designing such algorithms, the first task is to determine properties of the given graph and then to design algorithms that exploit these properties.