📊Graph Theory Unit 2 – Graph Terminology and Basic Properties

What's a Graph Anyway?

• Graphs model pairwise relationships between objects
• Consist of a set of vertices (also called nodes) and a set of edges connecting some pairs of vertices
• Edges represent relationships or connections between vertices
• Can be directed (edges have a specific direction) or undirected (edges have no direction)
• Useful for representing networks (social networks), transportation systems (road networks), and many other real-world scenarios
• Provide a powerful tool for analyzing complex systems and solving problems
• Enable the study of properties such as connectivity, shortest paths, and network flow

Building Blocks: Vertices and Edges

• Vertices are the fundamental units of a graph
  • Represent objects, entities, or points of interest
  • Denoted by letters (a, b, c) or numbers (1, 2, 3)
• Edges connect pairs of vertices
  • Represent relationships, connections, or interactions between vertices
  • Can be undirected (no specific direction) or directed (have a specific direction)
• Edges can have weights or labels
  • Weights represent the cost, distance, or strength of the connection
  • Labels provide additional information about the nature of the connection
• Self-loops are edges that connect a vertex to itself
• Multiple edges can exist between the same pair of vertices (multigraph)

Types of Graphs: A Quick Tour

• Simple graphs have no self-loops or multiple edges between the same pair of vertices
• Multigraphs allow multiple edges between the same pair of vertices
• Directed graphs (digraphs) have edges with specific directions
  • Edges are represented as ordered pairs (a, b) indicating a directed edge from vertex a to vertex b
• Weighted graphs assign weights or costs to edges
  • Weights can represent distance, time, or any other relevant measure
• Bipartite graphs have two disjoint sets of vertices, with edges only connecting vertices from different sets
• Complete graphs have an edge between every pair of vertices
• Planar graphs can be drawn on a plane without any edges crossing

Graph Properties That Matter

• Order of a graph is the number of vertices in the graph
• Size of a graph is the number of edges in the graph
• Density of a graph measures the ratio of the actual number of edges to the maximum possible number of edges
  • Calculated as $density = \frac{2|E|}{|V|(|V|-1)}$ for undirected graphs and $density = \frac{|E|}{|V|(|V|-1)}$ for directed graphs
• Degree of a vertex is the number of edges incident to it
  • In-degree and out-degree are used for directed graphs
• Connectivity refers to the presence of paths between vertices
  • Connected graphs have a path between every pair of vertices
  • Disconnected graphs have at least one pair of vertices with no path between them
• Diameter of a graph is the maximum shortest path distance between any two vertices

Degree and Connectivity: Getting to Know Your Graph

• Degree of a vertex is the number of edges incident to it
  • For undirected graphs, degree is the number of edges connected to the vertex
  • For directed graphs, in-degree is the number of incoming edges, and out-degree is the number of outgoing edges
• Degree sequence is the list of degrees of all vertices in the graph
  • Provides insights into the structure and properties of the graph
• Handshaking lemma states that the sum of degrees of all vertices in an undirected graph is twice the number of edges
  • Mathematically, $\sum_{v \in V} deg(v) = 2|E|$
• Connected graphs have a path between every pair of vertices
  • Can traverse from any vertex to any other vertex through a sequence of edges
• Disconnected graphs have at least one pair of vertices with no path between them
  • Consist of multiple connected components
• Bridges are edges whose removal disconnects the graph
• Articulation points (cut vertices) are vertices whose removal disconnects the graph

Paths, Cycles, and Walks: Taking a Stroll

• Walk is a sequence of vertices and edges, starting and ending at vertices, with each edge connecting consecutive vertices
  • Can repeat vertices and edges
• Path is a walk with no repeated vertices
  • Represents a sequence of distinct vertices connected by edges
• Cycle is a path that starts and ends at the same vertex
  • Has no repeated vertices except for the starting/ending vertex
• Simple path is a path with no repeated edges
• Simple cycle is a cycle with no repeated edges (except for the starting/ending vertex)
• Shortest path between two vertices is a path with the minimum number of edges or minimum total weight
• Eulerian path is a path that uses every edge exactly once
• Eulerian cycle is a cycle that uses every edge exactly once
• Hamiltonian path is a path that visits every vertex exactly once
• Hamiltonian cycle is a cycle that visits every vertex exactly once

Representing Graphs: From Paper to Computer

• Adjacency matrix is a square matrix representation of a graph
  • Rows and columns represent vertices
  • Entries indicate the presence (1 or weight) or absence (0) of an edge between vertices
• Adjacency list is a collection of lists, one for each vertex, storing its neighboring vertices
  • Efficient for sparse graphs (graphs with few edges compared to the maximum possible edges)
• Edge list is a list of all edges in the graph, represented as pairs of vertices
  • Simple and space-efficient representation
• Incidence matrix is a matrix with rows representing vertices and columns representing edges
  • Entries indicate the presence (1 or -1 for directed graphs) or absence (0) of an edge incident to a vertex
• Graph data structures in programming languages (Python, Java) provide built-in methods for graph operations
  • Adding/removing vertices and edges, checking connectivity, finding paths, etc.

Real-World Applications: Graphs in Action

• Social networks use graphs to represent connections between individuals
  • Vertices represent people, and edges represent friendships or interactions
  • Helps analyze social relationships, communities, and influence
• Transportation networks model road systems, airline routes, and public transit
  • Vertices represent locations (cities, airports), and edges represent routes or connections
  • Used for route planning, optimization, and network design
• Computer networks represent connections between devices and servers
  • Vertices represent computers or routers, and edges represent communication links
  • Helps analyze network topology, data flow, and security
• Recommendation systems use graphs to model relationships between users and items
  • Vertices represent users and items (products, movies), and edges represent interactions or preferences
  • Enables personalized recommendations based on user behavior and item similarities
• Biological networks model interactions between biological entities
  • Protein-protein interaction networks, metabolic networks, and gene regulatory networks
  • Helps understand complex biological processes and identify key components
• Project scheduling uses graphs to represent task dependencies
  • Vertices represent tasks, and edges represent dependencies between tasks
  • Allows for optimizing project timelines, resource allocation, and identifying critical paths