## Introduction to graph theory

A graph is an object composed of **vertices** (or **nodes**) and **edges** (or **arcs**, in some cases) that connect the vertices. We can see a graph like a geographic map: the vertices are then **cities** and the edges are the **roads** that lead from one city to another.

There are two types of graphs:

**Directed graph:**relationships are oriented and we speak of an arc. An arc is represented by a couple of ordered vertices( Or nodes).**Undirected graph:**relationships are not oriented and we therefore speak of edges. An edge is represented by a pair of unordered vertices.

#### Vocabulary

**A loop**is an arc that connects a vertex to itself. In an undirected graph, loops are prohibited and each edge is therefore made up of two distinct vertices.**Degree of a vertex**: In an undirected graph, the degree of a vertex is the number of edges which are incident to it.**Indegree of a vertex**: In a directed graph, the Indegree of a vertex is the number of arcs leaving it,**Outdegree of a vertex**: In a directed graph, the Outdegree of a vertex is the number of incoming arcs**Path:**In a directed graph G = (S, A), a path of length k from a vertex u to a vertex v is a sequence (u_{0}, u_{1}, ..., u_{k}) of vertices such that**u = u**and (_{0}, v = u_{k}**u**_{i-1}, u_{i}) belongs to A for all**i.**A path is elementary if its vertices are all distinct.**Notes !**The definition implies that if x and y are two vertices of a strongly connected graph, then there is a path from x to y and a path from y to x.

#### Share this course with your friends :

**This course is written by M. ESSADDOUKI Mostafa**

## 0 Comment(s)