Théorie des graphes - Fondamentaux

Un graphique est un diagramme de points et de lignes connectés aux points. Il a au moins une ligne joignant un ensemble de deux sommets sans aucun sommet se connectant. Le concept de graphes en théorie des graphes repose sur certains termes de base tels que point, ligne, sommet, arête, degré de sommets, propriétés des graphes, etc. Ici, dans ce chapitre, nous allons couvrir ces principes fondamentaux de la théorie des graphes.

Point

A pointest une position particulière dans un espace unidimensionnel, bidimensionnel ou tridimensionnel. Pour une meilleure compréhension, un point peut être désigné par un alphabet. Il peut être représenté par un point.

Exemple

Ici, le point est un point nommé «a».

Ligne

UNE Lineest une connexion entre deux points. Il peut être représenté par une ligne continue.

Example

Ici, «a» et «b» sont les points. Le lien entre ces deux points s'appelle une ligne.

Sommet

Un sommet est un point de rencontre de plusieurs lignes. Il est également appelé unnode. Semblable aux points, un sommet est également désigné par un alphabet.

Example

Ici, le sommet est nommé avec un alphabet «a».

Bord

Une arête est le terme mathématique pour une ligne qui relie deux sommets. De nombreuses arêtes peuvent être formées à partir d'un seul sommet. Sans sommet, une arête ne peut pas être formée. Il doit y avoir un sommet de départ et un sommet de fin pour une arête.

Example

Ici, «a» et «b» sont les deux sommets et le lien entre eux est appelé une arête.

Graphique

Un graphe «G» est défini comme G = (V, E) où V est un ensemble de tous les sommets et E est un ensemble de toutes les arêtes du graphe.

Example 1

Dans l'exemple ci-dessus, ab, ac, cd et bd sont les arêtes du graphique. De même, a, b, c et d sont les sommets du graphe.

Example 2

Dans ce graphique, il y a quatre sommets a, b, c et d, et quatre arêtes ab, ac, ad et cd.

Boucle

Dans un graphe, si une arête est dessinée du sommet vers elle-même, on l'appelle une boucle.

Example 1

Dans le graphe ci-dessus, V est un sommet pour lequel il a une arête (V, V) formant une boucle.

Example 2

Dans ce graphique, il y a deux boucles qui sont formées au sommet a et au sommet b.

Degré de sommet

C'est le nombre de sommets adjacents à un sommet V.

Notation - deg (V).

Dans un graphe simple avec n nombre de sommets, le degré de tous les sommets est -

deg (v) ≤ n - 1 ∀ v ∈ G

Un sommet peut former une arête avec tous les autres sommets sauf par lui-même. Ainsi, le degré d'un sommet sera à la hauteurnumber of vertices in the graph minus 1. Ce 1 est pour l'auto-sommet car il ne peut pas former une boucle par lui-même. S'il y a une boucle à l'un des sommets, alors ce n'est pas un graphique simple.

Le degré de sommet peut être considéré sous deux cas de graphes -

  • Graphique non dirigé

  • Graphique dirigé

Degré de sommet dans un graphe non dirigé

Un graphe non orienté n'a pas d'arêtes dirigées. Considérez les exemples suivants.

Example 1

Jetez un œil au graphique suivant -

Dans le graphique non dirigé ci-dessus,

  • deg (a) = 2, car il y a 2 arêtes se rencontrant au sommet 'a'.

  • deg (b) = 3, car il y a 3 arêtes se rencontrant au sommet 'b'.

  • deg (c) = 1, car il y a 1 arête formée au sommet 'c'

  • Donc 'c' est un pendent vertex.

  • deg (d) = 2, car il y a 2 arêtes se rencontrant au sommet 'd'.

  • deg (e) = 0, car il y a 0 arêtes formées au sommet 'e'.

  • Donc 'e' est un isolated vertex.

Example 2

Jetez un œil au graphique suivant -

Dans le graphique ci-dessus,

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 et deg (e) = 0.

Le sommet 'e' est un sommet isolé. Le graphe n'a pas de sommet pendant.

Degré de sommet dans un graphe orienté

Dans un graphe orienté, chaque sommet a un indegree Et un outdegree.

Indegree d'un graphique

  • L'Indegree du sommet V est le nombre d'arêtes qui entrent dans le sommet V.

  • Notation - deg− (V).

Au-delà d'un graphique

  • Le degré extérieur du sommet V est le nombre d'arêtes qui sortent du sommet V.

  • Notation - deg + (V).

Considérez les exemples suivants.

Example 1

Jetez un œil au graphique orienté suivant. Le sommet «a» a deux arêtes, «ad» et «ab», qui vont vers l'extérieur. D'où son degré extérieur est 2. De même, il y a une arête «ga», venant vers le sommet «a». Par conséquent, l'indegree de «a» est 1.

