Graph Theory

Vertices

Also known as nodes, they are the fundamental units of graphs that represent entities.

Edges

Connections between vertices in a graph, representing relationships between them.

Directed Graph (Digraph)

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

Undirected Graph

A graph where edges do not have a direction and represent a bidirectional relationship between vertices.

Bipartite Graph

A graph where the vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set.

Eulerian Circuit

A walk in a graph that visits every edge exactly once and returns to the starting vertex.

Hamiltonian Cycle

A cycle in a graph that visits every vertex exactly once and returns to the starting vertex.

Adjacency List

A representation of a graph where each vertex has a list of adjacent vertices, compactly representing sparse graphs.

Adjacency Matrix

A 2D matrix representation of a graph where rows and columns represent vertices, and entries indicate the presence of edges.

Degree of a Vertex

The number of edges incident to a vertex in a graph.

Simple Graph

An undirected graph that has no loops and no more than one edge between any pair of vertices.

m <= n(n-1) /2

Complete Graph

A simple graph in which there is an edge between every pair of distinct vertices.

Path

A walk in a graph where all vertices are distinct.

Circuit

A closed walk with all edges distinct, meaning it begins and ends at the same vertex but does not repeat any edge.

Cycle

A circuit where all vertices are distinct, meaning it starts and ends at the same vertex without repeating any vertex.

Connected Graph

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

Spanning Tree

A subgraph that is a tree and contains all the vertices of the original graph.

Weighted Graph

A graph where edges have weights, often representing costs or distances.

Adjacency

when two vertices share the same edge