Graph

A Graph is a way to show connections between things. It is made up of dots, called vertices (or nodes), and lines, called edges (or links), that connect the dots. Graphs help us understand relationships between objects and are used in many areas like computers, biology, and social studies.

Important Terms in Graphs

• Vertices and Edges
  • Vertices (Nodes): These are the basic points in a graph. ‘One node is called Vertex whereas Multiple nodes are called Vertices.’
  • Edges (Links): These are the lines connecting the points.
• Types of Graphs
  • Undirected Graph: The edges don’t have a direction, meaning the connection works both ways.
  • Directed Graph (Digraph): The edges have a direction, shown by arrows.
  • Weighted Graph: The edges have values or weights, like distance or cost.
  • Simple Graph: There are no loops (lines starting and ending at the same point) or duplicate edges.
  • Complete Graph: Every point is connected to every other point.
  • Bipartite Graph: The points are split into two groups, and lines only connect points from different groups.

Key Features of Graphs

• Degree: The number of edges connected to a point. In a directed graph, we have:
  • In-degree: Edges pointing to a vertex.
  • Out-degree: Edges pointing away from a vertex.
• Path: A way to move from one point to another by following the edges.
• Cycle: A path that starts and ends at the same point.
• Connected Graph: A graph where every point can be reached from any other point.
• Tree: A special type of graph that is connected and has no cycles.