Les degrés indegree et outdegree des autres sommets sont indiqués dans le tableau suivant -

Sommet Indegree Outdegree
une 1 2
b 2 0
c 2 1
ré 1 1
e 1 1
F 1 1
g 0 2

Example 2

Jetez un œil au graphique orienté suivant. Le sommet 'a' a une arête 'ae' partant du sommet 'a'. D'où son degré extérieur est 1. De même, le graphe a une arête «ba» venant vers le sommet «a». Ainsi l'indegree de «a» est 1.

Les degrés indegree et outdegree des autres sommets sont indiqués dans le tableau suivant -

Sommet Indegree Outdegree
une 1 1
b 0 2
c 2 0
ré 1 1
e 1 1

Sommet suspendu

En utilisant le degré d'un sommet, nous avons deux types spéciaux de sommets. Un sommet de degré un est appelé un sommet pendant.

Example

Ici, dans cet exemple, le sommet 'a' et le sommet 'b' ont une arête connectée 'ab'. Donc en ce qui concerne le sommet 'a', il n'y a qu'un seul bord vers le sommet 'b' et de même par rapport au sommet 'b', il n'y a qu'un seul bord vers le sommet 'a'. Enfin, le sommet «a» et le sommet «b» ont un degré qui est également appelé sommet pendant.

Sommet isolé

Un sommet de degré zéro est appelé un sommet isolé.

Example

Ici, le sommet «a» et le sommet «b» n'ont pas de connectivité entre eux et avec tous les autres sommets. Ainsi, le degré des deux sommets «a» et «b» est nul. Ceux-ci sont également appelés sommets isolés.

Proximité

Voici les normes de contiguïté -

  • Dans un graphe, on dit que deux sommets sont adjacent, s'il y a une arête entre les deux sommets. Ici, la contiguïté des sommets est maintenue par l'arête unique qui relie ces deux sommets.

  • Dans un graphique, on dit que deux arêtes sont adjacentes, s'il existe un sommet commun entre les deux arêtes. Ici, la contiguïté des arêtes est maintenue par le sommet unique qui relie deux arêtes.

Example 1

Dans le graphique ci-dessus -

  • «a» et «b» sont les sommets adjacents, car il existe une arête commune «ab» entre eux.

  • 'a' et 'd' sont les sommets adjacents, car il existe une arête commune 'ad' entre eux.

  • ab 'et' be 'sont les arêtes adjacentes, car il y a un sommet commun' b 'entre elles.

  • be 'et' de 'sont les arêtes adjacentes, car il y a un sommet commun' e 'entre elles.

Example 2

Dans le graphique ci-dessus -

  • 'a' et 'd' sont les sommets adjacents, car il existe une arête commune 'ad' entre eux.

  • «c» et «b» sont les sommets adjacents, car il existe une arête commune «cb» entre eux.

  • «ad» et «cd» sont les arêtes adjacentes, car il y a un sommet commun «d» entre elles.

  • «ac» et «cd» sont les arêtes adjacentes, car il y a un sommet commun «c» entre elles.

Bords parallèles

Dans un graphe, si une paire de sommets est connectée par plusieurs arêtes, ces arêtes sont appelées arêtes parallèles.

Dans le graphique ci-dessus, «a» et «b» sont les deux sommets qui sont reliés par deux arêtes «ab» et «ab» entre elles. On l'appelle donc comme une arête parallèle.

Multi-graphique

Un graphe ayant des arêtes parallèles est appelé Multigraph.

Example 1

Dans le graphique ci-dessus, il y a cinq arêtes «ab», «ac», «cd», «cd» et «bd». Puisque 'c' et 'd' ont deux arêtes parallèles entre eux, c'est un Multigraph.

Example 2

Dans le graphique ci-dessus, les sommets «b» et «c» ont deux arêtes. Les sommets «e» et «d» ont également deux arêtes entre eux. C'est donc un Multigraph.

Séquence de degrés d'un graphique

Si les degrés de tous les sommets d'un graphique sont disposés par ordre décroissant ou croissant, la séquence obtenue est appelée séquence de degrés du graphique.

Example 1

Sommet UNE b c ré e
Connexion à avant JC un d un d c, b, e ré
Diplôme 2 2 2 3 1

Dans le graphique ci-dessus, pour les sommets {d, a, b, c, e}, la séquence de degrés est {3, 2, 2, 2, 1}.

Example 2

Sommet UNE b c ré e F
Connexion à être a, c b, d c, e un d -
Diplôme 2 2 2 2 2 0

Dans le graphique ci-dessus, pour les sommets {a, b, c, d, e, f}, la séquence de degrés est {2, 2, 2, 2, 2, 0}.