Section 7.1 Basics
Subsection 7.1.1 Graph Definition
A graph \(G = (V, E)\) consists of a set \(V\) of vertices and a set \(E\) of edges, where
\begin{equation*}
E \subset \{\{u, v\} \mid u, v \in V\}
\end{equation*}
The set of edges is a set whose elements are subsets of two vertices.
Terminology:
- Vertices are synonymous with nodes.
- Edges are synonymous with links or arcs.
- In an undirected graph edges are unordered pairs of vertices.
- In a directed graph edges are ordered pairs of vertices.
There are several ways to define a graph in Sage. We can define a graph by listing the vertices and edges:
We can define a graph with an edge list. Each edge is a pair of vertices:
We can define a graph with an edge dictionary like so:
{edge: [neighbor, neighbor, etc], edge: [ neighbor, etc], etc: [etc]} Each dictionary key is a vertex. The dictionary values are the vertex neighbors.You can improve the readability of a dictionary by placing each item of the collection on a new line:
Sage offers a collection of predefined graphs. Here are some examples:
Subsection 7.1.2 Weighted Graphs
A weighted graph has a weight, or number, associated with each edge. These weights can model anything including distances, costs, or other relevant quantities.
To create a weighted graph, add a third element to each pair of vertices.
Subsection 7.1.3 Graph Characteristics
Sage offers many built-in functions for analyzing graphs. Let’s examine the following graph:
The
vertices() method returns a list of the graph’s vertices.The
G.edges() method returns triples representing the graph’s vertices and edge labels.Return the edges as a tuple without the label by setting
labels=false.The order of \(G=(V,E)\) is the number of vertices \(|V|\text{.}\)
The size of \(G=(V,E)\) is the number of edges \(|E|\text{.}\)
The degree of the vertex \(v\text{,}\) \(deg(v)\) is the number of edges incident with \(v\text{.}\)
The degree sequence of \(G = (V, E)\) is the list of degrees of its vertices.
Subsection 7.1.4 Graphs and Matrices
The adjacency matrix of a graph is a square matrix used to represent which vertices of the graph are adjacent to which other vertices. Each entry \(a_{ij}\) in the matrix is equal to 1 if there is an edge from vertex
i to vertex j, and is equal to 0 otherwise.We can also define a graph with an adjacency matrix:
The incidence matrix is an alternative matrix representation of a graph, which describes the relationship between vertices and edges. In this matrix, rows correspond to vertices, and columns correspond to edges, with entries indicating whether a vertex is incident to an edge.
Subsection 7.1.5 Manipulating Graphs in Sage
Add a vertex to a graph:
Add a list of vertices:
Remove a vertex from a graph:
Remove a list of vertices from a graph:
Add an edge between two vertices:
Delete an edge from a graph:
Deleting a nonexistent vertex returns an error. Deleting a nonexistent edge leaves the graph unchanged. Adding a vertex or edge already in the graph, leaves the graph unchanged.
