- Perfect graphs
- Amalgamation of graphs
- Regular graph
- Cage
- Bipartite graph
- Cayley's graph
- Click
- Complementary graph
- Bruijin graph
- Graph density (Dense graphs and Hollow graphs)
- Interval graph
- Circle graph
- Line graph
- Petersen graph
- Planar graph
- Random graph
- Scale-invariant graph
- Cordal or split graph
- Trellis

Contents

Toggle## Graph theory

In graph theory, a graph **G** is defined by a couple (S, A) with **S** a finite set of vertices, and **TO** a finite set of pair of vertices (s_{i}, s_{j}) in S².

In a directed graph, the pairs (s_{i}, s_{j}) of **TO** are oriented, that is, s_{i} is the initial vertex and s_{j} the terminal vertex. Graphically, this couple is a **bow **from the top s_{i} towards the top s_{j}.

In an undirected graph, the pairs (s_{i}, s_{j}) are not oriented. Thus, (s_{i}, s_{j}) is equivalent to writing (s_{j}, s_{i}). Graphically, this couple is a **fish bone** between vertices s_{i} and s_{j}.

Elements of terminology:

- THE'
**order**of a graph is the number of its vertices |S|. - A
**loop**is an arc or an edge (s_{i}, s_{i}). - An undirected graph is said
**simple**if it does not contain a loop and if it has at most one edge between any pair of vertices. Otherwise it is a multi-graph. - A directed graph is said
**elementary**if it does not contain a loop. - A directed graph is a
**p-graph**if it has at most*p*arcs between any pair of vertices. - A graph
**partiel**of a graph is the graph obtained by deleting certain arcs (or edges). - a
**subgraph**of a graph is the graph obtained by deleting certain vertices and all incident arcs at the deleted vertices. - A graph is said
**full**if it has an edge (s_{i}, s_{j}) for any pair of vertices (or two arcs (s_{i}, s_{j}) and (s_{j}, s_{i})). A complete simple graph with n vertices will have n (n-1) / 2 edges. - a
**attribute**can be associated with (s_{i}, s_{j}). The attribute can be a letter, a word or a weight (numerical value). A graph with weights is called**Network**.

Consider a graph G = (V, E, w) with a weight function:

Concepts of adjacency:

- In an undirected graph, a vertex s
_{i}is said**adjacent**at a summit s_{j}if there is an edge between s_{i}and s_{j}. The set of vertices adjacent to a vertex s_{i}is defined by:

- In a directed graph, we distinguish the vertices
**successors**(terminals of an arc) and**predecessors**(initials of an arc):

Notions of degree of a vertex:

- In an undirected graph, the
**degree**of a vertex is the number of edges incident to this vertex. In the case of a simple graph we have:

- In a directed graph, the
**external half-degree**from a vertex is the number of arcs starting from this vertex. In a 1-graph we have:

- In a directed graph, the
**interior half degree**from a vertex is the number of arcs coming from this vertex. In a 1-graph we have:

- The number of vertices of odd degree is even. The sum of all degrees is twice the number of edges. Since the sum of degrees is even and the sum of degrees of vertices with even degree is even, the sum of degrees of vertices with odd degree must be even. If the sum of degrees of vertices with odd degree is even, there must be an even number of such vertices.

## Computer representation

There are two “academic” ways of representing a graph in a computer way: either by an adjacency matrix, or by adjacency lists.

We assume that the vertices of S are numbered from 1 to **not**. The adjacency matrix is a matrix **M** of size n * n such that M [i, j] = **value** if (i, j) in A, M [i, j] = **no value** otherwise. Within the framework of the presence of link between the vertex i and j, **value** = 1 and **no value** = 0. Within the framework of link valued between the vertex i and j, **value** = weighting and **no value** = infinite. In a non-oriented frame, the matrix will be symmetrical with the upper right triangle. This type of coding requires O (| S | ²) memory locations.

The representation by adjacency lists consists of an array **T** of **not** lists, one for each vertex of **S**. A linked list T [s_{i}] contains all the elements_{j} of **S** such that there is a link (s_{i}, s_{j}) in **TO**. That is, the list of successors of s_{i}. If the graph is valued, each link can contain information on the weighting. This type of encoding requires O (| S | + | A |) memory locations.

Each method has advantages and disadvantages depending on the operations that you want to perform on the graph.

## Pathways

**u**towards a summit

**v**is a sequence <s

_{0}, s

_{1}, … , s

_{k}> vertices such that u = s

_{0}and v = s

_{k}, and (s

_{i}, s

_{(i + 1)}) is in

**TO**for

**i**from 0 to k-1. The length of the path is the number of arcs in the path, i.e.

**k**. If there is a path

**u**To

**v**, we will say that

**v**is accessible from

**u**. A path is elementary if the vertices it contains are all distinct. u is called Start, v is called End.

_{0}= s

_{k}and if the path has at least one arc. This circuit is elementary if the path <s

_{0}, …, s

_{(k-1)}> (the circuit without the last vertex) is elementary. A loop is therefore a circuit of length 1. The graph is said to be acyclic if it has no circuit.

This can be calculated by transitive closure. The latter is the sum of **not** first powers of the adjacency matrix, n=|A|. The graph is strongly connected if the whole matrix has **value**. A strongly connected component is a strongly connected subgraph.

The same notions exist for undirected graphs under the name of chain and cycle. The graph is said to be connected and we speak of a connected component.