🔶Intro to Abstract Math Unit 7 – Graph Theory

What's Graph Theory?

• Branch of mathematics that studies graphs, which are mathematical structures used to model pairwise relations between objects
• Graphs consist of vertices (also called nodes) which are connected by edges (also called links or lines)
• Provides a way to represent and analyze complex networks and relationships in various fields (social networks, computer networks, transportation networks)
• Offers a framework for solving problems involving connectivity, optimization, and flow in networks
• Has applications in computer science, engineering, biology, social sciences, and many other areas
• Enables the study of properties and characteristics of graphs (connectivity, cycles, paths, degree, centrality)
• Allows for the development of algorithms and techniques to solve graph-related problems (shortest path, minimum spanning tree, network flow)

Key Concepts and Definitions

• Vertex (node): A fundamental unit of a graph representing an object or entity
• Edge (link or line): A connection between two vertices representing a relationship or interaction
• Adjacency: Two vertices are adjacent if they are connected by an edge
• Path: A sequence of vertices connected by edges, where no vertex is repeated
• Cycle: A path that starts and ends at the same vertex
• Degree: The number of edges incident to a vertex
  • In-degree: The number of incoming edges to a vertex (in directed graphs)
  • Out-degree: The number of outgoing edges from a vertex (in directed graphs)
• Subgraph: A graph formed from a subset of vertices and edges of the original graph
• Connectivity: A graph is connected if there is a path between every pair of vertices
• Component: A maximal connected subgraph of a graph
• Clique: A complete subgraph where every pair of vertices is connected by an edge

Types of Graphs

• Undirected graph: Edges have no direction or orientation (friendship network)
• Directed graph (digraph): Edges have a direction or orientation (web page links)
• Weighted graph: Edges have associated weights or costs (road network with distances)
• Complete graph: Every pair of vertices is connected by an edge
• Bipartite graph: 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 (student-course enrollment)
• Tree: A connected acyclic undirected graph (hierarchical structure)
  • Rooted tree: A tree with a designated root vertex and parent-child relationships
• Planar graph: A graph that can be drawn on a plane without any edge crossings (map of countries)

Graph Properties and Characteristics

• Order: The number of vertices in a graph
• Size: The number of edges in a graph
• Density: The ratio of the number of edges to the maximum possible number of edges
• Diameter: The maximum shortest path distance between any pair of vertices
• Radius: The minimum eccentricity of any vertex, where eccentricity is the maximum distance from a vertex to any other vertex
• Centrality measures: Metrics that determine the importance or influence of vertices in a graph
  • Degree centrality: Based on the number of edges incident to a vertex
  • Closeness centrality: Based on the average shortest path distance from a vertex to all other vertices
  • Betweenness centrality: Based on the number of shortest paths passing through a vertex
• Clustering coefficient: A measure of the tendency of vertices to cluster together
• Chromatic number: The minimum number of colors needed to color the vertices such that no adjacent vertices have the same color

Common Graph Problems

• Shortest path problem: Finding the path with the minimum total weight between two vertices (Dijkstra's algorithm, Bellman-Ford algorithm)
• Minimum spanning tree (MST) problem: Finding a tree that connects all vertices with the minimum total edge weight (Kruskal's algorithm, Prim's algorithm)
• Network flow problem: Finding the maximum flow that can be sent from a source vertex to a sink vertex through a network with edge capacities (Ford-Fulkerson algorithm)
• Traveling salesman problem (TSP): Finding the shortest possible route that visits each vertex exactly once and returns to the starting vertex (NP-hard problem)
• Graph coloring problem: Assigning colors to vertices such that no adjacent vertices have the same color (used in scheduling and resource allocation)
• Vertex cover problem: Finding the smallest set of vertices such that every edge is incident to at least one vertex in the set (used in network security and facility location)
• Independent set problem: Finding the largest set of vertices such that no two vertices in the set are adjacent (used in coding theory and scheduling)

Algorithms and Techniques

• Breadth-first search (BFS): Traversing a graph level by level, exploring all neighbors of a vertex before moving to the next level (used for shortest path in unweighted graphs)
• Depth-first search (DFS): Traversing a graph by exploring as far as possible along each branch before backtracking (used for cycle detection and connectivity)
• Dijkstra's algorithm: Finding the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights
• Bellman-Ford algorithm: Finding the shortest path from a single source vertex to all other vertices in a weighted graph, allowing for negative edge weights
• Floyd-Warshall algorithm: Finding the shortest path between all pairs of vertices in a weighted graph
• Kruskal's algorithm: Finding the minimum spanning tree of a weighted undirected graph by adding edges in increasing order of weight, avoiding cycles
• Prim's algorithm: Finding the minimum spanning tree of a weighted undirected graph by starting with a single vertex and adding the nearest vertex at each step
• Ford-Fulkerson algorithm: Finding the maximum flow in a network by iteratively finding augmenting paths and updating the residual graph
• Topological sorting: Ordering the vertices of a directed acyclic graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering

Real-World Applications

• Social network analysis: Studying the structure and dynamics of social relationships (friendship networks, collaboration networks)
• Computer networks: Designing and optimizing network topologies, routing protocols, and resource allocation (Internet, wireless networks)
• Transportation networks: Planning and managing transportation systems (road networks, airline networks, public transit)
• Biological networks: Analyzing interactions between biological entities (protein-protein interaction networks, metabolic networks)
• Recommendation systems: Suggesting items or products based on user preferences and item similarities (e-commerce, movie recommendations)
• Web search engines: Ranking web pages based on their importance and relevance (PageRank algorithm)
• Resource allocation: Assigning resources to tasks or agents efficiently (job scheduling, facility location)
• Epidemiology: Modeling the spread of diseases and identifying key individuals for targeted interventions (contact networks)

Practice Problems and Examples

1. Given a weighted undirected graph, find the shortest path between two vertices using Dijkstra's algorithm.
2. Determine the minimum spanning tree of a weighted undirected graph using Kruskal's algorithm.
3. Find the maximum flow in a network from a source vertex to a sink vertex using the Ford-Fulkerson algorithm.
4. Check if a given undirected graph is bipartite using breadth-first search (BFS).
5. Color the vertices of a graph using the minimum number of colors such that no adjacent vertices have the same color (graph coloring problem).
6. Find the strongly connected components of a directed graph using Kosaraju's algorithm.
7. Determine the shortest path between all pairs of vertices in a weighted graph using the Floyd-Warshall algorithm.
8. Solve the traveling salesman problem (TSP) for a given set of cities and their pairwise distances using a heuristic approach (nearest neighbor algorithm).