Graph Theory and Algorithms 02

 Introduction to Graphs: Definition of graphs, types of graphs, graph representations, and basic terminology.

1. Definition of Graphs : A graph is a collection of points (vertices) and lines (edges) that connect them. Formally, a graph G = (V, E) consists of a set of vertices V and a set of edges E, where each edge e ∈ E connects two vertices.

2. Types of Graphs: There are several types of graphs, including:

• Undirected Graphs: Edges do not have a direction, and can be traversed in either direction. Example: The friendship network of a group of people.

        

• Directed Graphs (Digraphs): Edges have a direction and can only be traversed in one direction. Example: The network of roads between cities.

• Weighted Graphs: Edges have a weight or cost associated with them. Example: A transportation network with distances or costs assigned to each road or route.

• Bipartite Graphs: Vertices can be divided into two disjoint sets such that each edge connects a vertex from one set to a vertex in the other set. Example: A dating website matching potential partners based on interests.

3. Graph Representations: There are several ways to represent a graph, including:

• Adjacency Matrix: A matrix representation where the rows and columns represent vertices, and the entries represent whether there is an edge or not. Example:

# Define the number of nodes and edges in the graph

n = 5

m = 7

# Initialize the adjacency matrix

adj_matrix = [[0 for j in range(n)] for i in range(n)]

# Add the edges to the adjacency matrix

edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

for u, v in edges:

    adj_matrix[u][v] = 1

    adj_matrix[v][u] = 1  # assuming an undirected graph

# Print the adjacency matrix

for row in adj_matrix:

    print(row)

• Adjacency List: A list representation where each vertex has a list of adjacent vertices. Example:

# Define the number of nodes and edges in the graph

n = 5

m = 7

# Initialize the adjacency list

adj_list = [[] for i in range(n)]

# Add the edges to the adjacency list

edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

for u, v in edges:

    adj_list[u].append(v)

    adj_list[v].append(u)  # assuming an undirected graph

# Print the adjacency list

for i in range(n):

    print(f"{i}: {adj_list[i]}")

• Edge List: A list representation where each entry is a pair of vertices that defines an edge. Example:

# Define the number of nodes and edges in the graph

n = 5

m = 7

# Initialize the edge list

edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

# Print the edge list

for edge in edges:

    print(edge)

4. Basic Terminology: Some basic terminology used in graph theory includes:

• Vertex: A vertex, also known as a node, is a point in the graph.
• Edge: An edge, also known as a link, is a line connecting two vertices.
• Degree: The degree of a vertex is the number of edges connected to it.
• Path: A path is a sequence of vertices connected by edges.
• Cycle: A cycle is a path that starts and ends at the same vertex.
• Connected: A graph is connected if there is a path between any pair of vertices.
• Component: A component is a connected subgraph of a graph.
• Spanning Tree: A spanning tree is a connected subgraph that includes all the vertices of the original graph but contains no cycles.