23-4. Degree and Degree Sequence

The degree of a vertex is defined as the number of edges connected to it. The degree sequence of a graph is a list of vertex degrees sorted in non-increasing order. This information is crucial for many graph-theoretic algorithms, including those related to network connectivity and flow.

Graph Class: Contains methods to add vertices and edges and to compute the degrees.
add_vertex(vertex): Adds a new vertex to the graph if it does not already exist.
add_edge(vertex1, vertex2): Creates an undirected edge by adding both vertices to each other's adjacency list.
degree(vertex): Calculates the degree by returning the length of the adjacency list for the specified vertex.
degree_sequence(): Compiles the degree of all vertices, sorts them in non-increasing order, and returns the degree sequence.

class Graph:
    def __init__(self):
        """Initialize an empty graph."""
        self.graph_dict = {}
    
    def add_vertex(self, vertex):
        """Add a vertex to the graph."""
        if vertex not in self.graph_dict:
            self.graph_dict[vertex] = []

def add_edge(self, vertex1, vertex2):
        """Add an edge between two vertices."""
        if vertex1 not in self.graph_dict:
            self.add_vertex(vertex1)
        if vertex2 not in self.graph_dict:
            self.add_vertex(vertex2)
        
        self.graph_dict[vertex1].append(vertex2)
        self.graph_dict[vertex2].append(vertex1)  # For undirected graph
    
    def degree(self, vertex):
        """Return the degree of a vertex."""
        if vertex in self.graph_dict:
            return len(self.graph_dict[vertex])
        return 0
    
    def degree_sequence(self):
        """Return the degree sequence of the graph."""
        return sorted([self.degree(vertex) for vertex in self.graph_dict], reverse=True)

# Example usage
if __name__ == "__main__":
    g = Graph()
    g.add_edge("A", "B")
    g.add_edge("A", "C")
    g.add_edge("B", "C")
    g.add_edge("C", "D")
    
    print("Degree Sequence:", g.degree_sequence())

Output: show the degree sequence of the constructed graph based on the vertices and edges added.

Last updated: April 23, 2025

Python Programming

23-4. Degree and Degree Sequence