Introduction to Graph Theory

Definition of Graph

A graph is a network that helps define and visualize relationships between components.
Vertices (Nodes): Represent the components (circles in a graph).
Edges: Represent the relationships (lines connecting the circles).
Graph theory studies the properties of these networks and how they can model and solve various problems.

Graphs are prevalent in many fields, including:
- Mapping and Navigation Applications: Model roads and intersections as graphs.
- Social Networks: Model friendships between individuals as graphs.
- Sudoku: Graph theory can be applied to efficiently solve Sudoku puzzles by representing constraints as graphs.

A graph is defined as a set of vertices and edges, where each edge connects two vertices.
Mathematical representation:
- Vertex Set: V = {0, 1, 2, 3, 4}
- Edge Set: E = {(0,1), (0,2), (0,3), (1,3), (2,3), (3,4)}

Neighbors: Two vertices are neighbors if an edge connects them.
Degree: The number of edges connected to a vertex.
Paths: A sequence of vertices connected by edges. Path length is the number of edges in the path.
Cycles: A path that starts and ends at the same vertex.
Connectivity:
- Two vertices are connected if a path exists between them.
- A graph is connected if all vertices are pairwise connected.
- Connected Component: A subset of vertices that are connected.

Undirected Graph: Edges imply mutual connection (e.g., edge from vertex 0 to 1 implies edge from 1 to 0).
Directed Graph: Edges are unidirectional.
- Directed Cyclic Graph: Contains cycles.
- Directed Acyclic Graph: No cycles.
Weighted Graph: Edges have different weights, representing metrics like distances.
Trees: Connected and acyclic graphs with unique properties (removing an edge disconnects the graph).

Adjacency Matrix: A matrix that indicates connections between vertices (1 if edge exists, 0 otherwise).
Edge Set: A set containing all edges of the graph.
Adjacency List: Each vertex maps to a list of its neighbors; the most common representation for sparse graphs.

Connectivity Problem: Finding if there exists a path between two vertices.
Shortest Path Problem: Determining the least length path between two vertices.
Cycle Detection: Algorithms used for connectivity can also solve this.
Vertex Coloring: Assign colors to vertices such that no two connected vertices share the same color.
Paths Using Every Edge/Vertex: Finding paths that use all edges or vertices exactly once; known to be complex problems.

Explored the importance and applications of graph theory.
Defined key terms and types of graphs.
Discussed methods for representing graphs as data structures.
Introduced interesting problems in graph theory, setting the stage for future algorithm discussions.