Graph Theory and Algorithms

These flashcards cover key vocabulary terms and concepts related to graph theory and algorithms, including definitions and explanations relevant to the lecture material.

Counting Sort

An algorithm that sorts a collection of objects according to keys that are small integers.

Expectation E[X]

The expected value of a discrete random variable, calculated as the sum of each possible value multiplied by its probability.

Hitting Time

The expected number of trials needed to achieve the first success in a sequence of independent Bernoulli trials.

Undirected Graph

A graph in which edges have no direction, meaning the connection between two nodes is bidirectional.

Directed Graph

A graph where edges have a direction, going from one node to another.

BFS (Breadth First Search)

A traversal algorithm that explores nodes layer by layer from the starting node.

DFS (Depth First Search)

A traversal algorithm that explores nodes by following edges from the most recently discovered node until reaching a dead-end.

Connected Graph

A graph in which there is a path between every pair of nodes.

Bipartite Graph

An undirected graph that can be colored with two colors such that no two adjacent vertices share the same color.

Topological Sort

A linear ordering of vertices in a directed acyclic graph, where for every directed edge UV from vertex U to vertex V, U comes before V in the ordering.

DAG (Directed Acyclic Graph)

A directed graph that has no directed cycles, meaning there is no way to start at any vertex v and follow a consistently directed path that eventually loops back to v again.

Adjacency Matrix

A square matrix used to represent a finite graph, where the elements indicate whether pairs of vertices are adjacent.

Adjacency List

A collection of lists used to represent a graph, where each list corresponds to a vertex and contains the neighboring vertices.

Cycle in a Graph

A path in a graph where the starting and ending node are the same and consists of at least one edge.

Tree

A connected undirected graph with no cycles.

Rooted Tree

A tree in which one vertex has been designated as the root, and all edges point away from the root.

Phylogenetic Tree

A branching diagram that represents the evolutionary relationships among various biological species.

Heuristic

A problem-solving approach that utilizes a practical method not guaranteed to be optimal.