数据结构：图：图形和图形模型（Graphs and Graph Models）

章节总结

• 图形和图形模型

• 图形术语和特殊类型的图形

• 表示图形和图形同构

• 连通性

• 欧拉和哈密顿图

• 最短路径问题

 

Chapter Summary

• Graphs and Graph Models

• Graph Terminology and Special Types of Graphs 

• Representing Graphs and Graph Isomorphism

• Connectivity

• Euler and Hamiltonian Graphs

• Shortest-Path Problems

 

图形和图形模型（Graphs and Graph Models）

 

部分摘要

• 图表简介

• 图形分类

• 图模型

 

Section Summary

• Introduction to Graphs 

• Graph Taxonomy

• Graph Models

 

图表

定义：图G =（V，E）由一组顶点（或节点）和一组边E组成。 每条边都有一个或两个与之关联的顶点，称为端点。 据说边缘连接其端点。

 

Graphs

Definition:AgrapG=(V,E)consistsof anonempty set V of vertices (or nodes) and a set E of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.

 

备注：

• 我们在这里研究的图表与第2章研究的函数图无关。

• 我们绘制图形图片时有很大的自由度。 重要的是边缘连接，而不是描绘的特定几何形状。 例如，边缘的长度，边缘是否交叉，顶点如何描绘等等都无关紧要。

• 具有无限顶点集的图形称为无限图形。 具有有限顶点集的图被称为有限图。 我们将注意力集中在有限图上。

 

Remarks:

• The graphs we study here are unrelated to graphs of

• functions studied in Chapter 2.

• We have a lot of freedom when we draw a picture of a graph. All that matters is the connections made by the edges, not the particular geometry depicted. For example, the lengths of edges, whether edges cross, how vertices are depicted, and so on, do not matter.

• A graph with an infinite vertex set is called an infinite graph. A graph with a finite vertex set is called a finite graph. We restrict our attention to finite graphs.

 

一些术语（Some Terminology）

• 在一个简单图（simple graph）中，每条边连接两个不同的顶点，没有两条边连接同一对顶点。

• 多图（Multigraphs）可以有多条边连接相同的两个顶点。 当m个不同的边连接顶点u和v时，我们说{u，v}是多重m的边。

 

• In a simple graph each edge connects two different vertices and no two edges connect the same pair of vertices.

• Multigraphs may have multiple edges connecting the same two vertices. When m different edges connect the vertices u and v, we say that {u,v} is an edge of multiplicity m.

 

• 将顶点连接到自身的边称为循环。

• 伪图可以包括循环，以及连接同一对顶点的多个边。 该伪图具有多个边缘和一个环。

 

• An edge that connects a vertex to itself is called a loop.

• A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. This pseudograph has both multiple edges and a loop.

 

• 备注：图论没有标准术语。 因此，每当您阅读有关图表的材料时，了解所使用的术语至关重要。

 

• Remark: There is no standard terminology for graph theory. So, it is crucial that you understand the terminology being used whenever you read material about graphs.

 

有向图

定义：有向图（或有向图）G =（V，E）由顶点（或节点）的非空集V和有向边（或弧）的集合E组成。 每条边与一对有序顶点相关联。 与有序对（u，v）相关联的有向边称为从u开始并在v结束。

备注：

• 边缘端点未排序的图表称为无向图。

 

Directed Graphs

Definition: An directed graph (or digraph) G = (V, E) consists of a nonempty set V of vertices(or nodes)and a set E of directed edges (or arcs). Each edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u,v) is said to start at u and end at v.

Remark:

• Graphs where the end points of an edge are not ordered are said to be undirected graphs.

 

• 简单的有向图没有循环也没有多边。

 

• A simple directed graph has no loops and no multiple edges.

 

有向多图可以具有多个有向边。 如果从顶点到顶点，那么它就是多边形的，那就是（u，v）。

 

A directed multigraph may have multiple directed edges. Whentherearemdirectededgesfromthe vertexutothevertexv, wesaythat (u,v)isanedgeof multiplicity m.

 

图模型：计算机网络（Graph Models: Computer Networks）

• 当我们构建图模型时，我们使用适当类型的图来表现应用的重要特性。

• 我们使用不同类型的计算机网络的图模型来说明这个过程。 在所有这些图模型中，顶点表示数据中心，边表示通信链接。

 

• When we build a graph model, we use the appropriate type of graph to capture the important features of the application.

• We illustrate this process using graph models of different types of computer networks. In all these graph models, the vertices represent data centers and the edges represent communication links.

 

• 为了模拟计算机网络，当我们只关心两个数据中心是否通过通信链路连接时，我们使用一个简单图。 当我们只关心两个数据中心是否直接链接（而不是可能有多少链接）并且所有通信链路都在两个方向上工作时，这是适当的图形类型。

 

• To model a computer network where we are only concerned whether two data centers are connected by a communications link, we use a simple graph. This is the appropriate type of graph when we only care whether two data centers are directly linked (and not how many links there may be) and all communications links work in both directions.

 

• 为了模拟当我们关心数据中心之间链接数量的计算机网络的情况，我们使用多图。

 

