a graph is an ordered pair , where is a set whose elements are called vertices, and is a set of paired vertices, whose elements are called edges
consider the graph
a simple graph is a complete graph if for each two vertices we have .
a simple graph is an undirected graph with no parallel edges and no loops.
in a directed graph, the outdegree of a vertex is the number of the edges whose tail is connected to the vertex and the indegree is the number of edges whose head is connected to the vertex
an acyclic graph is a graph that contains no cycles.
an undirected graph is connected if between every two vertices there's a path.
a graph is called connected if it is non-empty and any two of its vertices are linked by a path in . if and is connected, we also call itself connected (in ). instead of 'not connected' we usually say 'disconnected'.
usually a graph is stored in computer memory using an adjacency list, this is the assumption here.
consider the following algorithm which receives an undirected graph and returns a list of its edges
the time complexity of this algorithm is
the maximum number of edges in a simple undirected graph is
in a complete graph, the rank of each vertex is , and it follows trivially that the sum of ranks is , and since each vertex touches 2 edges, the number of edges is .
let be a path in a graph
- if , then is a cycle
- a path is simple if no vertex appears in more than once
- a cycle is simple if no vertex except for the first one appears in more than once
- let be two paths in the graph , the concatenation of is