Graph Theory and Graph Algorithms

A comprehensive set of 80 vocabulary flashcards covering key concepts and terms related to graphs and graph algorithms as outlined in the lecture notes.

Graph

A mathematical construct consisting of vertices and edges.

Vertex

A node in a graph, represented as a point.

Edge

A connection between two vertices in a graph.

Directed Graph

A graph where edges have a direction, indicating the relationship from one vertex to another.

Undirected Graph

A graph where edges do not have a direction.

Adjacency List

A data structure that represents a graph as a list of its adjacent vertices.

Adjacency Matrix

A data structure that represents a graph as a matrix, where each cell indicates if a pair of vertices is connected.

Incidence Matrix

A matrix that shows the relationship between vertices and edges in a graph.

DFS

Depth-First Search, an algorithm for traversing graph structures.

BFS

Breadth-First Search, an algorithm for traversing graph structures.

Graph Traversal

The process of visiting all the vertices and edges of a graph.

Connected Graph

A graph where there is a path between every pair of vertices.

Path

A sequence of edges connecting a series of vertices.

Cycle

A path in a graph that starts and ends at the same vertex.

Articulation Point

A vertex in a graph whose removal increases the number of connected components.

Topological Sorting

An ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before vertex v.

Tree Edge

An edge that is part of the spanning tree created during DFS.

Back Edge

An edge that points from a vertex to one of its ancestors in the depth-first spanning tree.

Forward Edge

An edge that connects a vertex to a descendant in the depth-first spanning tree.

Cross Edge

An edge that connects two vertices in two separate branches of the depth-first spanning tree.

Graph Representation

Different methods to represent graphs, such as matrix or list.

Degree of Vertex

The number of edges connected to a vertex.

Isomorphism

A condition where two graphs contain the same number of graph vertices connected in the same way.

Traverse

To visit all the vertices or points in a graph.

Global Variable

A variable that is accessible from any place in the code.

Visited Array

An array used to keep track of which vertices have been visited during traversal.

Null Pointer

A pointer that does not point to any object or function.

Initialization

The process of assigning an initial value to a variable.

Stack

A data structure that follows the Last In First Out (LIFO) principle.

Queue

A data structure that follows the First In First Out (FIFO) principle.

Depth-first Numbering

The assignment of numbers to vertices in the order they are visited in DFS.

Algorithm

A step-by-step procedure for solving a problem or accomplishing a task.

Complexity

A measure of the resources required for an algorithm, typically time and space.

Space Efficiency

The amount of memory required by an algorithm as a function of input size.

Input/Output

The data that is fed into an algorithm and the data produced by it.

Global Data Structure

A data structure that can be accessed across multiple functions or modules in a program.

Iteration

A process of repeating a sequence of operations.

Vertex count

The number of vertices in a graph.

Edge count

The number of edges in a graph.

Graph Theory

The study of graphs and their properties.

Directed Edge

An edge that has a direction from one vertex to another.

Undirected Edge

An edge that connects two vertices without any specific direction.

Binary Tree

A tree data structure where each node has at most two children.

Spanning Tree

A subgraph that includes all the vertices of the graph with the minimum number of edges.

Planar Graph

A graph that can be embedded in the plane, meaning it can be drawn on a flat surface without edges crossing.

Subgraph

A graph formed from a subset of the vertices and edges of another graph.

DAG (Directed Acyclic Graph)

A directed graph with no cycles.

Connected Component

A maximal connected subgraph in an undirected graph.

Randomized Algorithm

An algorithm that uses random numbers to make decisions during execution.

Graph Isomorphism

When two graphs can be transformed into each other simply by renaming vertices.

Traversal Order

The sequence in which the vertices of a graph are visited.

Data Structure

A systematic way of organizing and accessing data.

Algorithm Complexity

The study of the behavior of algorithms regarding resource usage.

Exponential Growth

Growth where the quantity increases at a rate proportional to its current value.

Polynomial Time

A type of computational complexity indicating an algorithm completes in time proportional to a polynomial expression of the input size.

Breadth-first Tree

A tree formed by performing a BFS on a graph.

Depth-first Tree

A tree formed by performing a DFS on a graph.

Traversal Algorithms

Algorithms designed specifically for traversing graphs.

Backtracking

An algorithmic technique for solving problems incrementally, building candidates and abandoning those that fail to meet the conditions.

Vertex Connectivity

The minimum number of vertices that need to be removed to disconnect the remaining vertices.

Edge Connectivity

The minimum number of edges that must be removed to disconnect a graph.

Graph Algorithm

A set of procedures or formulas for solving problems related to graphs.

Queue Implementation

The way in which a queue is structured and operated in programming.

Recursive Algorithm

An algorithm that solves a problem by solving smaller instances of the same problem.

Iterative Algorithm

An algorithm that repeatedly applies the same operations until a specific condition is met.

Shortest Path Algorithm

An algorithm to find the shortest path from one vertex to another in a graph.