• To model a computer network where we care about the number of links between data centers, we use a multigraph.

 

• 为了在数据中心建立具有诊断链接的计算机网络，我们使用伪图，因为需要循环。

 

• To model a computer network with diagnostic links at data centers, we use a pseudograph, as loops are needed.

 

• 诊断链接：可能是用于诊断目的的反馈回路

 

• diagnostic links : perhaps a feedback loop for diagnostic purposes

 

 

• 为了使用多个单向链接建模网络，我们使用有向多图。 请注意，如果我们只关心是否存在从数据中心到另一个数据中心的至少一个链接，我们可以使用没有多个边的有向图。

 

• To model a net work with multiple one-waylinks,we use a directed multigraph. Note that we could use a directed graph without multiple edges if we only care whether there is at least one link from a data center to another data center.

 

图形术语：摘要（Graph Terminology: Summary）

• 要理解图形的结构并构建图形模型，我们会问这些问题：

 

• • 图的边缘是指向的还是指向的（或两者）？

  • 如果边缘是无向的，是否存在连接同一对顶点的多条边？ 如果边缘是直的，是否存在多个有向边？

  • 是否存在循环？

 

• To understand the structure of a graph and to build a graph model, we ask these questions:

 

• • Are the edges of the graph undirected or directed (or both)?

  • If the edges are undirected, are multiple edges present that connect the same pair of vertices? If the edges are directed, are multiple directed edges present?

  • Are loops present?

 

 

 

图的其他应用

• 图论可用于以下模型：

  • 社交网络

  • 通信网络

  • 信息网络

  • 软件设计

  • 运输网络

  • 生物网络

• 找到一个图形理论尚未应用的主题是一个挑战。 你能找到一个没有应用图论的区域吗？

 

Other Applications of Graphs

• Graph theory can be used in models of:  Social networks

  • Communications networks

  • Information networks

  • Software design

  • Transportation networks  Biological networks

• It’s a challenge to find a subject to which graph theory hasnotyetbeenapplied. Canyoufindanareawithout applications of graph theory?

 

图模型：社交网络（Graph Models: Social Networks）

• 图可用于根据人或群体之间不同类型的关系对社会结构进行建模。

• 在社交网络中，顶点表示个人或组织，边表示它们之间的关系。

 

• Graphs can be used to model social structures based on different kinds of relationships between people or groups.

• In a social network, vertices represent individuals or organizations and edges represent relationships between them.

 

• 有用的社交网络图模型包括：

• • 友谊图 - 如果他们是朋友（在现实世界中，在Facebook上，或在特定的虚拟世界中，两个人连接的无向图），在无方向的图中他们会被连接。

  • 影响图表 - 如果第一个人可以影响第二个人，那么从一个人到另一个人有边缘的有向图

  • 协作图 - 如果他们以特定方式协作，则两个人用无向图连接。

  • 协作图的示例：

  • 好莱坞图表模拟了电影中演员的合作。

    • 我们通过顶点表示演员，如果他们所代表的演员出现在同一部电影中，我们会连接两个顶点。

    • 凯文培根号码：第10.4节

 

• Useful graph models of social networks include:

