Introduction to graph theory

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
  •   The degree of a vertex in a directed graph is the sum of Indegree and Outdegree.
  •   Path: In a directed graph G = (S, A), a path of length k from a vertex u to a vertex v is a sequence (u0, u1, ..., uk) of vertices such that u = u0, v = uk and (ui-1, ui) belongs to A for all i. A path is elementary if its vertices are all distinct.
  •   Walk: In a directed graph G = (S, A), a Walk (u0, u1, ...., uk) forms a circuit if u0 = uk and if the path contains at least one arc. This circuit is elementary if the vertices u1, ..., uk are distinct. A loop is a circuit of length 1.
  •   Cycle: In the undirected case, a path v0v1, v1v2, ..., vk − 1vk is a cycle if v0 = vk and if an edge does not appear twice with a different orientation. For example v0v1, v1v0 is not a cycle in the non-oriented case. This cycle is elementary if the vertices u1, ..., uk are distinct. A graph without a cycle is said to be acyclic.
  •   Connected graph: An undirected graph is connected if each pair of vertices is connected by a path. The connected components of a graph are the vertex equivalence classes induced by the relation "is accessible from".
  •   Strongly connected graph: A Directed graph is strongly connected if for any pair of vertices x, y there exists a path connecting x to y.
    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

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Comment(s)

To leave a comment you must have an account Sign up, or Sign in