Graph Theory Terminology to Know for Discrete Mathematics

Graph theory is a key part of discrete mathematics, focusing on the study of graphs made up of vertices and edges. These structures help model relationships in various fields, making them essential for understanding complex systems and connections.

1. Graph

   • A collection of vertices (nodes) and edges connecting them.
   • Can be directed or undirected, depending on the nature of the edges.
   • Used to model relationships and structures in various fields such as computer science, biology, and social sciences.

2. Vertex (Node)

   • Fundamental unit of a graph representing an entity or point.
   • Can have attributes or properties associated with it.
   • The number of vertices in a graph is denoted as |V|.

3. Edge

   • A connection between two vertices in a graph.
   • Can be directed (one-way) or undirected (two-way).
   • Edges can also have weights, representing costs or distances.

4. Degree of a vertex

   • The number of edges incident to a vertex.
   • In directed graphs, it is divided into in-degree (incoming edges) and out-degree (outgoing edges).
   • Helps in understanding the connectivity and importance of a vertex within the graph.

5. Adjacent vertices

   • Two vertices are adjacent if they are connected by an edge.
   • The concept is crucial for traversing and analyzing graphs.
   • Helps in defining paths and connectivity within the graph.

6. Path

   • A sequence of vertices where each adjacent pair is connected by an edge.
   • Can be simple (no repeated vertices) or contain cycles.
   • Important for determining routes and connections in a graph.

7. Cycle

   • A path that starts and ends at the same vertex without repeating any edges or vertices (except the starting/ending vertex).
   • Indicates a closed loop within the graph.
   • Essential for understanding the structure and properties of graphs.

8. Connected graph

   • A graph in which there is a path between every pair of vertices.
   • In a disconnected graph, at least one pair of vertices lacks a connecting path.
   • Connectivity is a key property in network design and analysis.

9. Tree

   • A special type of connected graph with no cycles.
   • Contains |V| - 1 edges if there are |V| vertices.
   • Used to represent hierarchical structures, such as file systems and organizational charts.

10. Directed graph (Digraph)

    • A graph where edges have a direction, indicated by arrows.
    • Each edge connects an ordered pair of vertices.
    • Useful for representing one-way relationships, such as web links or task dependencies.

11. Weighted graph

    • A graph where edges have weights or costs associated with them.
    • Weights can represent distances, time, or any quantifiable measure.
    • Important for optimization problems, such as finding the shortest path.

12. Complete graph

    • A graph in which every pair of distinct vertices is connected by a unique edge.
    • Denoted as K_n, where n is the number of vertices.
    • Maximizes connectivity and is often used in theoretical studies.

13. Bipartite graph

    • A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
    • Useful for modeling relationships between two different classes of objects.
    • Commonly applied in matching problems and network flows.

14. Planar graph

    • A graph that can be drawn on a plane without any edges crossing.
    • Important in geographical mapping and circuit design.
    • Follows specific properties, such as Euler's formula relating vertices, edges, and faces.

15. Isomorphic graphs

    • Two graphs that can be transformed into each other by renaming vertices.
    • They have the same structure but may differ in appearance.
    • Understanding isomorphism is crucial for graph equivalence and classification.