A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them, called edges. Graphs have applications in modeling many domains, including mapping, transportation, computer networks, and social networks.
Viewed abstractly, a graph G is a set of V vertices and a collection E of pairs of vertices from V, called edges.
Edges can be either directed or undirected.
If all the edges in a graph are undirected, then we say the graph is an undirected graph.
Example: graph of coauthorship among some authors.
Edges are undirected because coauthorship is a symmetric relation.
If all the edges in a graph are directed, then we say the graph is a directed graph (digraph).
Example: class hierarchy diagram for an object-oriented program.
Edges are directed because the inheritance relation only goes in one direction (asymmetric).
A graph that has both directed and undirected edges is called a mixed graph
Example: A city map can be modeled as a graph whose vertices are intersections or dead ends, and whose edges are stretches of streets without intersections. This graph has both undirected edges, which correspond to stretches of two-way streets, and directed edges, which correspond to stretches of one-way streets. Thus, in this way, a graph modeling a city map is a mixed graph.
We can study air transportation by constructing a graph, called a flight network, whose vertices are associated with airports, and whose edges are associated with flights. In graph G, the edges are directed because a given flight has a specific travel direction. The endpoints of an edge in G correspond respectively to the origin and destination of the flight corresponding to that edge. Two airports are adjacent in G if there is a flight that flies between them, and an edge is incident to a vertex in G if the flight for that edge flies to or from the airport for that vertex. The outgoing edges of a vertex correspond to the outbound flights from that vertex's airport, and the incoming edges correspond to the inbound flights to that vertex's airport. Finally, the in-degree of a vertex of G corresponds to the number of inbound flights to that vertex's airport, and the out-degree of a vertex in G corresponds to the number of outbound flights.
The endpoints of edge UA 120 are origin LAX and destination ORD; hence, LAX and ORD are adjacent. The in-degree of DFW is 3, and the out-degree of DFW is 2.
Refer to the graph in the figure above.
Answer: directed
Answer: LAX
Answer: five
Answer: SFO
a directed path from BOS to LAX:
a directed cycle (ORD, MIA, DFW, LAX, ORD): its vertices induce a strongly connected subgraph
the subgraph of the vertices and edges reachable from ORD:
the removal of the dashed edges results in a directed acyclic graph:
Consider the following directed graph with 6 vertices and 9 edges.
Answer: Yes. Path G -> F -> C -> B goes from G to B.
Answer: No. When starting at B, only F and C are reachable.
Answer: F -> C -> B -> F. This cycle is a strongly connected component, as each of B, C, and F can reach the other two.
Answer: 6. A path exists from A → D → G → F → C → B.
If a graph G with m edges and vertex set V, then the total degree of G is 2m.
If G is a directed graph with m edges and vertex set V, then the total in-degree of G is the same as the total out-degree of G, which is equal to m.
Let G be a simple graph with n vertices and m edges. If G is undirected, then m <= n(n-1)/2. If G is directed, then m <= n(n-1).
Let G be an undirected graph with n vertices and m edges:
Function | Description |
---|---|
is_directed() |
Returns true if this is a directed graph and false if this is an undirected graph |
num_vertices() |
Returns the number of vertices of the graph |
vertices() |
Returns a list of all vertices of the graph |
num_edges() |
Returns the number of edges of the graph |
edges() |
Returns a list of all edges of the graph |
has_edge(u,v) |
Returns true if there exists an edge from u to v and false otherwise. For an undirected graph, there is no difference between has_edge(u, v) and has_edge(v, u) . |
get_edge(u,v) |
Returns the edge from vertex u to vertex v ; undefined behavior if no such edge exists. For an undirected graph, there is no difference between get_edge(u, v) and get_edge(v, u) . |
endpoints(e) |
Returns the pair of vertices (origin, destination) for edge e . |
opposite(e,v) |
For edge e incident to vertex v , returns the other vertex of the edge |
degree(v, out=true) |
For an undirected graph, return the number of edges incident to vertex v . For a directed graph, return the number of outgoing edges incident to vertex v by default; report the number of incoming edges incident to vertex v if the optional parameter is set to false . |
neighbors(v, out=true) |
Return a list of all vertices adjacent to vertex v . In the case of a directed graph, report neighbors via outgoing edge by default; report neighbors via incoming edge if the optional parameter is set to false . |
incident_edges(v, out=true) |
Return a list of all edges incident to vertex v . In the case of a directed graph, report outgoing edges by default; report incoming edges if the optional parameter is set to false . |
insert_vertex(x) |
Creates and returns a new Vertex storing element x |
insert_edge(u, v, w, x) |
Creates and returns a new Edge from vertex u to vertex v , having weight w (1 by default), and storing element x ; if an edge from u to v already exists, updates w and x for that edge |
erase(v) |
Removes vertex v and all its incident edges from the graph |
erase(e) |
Removes edge e from the graph |