Maths 1 week 10 Summary

📚

Graph Theory Summary

Basic Concepts

Vertices and Edges: A graph is a collection of vertices (or nodes) connected by edges. Vertices represent entities, and edges represent relationships between them.

Directed and Undirected Graphs: In a directed graph, edges have a direction, indicating a one-way relationship. In an undirected graph, edges have no direction, indicating a two-way relationship.

Paths and Walks: A path is a sequence of edges connecting a sequence of vertices without repeating any vertices. A walk allows vertices to be repeated.

Reachability: Reachability refers to the ability to get from one vertex to another within a graph. In directed graphs, this is determined by the existence of a directed path.

Coloring Problem: The coloring problem involves assigning colors to vertices so that no two adjacent vertices share the same color. This is used in scheduling and map coloring.

Vertex Cover: A vertex cover is a set of vertices such that each edge in the graph is incident to at least one vertex in the set.

Independent Set: An independent set is a set of vertices with no edges connecting them.

Matching: A matching is a set of edges without common vertices. A maximal matching is a matching that cannot be extended by adding an edge. A perfect matching covers all vertices.

Adjacency Matrix: An adjacency matrix is a square matrix used to represent a graph, where the element at row i and column j indicates the presence of an edge between vertices i and j.

Degree of Vertex: The degree of a vertex is the number of edges incident to it. In directed graphs, we have in-degree and out-degree.

Graph Traversal

BFS and DFS: Breadth-First Search (BFS) and Depth-First Search (DFS) are algorithms for traversing or searching tree or graph data structures. BFS explores all neighbors at the present depth before moving on to nodes at the next depth level. DFS explores as far as possible along each branch before backtracking.

Use of BFS and DFS: BFS is used for finding the shortest path in unweighted graphs, while DFS is used for topological sorting, cycle detection, and solving puzzles with only one solution.

Difference between BFS and DFS Tree: BFS tree is level-wise, while DFS tree is depth-wise. BFS uses a queue, and DFS uses a stack.

Cyclic and Acyclic Graphs: A cyclic graph contains at least one cycle, while an acyclic graph has no cycles. A directed acyclic graph (DAG) is a directed graph with no directed cycles.

Topological Sorting: Topological sorting of a DAG is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. It is used in scheduling tasks.