home blog search about
◐

graph

2023-03-14

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

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

  1. if , then is a cycle
  2. a path is simple if no vertex appears in more than once
  3. a cycle is simple if no vertex except for the first one appears in more than once
  4. let be two paths in the graph , the concatenation of is
  1. the graph is connected if between every two vertices there's a path
  2. a graph is acyclic if in there's no cycles
  3. a graph is a tree if it is connected and acyclic