Representing graphs

Lecture 12

Glossary

New graphs from old

When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph.

A subgraph of a graph is a graph where and .

The union of two simple graphs and is the simple graph with vertex set and edge set . The union of G ₁ and G ₂ is denoted by .

Example. Find the union of the graphs G ₁ and G ₂.

Solution: The vertex set of the union is the union of the two vertex sets, namely, { a, b, c, d, e, f }. The edge set of the union is the union of the two edge sets.

adjacent – соседний, смежный; pendant – подвесная, висячая; handshake – рукопожатие

bipartite – двусторонний; loop – петля

One way to represent a graph without multiple edges is to list all the edges of this graph. Another way to represent a graph with no multiple edges is to use adjacency lists, which specify the vertices that are adjacent to each vertex of the graph.

Example. Use adjacency lists to describe the simple graph given in Figure below.

Solution:

An edge list for a simple graph
Vertex	Adjacent vertices
a b c d e	b, c, e a a, d, e c, e a, c, d

Example. Represent the directed graph by listing all the vertices that are the terminal vertices of edges starting at each vertex of the graph.

Solution:

An edge list for a directed graph
Initial vertex	Terminal vertex
a b c d e	b, c, d, e b, d a, c, e b, c, d

Дата добавления: 2014-12-23