TOPICS TO BE COVERED
1. Introduction.
2. Types of graph.
3. Overview of algorithms.
WHAT IS GRAPH THEORY?
It is the study of properties and applications of graph or networks.
TYPES OF GRAPH:
1. UNDIRECTED GRAPH:
In this type of graph, edges has no orientation. The edge (x, y) is identical to (y, x).
2. DIRECTED GRAPH:
In this type of graph, edges have orientation and edge (x, y) is not identical to (y, x).
3. WEIGHTED GRAPH:
In this type of graph, edges have weighted values like weight, height, cost etc.
4. TREE
It is an undirected graph with no cycles.
5. ROOTED TREE
It is a tree with a designated root node where every edge either points away from or towards the root node. When edges points away from the root node, then it is called arborescence or out tree, else called anti-arborescence or in tree.
6. DIRECTED ACYCLIC GRAPHS:
It has directed edges but no cycles. All out trees are directed acyclic graph.
7. BIPARTITE GRAPHS:
These are the graphs whose vertices can be split into two independent groups u, v such that every edge connects between u and v.
8. COMPLETE GRAPH:
It is a type of graph where there is unique edge between every pair of nodes.
OVERVIEW OF ALGORITHMS:
1. SHORTEST PATH PROBLEM:
Algorithms that can be used are- BFS( Breadth first search), Dijkstra's algorithm, Bellman-Ford algorithm, Floyd- warshall algorithm, A* etc.
2. CONNECTIVITY:
Algorithms that can be used are- DFS (Depth first search ), BFS etc
3. DETECTING NEGATIVE CYCLES:
Algorithms that can be used are- Bellman-Ford, Floyd-Warshall etc
4. STRONGLY CONNECTED COMPONENTS:
Algorithms that can be used are- Tarjan's algorithm, Kosaraju's algorithm etc.
5. TRAVELLING SALESMAN PROBLEM:
Algorithms that can be used are- Held-Karp, branch and bound etc.
6. BRIDGES ON A GRAPH
7. ARTICULATION POINTS
8. MINIMUM SPANNING TREE (MST):
Algorithms that can be used are: Kruskal's algorithm, Prim's and Boruvka's algorithm etc.
9. NETWORK FLOW:
Algorithms can be used: Ford- Fulkerson, Edmonds-Karp & Dinic's algorithm.
Problems related to graph theory
https://www.cuplex2b.com/2021/02/shortest-path-in-maze-using-dfs.html
0 Comments