Introduction to Graphs

Types of Graphs

1. Undirected Graph

   • No arrows on edges.
   • Edges can be traversed in both directions between nodes.
   • Edge between two nodes (U, V) allows travel both U to V and V to U.

2. Directed Graph

   • Edges have arrows, indicating a direction.
   • Travel is possible only in the direction of the arrows.
   • Can have bi-directional edges with two distinct directed edges between the same nodes.

Graph Terminology

• Node/Vertex:
  • Represented by circles in a graph.
  • Identified typically by numbers (Node 1, Node 2, etc.).
  • No specific order required for numbering.
• Edge:
  • Line connecting two nodes.
  • In undirected graphs, can be traversed in either direction.
  • In directed graphs, the direction is specified by an arrow.

Cycles in Graphs

• Cycle:
  • Path starting and ending at the same node.
  • A graph with a cycle is called a Cyclic Graph.
  • Acyclic Graph: Contains no cycles.
  • Directed Acyclic Graph (DAG): A directed graph with no cycles.

Paths in Graphs

• Path:
  • Sequence of nodes in which each adjacent pair is connected by an edge.
  • No node appears more than once within a path.
  • Nodes must be reachable from one another.

Degrees in Graphs

• Degree (Undirected Graph):

  • Number of edges attached to a node.
  • Property: Total degree of graph = 2 x number of edges.

• In-Degree (Directed Graph):

  • Number of edges coming into a node.

• Out-Degree (Directed Graph):

  • Number of edges going out from a node.

Edge Weights

• Edge Weight:
  • Numerical value assigned to an edge.
  • If unspecified, assume unit weight of 1.

Summary

• Graphs can be undirected or directed and can contain cycles.
• Paths must not repeat nodes and all nodes must be reachable.
• Understanding in-degrees and out-degrees is crucial for directed graphs.
• Weights may be assigned to edges, influencing traversal and algorithms.