Preface :
A graph consists of a set of vertices V, along with a set of edges E that connect pairs of vertices. An edge (e = Vi, Vj) connects vertices Vi and Vj. A self-loop is an edge that connects a vertex to itself. We assume that none of our graphs have self-lookps.
In below figure, the building and the connecting walkways in a civic center from a graph. The vertices consists of three government facilities, an opera and a library.
The degree of a vertex is the number of edges originating at the vertex. Two vertices in a graph are adjacent (neighbors) if there is an edge connecting the vertices. The term path describes a more general notion of connection. Two vertices Vs and Ve lie on a path, provide that there is a sequence of vertices beginning with Vs and ending with Ve such that successive pair are adjacent vertices. The length of the path is the number of edges connecting the vertices :
For instance, in upper figure, the Library and the Human Services building are adjacent vertices. The Library and the Opera are not adjacent, but they do lie on a path of length 3 :
P(Library, Opera) = Library-Human Services-City Hall-Opera
A graph exhibits different kinds of paths. A simple path has distinct edges. For instance, [Opera-City Hall-Human Services] is a simple path, but [Human Services-Courthouse-Human Services] is not. A cycle is a simple path of positive length that starts and ends at the same vertex. Among the government buildings, a path from City Hall back to City Hall by way of [Human Services] and the [Courthouse] is a cycle. A graph with no cycle is said to be acyclic.
The existence of a path indicates that two vertices are connected. In terms of access, we say on vertex is reachable from the other. The terminology can be extended to entire graph. A graph is connected if each pair of distinct vertices has a path between them. The Civic Center is an example. A complete graph in which each pair of vertices is linked by an edge. Below figure displays examples of connected, disconnected and complete graphs :
Directed Graphs :
Up to this point, we have described an edge as a pair that connects two vertices. Movement between vertices can occur in either direction. Edges of this type are called undirected edges and the corresponding graph is called an undirected graph. For many applications, such as a city map that includes one-way streets, we want the edges of the graph to have a direction representing flow. For these graphs, an edge is an ordered pair E(vi, vj) connecting vertex vi to vj. The graph must provide a second edge, E=(vj,vi), if flow between the vertices occurs in both directions. Graphs with ordered edges are called directed graphs or digraphs. Below figure is an example of a digraph with five vertices and seven edges. In this chapter, we present a Graph interface that applies to both undirected graphs and digraphs, and we discuss an implementation, called DiGraph, that represents a digraph. For applications that need an undirected graph, we use a DiGraph object and provides pairs of directed edges to connect the vertices :
Much of the terminology for undirected graphs carries over to digraphs. For instance, vertex vi is adjacent to vertex vj if there is a directed edge (vi, vj) between the vertices. The notation E=(vi, vj) highlights the fact that the edge emanates from the source vertex vi and terminates in the destination (ending) vetex vj. A directed path connecting vertices vs and ve is a sequence of directed edges that begin at vs and end at ve. The number of the edges that emanate from a vertex v is called the out-degree of the vertex. The number of the edges that terminate in vertex v is the in-degree of the vertex. in upper figure, vertex A has out-degree 3 and in-degree 1. The out-degree of vertex E is 0, while its in-degree is 2.
The concept of connectivity is a digraph distinguishes between a strongly connected and a weakly connected digraph. A digraph is strongly connected if there is a path from any vertex to any other vertex. The digraph is weakly connected if, for each pair of vertices vi and vj, there is either a path P(vi, vj) or a path P(vj, vi). Below figure illustrates different types of connectedness for a digraph :
A cycle in a digraph is a path of length 2 or more that connects a vertex to itself. In the directed graph of upper figure(c), the vertices {A,B,C} are in a cycle. In the digraph of upper figure(b), the path A-B-A is considered a cycle. A digraph that contains no cycle is called an acyclic digraph.
Weighted Graphs :
Edges in a graph describe links between vertices. The edges may also have an associated value, called a weight, that represents an attribute such as length, flow potential, and so froth. Graphs with weighted edges are called weighted graphs. The wiring diagram of a house is an undirected graph. If each edge of the graph is labeled with the distance between outlets, the diagram is a weighted graph. Transportation managers use a weighed digraph to describe potential traffic flow on city streets. All of our graphs are weighted graphs. When the weight component is not relevant, we simply assign a weigh of 1 to each edge in the graph. Below figure illustrates a weighted job-scheduling digraph. The value of an edge defines the length of time to finish a task :
Supplement :
* [ 資料結構 小學堂 ] 圖形結構 : 圖形介紹
* Wiki : Graphy theory
A graph consists of a set of vertices V, along with a set of edges E that connect pairs of vertices. An edge (e = Vi, Vj) connects vertices Vi and Vj. A self-loop is an edge that connects a vertex to itself. We assume that none of our graphs have self-lookps.
In below figure, the building and the connecting walkways in a civic center from a graph. The vertices consists of three government facilities, an opera and a library.
The degree of a vertex is the number of edges originating at the vertex. Two vertices in a graph are adjacent (neighbors) if there is an edge connecting the vertices. The term path describes a more general notion of connection. Two vertices Vs and Ve lie on a path, provide that there is a sequence of vertices beginning with Vs and ending with Ve such that successive pair are adjacent vertices. The length of the path is the number of edges connecting the vertices :
For instance, in upper figure, the Library and the Human Services building are adjacent vertices. The Library and the Opera are not adjacent, but they do lie on a path of length 3 :
P(Library, Opera) = Library-Human Services-City Hall-Opera
A graph exhibits different kinds of paths. A simple path has distinct edges. For instance, [Opera-City Hall-Human Services] is a simple path, but [Human Services-Courthouse-Human Services] is not. A cycle is a simple path of positive length that starts and ends at the same vertex. Among the government buildings, a path from City Hall back to City Hall by way of [Human Services] and the [Courthouse] is a cycle. A graph with no cycle is said to be acyclic.
The existence of a path indicates that two vertices are connected. In terms of access, we say on vertex is reachable from the other. The terminology can be extended to entire graph. A graph is connected if each pair of distinct vertices has a path between them. The Civic Center is an example. A complete graph in which each pair of vertices is linked by an edge. Below figure displays examples of connected, disconnected and complete graphs :
Directed Graphs :
Up to this point, we have described an edge as a pair that connects two vertices. Movement between vertices can occur in either direction. Edges of this type are called undirected edges and the corresponding graph is called an undirected graph. For many applications, such as a city map that includes one-way streets, we want the edges of the graph to have a direction representing flow. For these graphs, an edge is an ordered pair E(vi, vj) connecting vertex vi to vj. The graph must provide a second edge, E=(vj,vi), if flow between the vertices occurs in both directions. Graphs with ordered edges are called directed graphs or digraphs. Below figure is an example of a digraph with five vertices and seven edges. In this chapter, we present a Graph interface that applies to both undirected graphs and digraphs, and we discuss an implementation, called DiGraph, that represents a digraph. For applications that need an undirected graph, we use a DiGraph object and provides pairs of directed edges to connect the vertices :
Much of the terminology for undirected graphs carries over to digraphs. For instance, vertex vi is adjacent to vertex vj if there is a directed edge (vi, vj) between the vertices. The notation E=(vi, vj) highlights the fact that the edge emanates from the source vertex vi and terminates in the destination (ending) vetex vj. A directed path connecting vertices vs and ve is a sequence of directed edges that begin at vs and end at ve. The number of the edges that emanate from a vertex v is called the out-degree of the vertex. The number of the edges that terminate in vertex v is the in-degree of the vertex. in upper figure, vertex A has out-degree 3 and in-degree 1. The out-degree of vertex E is 0, while its in-degree is 2.
The concept of connectivity is a digraph distinguishes between a strongly connected and a weakly connected digraph. A digraph is strongly connected if there is a path from any vertex to any other vertex. The digraph is weakly connected if, for each pair of vertices vi and vj, there is either a path P(vi, vj) or a path P(vj, vi). Below figure illustrates different types of connectedness for a digraph :
A cycle in a digraph is a path of length 2 or more that connects a vertex to itself. In the directed graph of upper figure(c), the vertices {A,B,C} are in a cycle. In the digraph of upper figure(b), the path A-B-A is considered a cycle. A digraph that contains no cycle is called an acyclic digraph.
Weighted Graphs :
Edges in a graph describe links between vertices. The edges may also have an associated value, called a weight, that represents an attribute such as length, flow potential, and so froth. Graphs with weighted edges are called weighted graphs. The wiring diagram of a house is an undirected graph. If each edge of the graph is labeled with the distance between outlets, the diagram is a weighted graph. Transportation managers use a weighed digraph to describe potential traffic flow on city streets. All of our graphs are weighted graphs. When the weight component is not relevant, we simply assign a weigh of 1 to each edge in the graph. Below figure illustrates a weighted job-scheduling digraph. The value of an edge defines the length of time to finish a task :
Supplement :
* [ 資料結構 小學堂 ] 圖形結構 : 圖形介紹
* Wiki : Graphy theory
This message was edited 6 times. Last update was at 28/03/2011 10:11:12
沒有留言:
張貼留言