What Did Buhayan Learn?? 🤔

A. Graphs and Graph Models

What it is: A graph G = (V, E) consists of:

• V: A non-empty set of vertices (or nodes).
• E: A set of edges, where each edge connects two vertices (which could be the same vertex in the case of a loop).

• Undirected Graph: Edges have no direction (e.g., a friendship on Facebook).
• Directed Graph (Digraph): Edges have a direction (e.g., following someone on X, a one-way street).
• Weighted Graph: Each edge has an associated numerical value (weight), representing cost, distance, capacity, etc.
• Unweighted Graph: Edges do not have weights.
• Simple Graph: An undirected graph with no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices.
• Multigraph: Allows multiple edges between the same pair of vertices.

Real-life example:

• Social Network: Vertices represent people, and an undirected edge connects two people if they are friends.
• Road Network: Vertices represent intersections or cities, and edges represent roads. A weighted graph can model distances or travel times. Directed edges can model one-way streets.
• World Wide Web: Vertices represent web pages, and a directed edge from page A to page B exists if A links to B.
• Task Dependencies: In project management, vertices can be tasks, and a directed edge from task A to task B means A must be completed before B can start.

B. Graph Terminology and Special Types of Graphs

What it is: Key Terminology:

• Adjacent Vertices (Neighbors): Two vertices are adjacent if there is an edge connecting them.
• Degree of a Vertex (in an undirected graph): The number of edges incident to it (a loop counts twice).
• In-degree/Out-degree (in a directed graph): In-degree is the number of edges pointing to a vertex; out-degree is the number of edges pointing away from it.
• Path: A sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence.
• Cycle: A path that starts and ends at the same vertex and doesn't repeat edges or intermediate vertices.
• Connected Graph (undirected): There is a path between every pair of distinct vertices.
• Strongly Connected Graph (directed): There is a directed path from any vertex to any other vertex.

• Complete Graph (K_n): A simple undirected graph in which every pair of distinct vertices is connected by a unique edge. Has n(n-1)/2 edges.
• Cycle Graph (C_n): A graph consisting of a single cycle through n vertices (n ≥ 3).
• Path Graph (P_n): A graph whose vertices can be listed in an order v₁, v₂, ..., v_n such that the edges are {v_i, v_i+1} for i = 1, ..., n-1.
• Wheel Graph (W_n): A graph formed by connecting a single universal vertex to all vertices of a cycle C_n-1.
• Bipartite Graph: A graph whose vertices can be divided into two disjoint and independent sets, U and V, such that every edge connects a vertex in U to one in V.
• Tree: A connected undirected graph with no cycles. It has n vertices and n-1 edges.

Real-life example:

• Complete Graph: A small group of people where everyone knows everyone else. A network where every computer is directly connected to every other computer.
• Bipartite Graph: Modeling job applicants (set U) and job openings (set V), where an edge exists if an applicant is qualified for an opening. Useful in matching problems.
• Tree: Family trees, organizational hierarchies, file system directory structures. In computer networks, spanning trees are used to prevent broadcast storms.

C. Representing Graph and Graph Isomorphism

What it is: Ways to represent graphs for computation:

