What is a weighted graph?

A weighted graph is a graph where each edge is assigned a numerical value called a weight. The weight represents the cost, distance, or some other attribute of the relationship between the two vertices connected by the edge.

What is a path in a graph?

A path in a graph is a sequence of vertices connected by edges. A path may visit a vertex multiple times, but it cannot use the same edge twice in a row.

What is a cycle in a graph?

A cycle in a graph is a path that starts and ends at the same vertex, and visits at least one other vertex in between.

What is a connected graph?

A connected graph is a graph where there is a path between any two vertices in the graph.

What is a spanning tree?

A spanning tree is a tree that includes all the vertices of a graph and a subset of the edges that form a tree (no cycles) and connect all the vertices.

What is a minimum spanning tree?

A minimum spanning tree is a spanning tree that has the smallest possible sum of edge weights. It is used to find the most efficient way to connect all the vertices in a weighted graph.

What is a directed acyclic graph (DAG)?

A directed acyclic graph (DAG) is a directed graph that does not contain any directed cycles. DAGs are commonly used in many applications, including task scheduling, gene expression analysis, and data flow analysis.

What is a topological sort?

A topological sort is an ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. Topological sorting is used to solve many problems related to scheduling, dependency resolution, and orderings.

What is a bipartite graph?

A bipartite graph is a graph where the vertices can be divided into two disjoint sets, such that all edges connect vertices in different sets. Bipartite graphs have many applications, including matching problems, circuit design, and resource allocation.

What is a clique in a graph?

A clique in a graph is a subset of vertices where every vertex is connected to every other vertex in the subset. Cliques are used in many applications, including social network analysis, genetics, and information retrieval.