Graph Thoery
Graphs is said to be a fundamental data structures
It is used in various computer science applications
Graph is also used network design, social network analysis, and route planning.
Generally, we understand that graph terminology is crucial for effectively navigating and manipulating graph data structures.
So, In this article, we will discuss the graph terminology used in the data structure.
Let’s explore some essential graph terminology to get a solid grasp of the basics:
1. Vertex (Node)
Definition: A fundamental unit of a graph, representing an entity or a point.
Example: In a social network, a person can be represented as a vertex.
2. Edge (Link)
Definition: A connection between two vertices, which can be directed or undirected.
Example: In a social network, a friendship between two people is represented as an edge.
3. Adjacency
Definition: Two vertices are adjacent if there is an edge connecting them.
Example: If there's a direct connection (edge) between vertices A and B, A and B are considered adjacent.
4. Graph
Definition: A collection of vertices and edges. Graphs can be categorized based on their properties.
Example: A social network graph where vertices represent people and edges represent friendships.
5. Directed Graph (Digraph)
Definition: A graph where edges have a direction, going from one vertex to another.
Example: A workflow with tasks where some tasks need to be completed before others.
6. Undirected Graph
Definition: A graph where edges have no direction, making the connection between vertices bidirectional.
Example: An undirected social network where friendships are mutual.
7. Weighted Graph
Definition: A graph where edges have weights, representing costs, distances, or other metrics.
Example: A road network where edges represent distances between cities.
8. Unweighted Graph
Definition: A graph where edges have no weights or all edges are considered to have the same weight (typically 1).
Example: A simple social network where all connections are equal.
9. Path
Definition: A sequence of vertices connected by edges.
Example: In a city map, a path could represent the route from one location to another.
10. Cycle
Definition: A path that starts and ends at the same vertex, without repeating any other vertices or edges.
Example: A route that forms a loop in a city.
11. Connected Graph
Definition: A graph in which there is a path between every pair of vertices.
Example: A network of computers where every computer can communicate with every other computer.
12. Disconnected Graph
Definition: A graph where some vertices are not connected by any path.
Example: A set of isolated networks that do not communicate with each other.
13. Subgraph
Definition: A portion of a graph formed from a subset of its vertices and edges.
Example: A section of a social network graph focusing on a particular community.
14. Tree
Definition: A connected acyclic graph.
Example: A hierarchical organization chart.
15. Forest
Definition: A disjoint set of trees (i.e., a collection of trees).
Example: Multiple organizational charts that do not share any common vertices.
16. Degree of a Vertex
Definition: The number of edges incident to a vertex.
Example: In a social network, the degree of a person could represent their number of friends.
17. Indegree and Outdegree
Definition: In a directed graph, the indegree is the number of incoming edges to a vertex, and the outdegree is the number of outgoing edges from a vertex.
Example: In a citation graph, the indegree could represent how many times a paper has been cited, and the outdegree represents how many papers it cites.
These terms provide a solid foundation for understanding and solving graph-related problems. Happy learning!
