Introduction to Graph Theory in Computer Science

What is a Graph?

Simplest definition: A network that defines and visualizes relationships between components.
Components -> circles called vertices or nodes.
Relationships -> lines called edges.

Graphs are prevalent in various fields:
- Mapping and Navigation: Model roads (edges) and intersections (vertices).
- Social Networks: Model friendships (edges) between people (vertices).
- Sudoku: Solving puzzles by mapping numbers to graph colorings.

Vertices (or Nodes): Fundamental components of a graph.
Edges: Connections between vertices.
Neighbors: Two vertices connected by an edge.
Degree of a Vertex: Number of edges connected to a vertex (number of neighbors).
Paths: Sequence of vertices connected by edges. Length is the number of edges in the path.
Cycle: A path that starts and ends at the same vertex. All cycles are paths but not all paths are cycles.
Connectivity: Two vertices are connected if a path exists. A graph is connected if all vertices are pairwise connected.
Connected Component: Subset of vertices that is connected.

Undirected Graph: Edges imply bidirectional relationships.
Directed Graph: Edges are unidirectional.
- Directed Cyclic Graph: Contains cycles.
- Directed Acyclic Graph (DAG): Contains no cycles.
Weighted Graph: Edges have weights, modeling metrics like traffic or distances.
Tree: A connected, acyclic graph. Removing an edge disconnects it; adding one creates a cycle.

Adjacency Matrix: Matrix representation where if there's an edge between node i and j, entry is 1; otherwise, 0.
Edge Set: Set of edges for the graph.
Adjacency List: Maps each vertex to a list of its neighbors. Preferred for sparse graphs (large vertices, few edges per vertex).

Connectivity: Are two vertices connected? Is the graph connected?
Shortest Path: Path of least length between two vertices.
Cycle Detection: Detecting cycles in a graph.
Vertex Coloring: Assign colors to vertices ensuring no two neighbors share the same color.
Eulerian Path: Path that uses every edge exactly once.
Hamiltonian Path: Path that uses every vertex exactly once. No efficient algorithm exists.

Graph theory has numerous applications and is pivotal in understanding relationships and solving complex problems.
Important concepts: terminology, types of graphs, representations, and key problems.
Future content will dive deeper into graph algorithms for these problems.