WG 2008: 34th International Workshop on Graph-Theoretic Concepts in Computer Science

一年一度的计算机科学图论概念国际研讨会，在社区内被称为WG，有着悠久的传统，聚集了来自(理论)计算机科学和离散数学的研究人员，他们致力于图论概念及其在计算机科学中的使用。本文中的图形是抽象的数学结构，用于模拟来自某个集合的对象之间的成对关系。图表示连接某些顶点对的顶点集合和边集合。图可以是无向的，这意味着顶点对之间的关系是对称的，或者它的边可以从一个顶点指向另一个顶点；在通常认为的图的类型中还有许多其他的变化。例如，可以通过为图的每条(有向)边赋权来扩展图结构。带权图或加权图用于表示结构，在这些结构中，成对连接具有一些可以通过数值获取的属性。例如，如果图表示计算机网络，则边的权重可以表示相应链路的容量。事实上，在图论的背景下，带权边的有向图也通常被称为网络。由于图的顶点表示的对象可以来自任何看似合理的集合，所以可以表示为图的结构是无处不在的，因此许多实际感兴趣的问题可以并且已经被建模为图问题。可以在图上定义的概念的数量也非常大，并且许多这样的概念产生深层次的问题或著名的猜想(例如臭名昭著的四色问题)。事实上，这些概念或理论问题中的许多都来自于实际问题(而不仅仅是数学家的想象力)，以及解决以图形为模型的现实生活问题的冲动。此外，由于这些模型通常涉及非常大的图，并且不能手工求解，算法图论的研究人员试图(如果可能的话)找到解决这些问题的有效算法。在计算机科学中，最明显的图论模型是计算机网络模型，其中顶点表示计算机，边(或有向边)表示计算机对之间的双向(或单向)链接。该模型及其变体导致了许多图论概念和图算法的发展和应用，例如用于路由、爬行、聚类等，但也用于脆弱性的结构度量或其他性能度量。最近的应用可以在传感器网络、自组织网络和动态网络的丰富和流行的领域中找到，其中物理链路以及无线(通常是临时的)连接可以被建模为边，从而产生随时间不断变化的图形。图论概念在计算机科学中的另一个应用是与互联网有关的，其中网站的结构可以用有向图来表示：顶点是在互联网上可用的网页，从页面A到页面B的有向边存在当且仅当A包含到B的超链接。因此，开发处理(大)图的算法是计算机科学的主要兴趣。研究Web图可以深入了解爬行、搜索或排序网页的算法。这是另一个有趣的例子，说明了日常生活中的一个非常实用的领域与图论中的一个中心问题之间的有趣联系。在谱图理论中，研究人员试图理解、估计和寻找图的特征向量和特征值。对图上随机游动的研究是谱图理论最早的应用之一。我们几乎所有人都在日常生活中使用的一个较新的应用程序是Google的页面排名算法，该算法基于Web图形上的随机行走。

The annual international workshops on Graph-Theoretic Concepts in Computer Science, known within the community as WG, have a long tradition of bringing together researchers from (theoretical) computer science and discrete mathematics who are working on graph-theoretic concepts and their use in computer science.Graphs in this context are abstract mathematical structures used to model pairwise relations between objects from a certain collection. A graph represents a collection of vertices and a collection of edges that join certain pairs of vertices. A graphmay be undirected, meaning that the relations between pairs of vertices are symmetric, or its edges may be directed from one vertex to another; and there are many other variations in the types of graphs that are commonly considered. For instance, a graph structure can be extended by assigning a weight to each (directed) edge of thegraph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some properties that can be captured by numerical values. For example, if a graph represents a computer network the weight of an edge could represent the capacity of the corresponding link. In fact, a directed graph with weighted edges in the context of graph theory is also often called a network. Because the objects that are represented by the vertices of a graph can be from any plausible collection, structures that can be represented as graphs are ubiquitous, and therefore many problems of practical interest can be and have been modelled as graph problems.The number of concepts that can be defined on graphs is also very large, and many such concepts generate deep problems or famous conjectures (for instance the notorious Four Colour Problem). In fact, many of these concepts or theoretical questions arise from practical problems (and not just from the mathematicians' imagination) and from the urge to solve real-life problems modelled by graphs. Moreover, as these models often involve very large graphs and cannot be solved by hand, researchers in algorithmic graph theory try (if possible) to find efficient algorithms for solving these problems. Within computer science the most obvious graph-theoretic model is that of a computer network, in which vertices represent computers and edges (or directed edges) represent bidirectional (or unidirectional) links between pairs of computers. This model and itsvariants have led to the development and application of many graph-theoretic concepts and graph algorithms, e.g. for routing, crawling, clustering, etc., but also for structural measures of vulnerability or other performance measures. More recent applications can be found in the rich and popular areas of sensor networks, ad-hoc networks and dynamic networks, where physical links as well as wireless (and often temporary) connections can be modelled as edges, yielding graphs that change constantly over time. Another application of graph-theoretic concepts within computer science is related to the internet, in which the structure of websites can be represented by a directed graph: the vertices are the web pages available at the internet and a directed edge from a page A to a page B exists if and only if A contains a hyperlink to B. The development of algorithms to handle (large) graphs is therefore of major interest in computer science. Studying web graphs gives insight into algorithms for crawling, searching or ranking web pages. Here is another example of an interesting connection between a very applied area from everyday life and a central issue in graph theory. In spectral graph theory researchers try to understand, estimate and find eigenvectors and eigenvalues of graphs. The study of random walks on graphs was one of the first applications of spectral graph theory. A more recent application which almost all of us use in our daily life is Google's page rank algorithm which is based on such random walks on the web graph.