Adjacency and Degree#
Adjacency and Degree Functions for a Graph#
- Degree(u): GrphVert -> RngIntElt#
Given a vertex \(u\) of the graph \(G\), return the degree of \(u\), ie the number of edges incident to \(u\).
- Alldeg(G, n): GrphUnd, RngIntElt -> { GrphVert}#
Given a graph \(G\), and a non-negative integer \(n\), return the set of all vertices of \(G\) that have degree equal to \(n\).
- MaximumDegree(G): GrphUnd -> RngIntElt, GrphVert#
- Maxdeg(G): GrphUnd -> RngIntElt, GrphVert#
The maximum of the degrees of the vertices of the graph \(G\). This function returns two values: the maximum degree, and a vertex of \(G\) having that degree.
- MinimumDegree(G): GrphUnd -> RngIntElt, GrphVert#
- Mindeg(G): GrphUnd -> RngIntElt, GrphVert#
The minimum of the degrees of the vertices of the graph \(G\). This function returns two values: the minimum degree, and a vertex of \(G\) having that degree.
- DegreeSequence(G): Grph -> [ { GrphVert} ]#
Given a graph \(G\) such that the maximum degree of any vertex of \(G\) is \(r\), return a sequence \(D\) of length \(r+1\), such that \(D[i]\), \(1 \leq i \leq r+1\), is the number of vertices in \(G\) having degree \(i-1\).
- Valence(G): GrphUnd -> RngIntElt#
Given a regular graph \(G\), return the valence of \(G\) (the degree of any vertex).
- Neighbours(u): GrphVert -> { GrphVert}#
- Neighbors(u): GrphVert -> { GrphVert}#
Given a vertex \(u\) of the graph \(G\), return the set of vertices of \(G\) that are adjacent to \(u\).
- IncidentEdges(u): GrphVert -> { GrphEdge}#
The set of all edges incident with the vertex \(u\).
- Bipartition(G): GrphUnd -> [ { GrphVert} ]#
Given a bipartite graph \(G\), return its two partite sets in the form of a pair of subsets of \(V(G)\).
- MinimumDominatingSet(G): GrphUnd -> SetEnum#
A dominating set \(S\) of a graph \(G\) is such that the vertices of \(S\) together with the vertices adjacent to vertices in \(S\) form the vertex-set of \(G\). A dominating set \(S\) is minimal if no proper subset of \(S\) is a dominating set. A minimum dominating set is a minimal dominating set of smallest size. The algorithm implemented is a backtrack algorithm (see [Christofides, 1975] p. 41).
Adjacency and Degree Functions for a Digraph#
- InDegree(u): GrphVert -> RngIntElt#
The number of edges directed into the vertex \(u\) belonging to the directed graph \(G\).
- OutDegree(u): GrphVert -> RngIntElt#
The number of edges of the form \(uv\) where \(u\) is a vertex belonging to the directed graph \(G\).
- Degree(u): GrphVert -> RngIntElt#
Given a vertex \(u\) belonging to the digraph \(G\), return the total degree of \(u\), i.e. the sum of the in–degree and out–degree for \(u\).
- Alldeg(G, n): GrphDir, RngIntElt -> { GrphVert}#
Given a digraph \(G\), and a non–negative integer \(n\), return the set of all vertices of \(G\) that have total degree equal to \(n\).
- MaximumInDegree(G): GrphDir -> RngIntElt, GrphVert#
- Maxindeg(G): GrphDir -> RngIntElt, GrphVert#
The maximum indegree of the vertices of the digraph \(G\). This function returns two values: the maximum indegree, and the first vertex of \(G\) having that degree.
- MaximumOutDegree(G): GrphDir -> RngIntElt, GrphVert#
- Maxoutdeg(G): GrphDir -> RngIntElt, GrphVert#
The maximum outdegree of the vertices of the digraph \(G\). This function returns two values: the maximum outdegree, and the first vertex of \(G\) having that degree.
- MinimumInDegree(G): GrphDir -> RngIntElt, GrphVert#
- Minindeg(G): GrphDir -> RngIntElt, GrphVert#
The minimum indegree of the vertices of the digraph \(G\). This function returns two values: the minimum indegree, and the first vertex of \(G\) having that degree.
- MinimumOutDegree(G): GrphDir -> RngIntElt, GrphVert#
- Minoutdeg(G): GrphDir -> RngIntElt, GrphVert#
The minimum outdegree of the vertices of the digraph \(G\). This function returns two values: the minimum outdegree, and the first vertex of \(G\) having that degree.
- MaximumDegree(G): GrphDir -> RngIntElt, GrphVert#
- Maxdeg(G): GrphDir -> RngIntElt, GrphVert#
The maximum total degree of the vertices of the digraph \(G\). This function returns two values: the maximum total degree, and the first vertex of \(G\) having that degree.
- MinimumDegree(G): GrphDir -> RngIntElt, GrphVert#
- Mindeg(G): GrphDir -> RngIntElt, GrphVert#
The minimum total degree of the vertices of the digraph \(G\). This function returns two values: the minimum total degree, and the first vertex of \(G\) having that degree.
- DegreeSequence(G): Grph -> [ { GrphVert} ]#
Given a digraph \(G\) such that the maximum degree of any vertex of \(G\) is \(r\), return a sequence \(D\) of length \(r+1\), such that \(D[i]\), \(1 \leq i \leq r+1\), is the number of vertices in \(G\) having degree \(i-1\).
- InNeighbours(u): GrphVert -> { GrphVert}#
- InNeighbors(u): GrphVert -> { GrphVert}#
Given a vertex \(u\) of the digraph \(G\), return the set containing all vertices \(v\) such that \(vu\) is an edge in the digraph, i.e. the starting points of all edges that are directed into the vertex \(u\).
- OutNeighbours(u): GrphVert -> { GrphVert}#
- OutNeighbors(u): GrphVert -> { GrphVert}#
Given a vertex \(u\) of the digraph \(G\), return the set of vertices \(v\) of \(G\) such that \(uv\) is an edge in the graph \(G\), i.e. the set of vertices \(v\) that are the end vertices of edges directed from \(u\) to \(v\).
- IncidentEdges(u): GrphVert -> { GrphEdge}#
The set of all edges incident with the vertex \(u\).