🧩Discrete Mathematics Unit 8 – Graph Theory

What's Graph Theory?

• Branch of mathematics that studies the properties and applications of graphs
• Graphs model pairwise relations between objects
• Consists of vertices (nodes) connected by edges (links)
• Edges can be directed or undirected
  • Directed edges have a specific direction and are represented by arrows
  • Undirected edges have no specific direction and are represented by lines
• Graphs can be weighted or unweighted
  • Weighted graphs have values assigned to their edges
  • Unweighted graphs do not have values assigned to their edges
• Used to solve problems in various fields (computer science, social networks, transportation)

Key Concepts and Definitions

• Vertex (node): Fundamental unit of a graph, represents an object or entity
• Edge (link): Connection between two vertices, represents a relationship or interaction
• Adjacent vertices: Two vertices connected by an edge
• Degree of a vertex: Number of edges incident to a vertex
  • In-degree: Number of incoming edges to a vertex (directed graphs)
  • Out-degree: Number of outgoing edges from a vertex (directed graphs)
• Path: Sequence of vertices connected by edges, with no repeated vertices
• Cycle: Path that starts and ends at the same vertex
• Connected graph: Graph where there is a path between any two vertices
• Disconnected graph: Graph where there exists at least one pair of vertices with no path between them

Types of Graphs

• Simple graph: Unweighted, undirected graph with no loops or multiple edges
• Multigraph: Graph that allows multiple edges between the same pair of vertices
• Directed graph (digraph): Graph with directed edges
• Weighted graph: Graph with weights assigned to its edges
• Complete graph: Simple graph where every pair of vertices is connected by an edge
• Bipartite graph: Graph whose vertices can be divided into two disjoint sets, such that every edge connects a vertex in one set to a vertex in the other set
• Tree: Connected, undirected graph with no cycles
  • Rooted tree: Tree with a designated root vertex, inducing a hierarchy among the vertices
  • Binary tree: Rooted tree where each vertex has at most two children (left and right)

Graph Representation

• Adjacency matrix: Square matrix representing a graph, where the entry at row i and column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise
  • Space complexity: $O(V^2)$, where V is the number of vertices
  • Suitable for dense graphs (many edges relative to the number of vertices)
• Adjacency list: Collection of lists, where each list corresponds to a vertex and contains the vertices adjacent to it
  • Space complexity: $O(V + E)$, where V is the number of vertices and E is the number of edges
  • Suitable for sparse graphs (few edges relative to the number of vertices)
• Edge list: List of all edges in the graph, represented as pairs of vertices
  • Space complexity: $O(E)$, where E is the number of edges
  • Useful for iterating over all edges in the graph

Graph Properties and Characteristics

• Connectivity: Measure of how well-connected a graph is
  • Strongly connected: Directed graph where there is a directed path from any vertex to any other vertex
  • Weakly connected: Directed graph where its underlying undirected graph is connected
• Diameter: Maximum shortest path length between any pair of vertices in the graph
• Centrality measures: Quantify the importance of vertices in a graph
  • Degree centrality: Based on the number of edges incident to a vertex
  • Betweenness centrality: Based on the number of shortest paths passing through a vertex
  • Closeness centrality: Based on the average shortest path length from a vertex to all other vertices
• Clique: Complete subgraph of a graph
  • Maximum clique: Clique with the largest possible number of vertices
• Independent set: Set of vertices in a graph, no two of which are adjacent
  • Maximum independent set: Independent set with the largest possible number of vertices

Graph Algorithms

• Breadth-First Search (BFS): Traverses a graph level by level, exploring all neighbors of a vertex before moving to the next level
  • Time complexity: $O(V + E)$, where V is the number of vertices and E is the number of edges
  • Applications: Shortest path in unweighted graphs, connected components, bipartiteness testing
• Depth-First Search (DFS): Traverses a graph by exploring as far as possible along each branch before backtracking
  • Time complexity: $O(V + E)$, where V is the number of vertices and E is the number of edges
  • Applications: Cycle detection, topological sorting, strongly connected components
• Dijkstra's algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights
  • Time complexity: $O((V + E) \log V)$ with a priority queue, where V is the number of vertices and E is the number of edges
• Kruskal's algorithm: Finds a minimum spanning tree in a weighted, undirected graph
  • Time complexity: $O(E \log E)$ or $O(E \log V)$ with a disjoint-set data structure, where V is the number of vertices and E is the number of edges
• Prim's algorithm: Finds a minimum spanning tree in a weighted, undirected graph
  • Time complexity: $O((V + E) \log V)$ with a priority queue, where V is the number of vertices and E is the number of edges

Applications of Graph Theory

• Social networks: Modeling relationships and interactions between people (Facebook, Twitter)
• Computer networks: Representing connections between computers and devices (Internet, LAN)
• Transportation networks: Modeling roads, railways, and flight routes for efficient planning and routing
• Biological networks: Representing interactions between genes, proteins, and other biological entities
• Recommendation systems: Suggesting products, services, or content based on user preferences and behavior (Amazon, Netflix)
• Resource allocation: Assigning limited resources to tasks or agents in an optimal manner (job scheduling, network flow)

Common Problems and Exercises

• Shortest path problem: Find the shortest path between two vertices in a graph
• Minimum spanning tree: Find a tree that connects all vertices in a weighted graph with the minimum total edge weight
• Graph coloring: Assign colors to vertices such that no two adjacent vertices have the same color, using the minimum number of colors
• Traveling salesman problem: Find the shortest possible route that visits each vertex exactly once and returns to the starting vertex
• Network flow: Determine the maximum flow that can be sent from a source vertex to a sink vertex through a network with capacity constraints on the edges
• Hamiltonian cycle: Find a cycle that visits each vertex exactly once in a graph
• Eulerian circuit: Find a closed walk that visits each edge exactly once in a graph
• Graph isomorphism: Determine whether two graphs are isomorphic (have the same structure)