• Adjacency List: For each vertex, store a list of its adjacent vertices. Efficient for sparse graphs (few edges).
• Adjacency Matrix: A square matrix A where A[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j, and 0 otherwise. Efficient for dense graphs (many edges) or when checking for an edge quickly is needed.
• Incidence Matrix: A matrix where rows represent vertices and columns represent edges. M[v][e] = 1 if vertex v is an endpoint of edge e, and 0 otherwise.

Real-life example:

• Adjacency List/Matrix: How social network data (who is connected to whom) or road network data is stored in databases for applications like GPS navigation or friend suggestions.
• Graph Isomorphism: In chemistry, identifying if two molecular structures are the same, even if depicted differently. In circuit design, checking if two circuit layouts are equivalent.

D. Connectivity

What it is: Connectivity explores how "connected" a graph is.

• Connected Components: Maximal connected subgraphs of an undirected graph.
• Cut Vertex (Articulation Point): A vertex whose removal increases the number of connected components.
• Cut Edge (Bridge): An edge whose removal increases the number of connected components.
• Vertex Connectivity (κ(G)): The minimum number of vertices whose removal disconnects G or reduces it to a single vertex.
• Edge Connectivity (λ(G)): The minimum number of edges whose removal disconnects G.

Real-life example:

• Network Reliability: Identifying cut vertices or cut edges in a communication network (like the internet or a corporate network) helps find single points of failure. A network with higher vertex/edge connectivity is more robust.
• Social Network Analysis: Finding connected components can identify distinct communities or groups within a larger network.
• Transportation Networks: Identifying bridges (cut edges) in a road or rail network is crucial for planning detours during maintenance or emergencies.

E. Shortest-Path Problem

What it is: The problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. Common algorithms include:

• Dijkstra's Algorithm: Finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.
• Bellman-Ford Algorithm: Finds the shortest path from a single source vertex to all other vertices, and can handle graphs with negative edge weights (also detects negative cycles).
• Floyd-Warshall Algorithm: Finds the shortest paths between all pairs of vertices in a weighted graph.
• A* Search Algorithm: An informed search algorithm that uses heuristics to guide its search, often faster than Dijkstra's for finding the shortest path between two specific nodes.

Real-life example:

• GPS Navigation: Finding the shortest or fastest route between two locations (vertices are intersections/locations, edges are roads with weights like distance or travel time).
• Network Routing: Internet routers use shortest-path algorithms (like OSPF, which is based on Dijkstra's) to determine the most efficient path for data packets to travel.
• Airline Route Planning: Finding the cheapest or quickest sequence of flights between cities.
• Robotics: Path planning for robots to navigate an environment.
• Social Networks: Finding the "degrees of separation" between two people.

F. Planar Graphs

What it is: A graph is planar if it can be drawn in a plane such that no two edges cross each other (they can only meet at a common vertex). A planar representation of a planar graph is called a plane graph.

• Kuratowski's Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ (the complete graph on five vertices) or K_3,3 (the complete bipartite graph with three vertices in each part, also known as the "utility graph").
• Euler's Formula for Connected Plane Graphs: v - e + f = 2, where v is the number of vertices, e is the number of edges, and f is the number of faces (regions bounded by edges, including the outer unbounded region).

Real-life example:

• Circuit Design (PCBs): When designing printed circuit boards, components (vertices) need to be connected by conductive paths (edges) on a flat surface. Planarity is crucial to avoid short circuits from crossing paths on a single layer. If a circuit graph is not planar, multiple layers are needed.
• Utility Layout: The classic "three utilities problem" (can three houses each be connected to three utilities - gas, water, electricity - without any lines crossing?) is an example of K_3,3, which is non-planar. This relates to planning infrastructure.
• Map Design: Geographic maps can be thought of as planar graphs where regions are vertices and shared borders are edges.

G. Graph Coloring

What it is: Graph coloring is an assignment of "colors" (labels, typically integers) to elements of a graph subject to certain constraints.

• Vertex Coloring: Assigning colors to vertices such that no two adjacent vertices share the same color. The goal is often to use the minimum number of colors, called the chromatic number (χ(G)).
• Edge Coloring: Assigning colors to edges such that no two edges incident to the same vertex share the same color.

Real-life example:

• Scheduling:
  • Exam Scheduling: Vertices are exams, an edge connects two exams if at least one student is taking both. Colors represent time slots. The chromatic number gives the minimum number of time slots needed so no student has a conflict.
  • Task Scheduling: Tasks that cannot be done simultaneously (e.g., require the same resource) are connected by an edge. Colors are time slots or resources.
• Map Coloring: Coloring countries or regions on a map such that no two adjacent regions have the same color. This was the original problem that led to the Four Color Theorem.
• Frequency Assignment: Assigning radio frequencies to broadcasting towers (vertices). Towers that are close enough to interfere if using the same frequency are connected by an edge. Colors represent distinct frequencies.
• Register Allocation in Compilers: Variables in a program are vertices, an edge connects two variables if they are "live" (in use) at the same time. Colors represent CPU registers. The goal is to assign variables to registers such that conflicting variables get different registers, minimizing the need to spill variables to memory.