• • friendship graphs - undirected graphs where two people are connected if they are friends (in the real world, on Facebook, or in a particular virtual world

  • influence graphs - directed graphs where there is an edge from one person to another if the first person can influence the second person

  • collaboration graphs - undirected graphs where two people are connected if they collaborate in a specific way.

  • Examples of collaboration graphs :

  • The Hollywood graph models the collaboration of actors in films.

    • We represent actors by vertices and we connect two vertices if the actors they represent have appeared in the same movie.

    • Kevin Bacon numbers: Section 10.4

 

协作图的示例

• 学术合作图表模拟了在特定主题中共同撰写论文的研究人员的合作。

  • 我们使用顶点代表研究人员进行特殊的学术研究。

  • 如果他们是论文的共同作者，我们将代表两个研究人员的顶点连接起来。

  • 数学家的协作图：第10.4节中的Erdős数字。

 

Examples of Collaboration Graphs

• An academic collaboration graph models the collaboration of researchers who have jointly written a paper in a particular subject.

  • We represent researchers in a particular academic discipline using vertices.

  • We connect the vertices representing two researchers in this discipline if they are coauthors of a paper.

  • Collaboration graph for mathematicians: Erdős numbers in Section 10.4.

 

信息网络的应用（Applications to Information Networks）

• 图表可用于模拟链接不同类型信息的不同类型的网络。

• 在Web图表中，网页由顶点表示，链接由有向边表示。

  • 网页图表在特定时间对网络进行建模。

  • 我们将在第11.4节中解释搜索引擎如何使用Web图表。

 

 

• Graphs can be used to model different types of networks that link different types of information.

• In a web graph, web pages are represented by vertices and links are represented by directed edges.

  • A web graph models the web at a particular time.

  • Wewillexplainhowthewebgraphisusedby search engines in Section 11.4.

 

• 在引文网络中：

  • 特定学科的研究论文由顶点表示。

  • 当纸张引用第二张纸作为参考时，从表示该纸张的顶点到表示第二张纸张的顶点有一条边。

 

• In a citation network:

  • Research papers in a particular discipline are represented by vertices.

  • When a paper cites a second paper as a reference, there is an edge from the vertex representing this paper to the vertex representing the second paper.

 

交通图（Transportation Graphs）

• 图模型广泛用于交通网络的研究。

• 航空公司网络可以使用有向多图来建模

  • 机场由顶点表示

  • 每个航班由表示出发机场的顶点到代表目的地机场的顶点的有向边表示

• 道路网络可以使用图表建模

  • 顶点表示交叉点，边表示道路。

  • 无向边缘代表双向道路，有向边缘代表单向道路。

 

• Graph models are extensively used in the study of transportation networks.

• Airline networks can be modeled using directed multigraphs where

  • airports are represented by vertices

  • each flight is represented by a directed edge from the vertex representing the departure airport to the vertex representing the destination airport

• Road networks can be modeled using graphs where 

  • vertices represent intersections and edges represent roads.

  • undirected edges represent two-way roads and directed edges represent one-way roads.

 

软件设计应用（Software Design Applications）

• 图模型广泛用于软件设计。 我们将在这里介绍两个这样的模型; 一个表示软件应用程序模块之间的依赖关系，另一个表示计算机程序中语句执行的限制。

• 当使用自上而下的方法设计软件时，系统分为模块，每个模块执行特定任务。

 

• Graph models are extensively used in software design. We will introduce two such models here; one representing the dependency between the modules of a software application and the other representing restrictions in the execution of statements in computer programs.

• When a top-down approach is used to design software, the system is divided into modules, each performing a specific task.

 

• 我们使用模块依赖关系图来表示这些模块之间的依赖关系。 在编码之前需要理解这些依赖性。

  • 在模块依赖图中，顶点表示软件模块，如果第二个模块依赖于第一个模块，则从一个模块到另一个模块存在边缘。

• We use a module dependency graph to represent the dependency between these modules. These dependencies need to be understood before coding can be done.

  • In a module dependency graph vertices represent software modules and there is an edge from one module to another if the second module depends on the first.

 

• 示例：Web浏览器设计中的七个模块之间的依赖关系由此模块依赖关系图表示。

 

• Example: The dependencies between the seven modules in the design of a web browser are represented by this module dependency graph.

 

 

 

• 我们可以使用一个称为优先级图的有向图来表示在执行每个语句之前必须执行的语句。

  • 顶点代表计算机程序中的声明

  • 如果在第一个顶点之前不能执行第二个顶点，则会有一个从顶点到第二个顶点的有向边

 

• We can use a directed graph called a precedence graph to represent which statements must have already been executed before we execute each statement.

  • Vertices represent statements in a computer program

  • There is a directed edge from a vertex to a second vertex if the second vertex cannot be executed before the first

 

• 示例：此优先级图表显示在我们可以执行程序中的每个语句之前必须已执行的语句。

 

• Example: This precedence graph shows which statements must already have been executed before we can execute each of the six statements in the program.

 

生物应用（Biological Applications）

• 图形模型广泛用于生物科学的许多领域。 我们将描述两个这样的模型，一个是生态学，另一个是分子生物学。

• 生态位重叠图表模拟生态系统中物种之间的竞争

  • 顶点代表物种，当它们代表竞争食物资源的物种时，边缘连接两个顶点。

 

• Graph models are used extensively in many areas of thebiologicalscience. We will describe two such models, one to ecology and the other to molecular biology.

• Niche overlap graphs model competition between species in an ecosystem

  • Vertices represent species and an edge connects two vertices when they represent species who compete for food resources.

 

• 示例：这是具有9种物种的森林生态系统的生态位重叠图。

 

• Example: This is the niche overlap graph for a forest ecosystem with nine species.

 

• 我们可以使用蛋白质相互作用网络模拟细胞中蛋白质的相互作用。

• 在蛋白质相互作用图中，顶点代表蛋白质，如果它们所代表的蛋白质相互作用，则顶点通过边缘连接。

• 蛋白质相互作用图可能很大，可能包含超过100,000个顶点，每个顶点代表不同的蛋白质，超过1,000,000个边缘，每个顶点代表蛋白质之间的相互作用

• 蛋白质相互作用图通常被分成较小的图形，称为模块，代表特定功能中涉及的蛋白质之间的相互作用。

 

• We can model the interaction of proteins in a cell using a protein interaction network.

• In a protein interaction graph, vertices represent proteins and vertices are connected by an edge if the proteins they represent interact.

• Protein interaction graphs can be huge and can contain more than 100,000 vertices, each representing a different protein, and more than 1,000,000 edges, each representing an interaction between proteins

• Protein interaction graphs are often split into smaller graphs, called modules, which represent the interactions between proteins involved in a particular function.

 

实施例：这是蛋白质的蛋白质相互作用图的模块，其降解人细胞中的RNA。

 

Example: This is a module of the protein interaction graph of proteins that degrade RNA in a human cell.