Théorie des graphes - Guide rapide pour les débutants

30 octobre 2021

La théorie des graphes a des applications dans tous ces domaines et est donc très populaire, qu'il s'agisse de mathématiques, d'informatique, de biosciences, de technologie de l'information ou de linguistique.

Il est donc naturel que vous soyez curieux d'en savoir plus sur la théorie des graphes.

Cet article vous apporte un guide de la théorie des graphes pour vous aider à comprendre ses concepts.



La théorie des graphes est définie comme l'étude des graphes ou des structures mathématiques utilisées pour modéliser les relations entre les objets.

Ces modèles mathématiques traitent principalement des arêtes et des sommets et de leurs relations les uns avec les autres.

Table des matières

Structures de données : arbres et graphiques

Nous avons toujours été confus si les arbres et les graphiques sont des structures de données identiques ou différentes.

Hé bien oui. Ce sont presque les mêmes.

Les arbres sont des réseaux ou des graphes ayant des nœuds racines qui se connectent à d'autres nœuds enfants et feuilles et sont toujours définis par un ensemble de règles. Les graphiques n'ont aucune restriction et aucun nœud racine.

Dans les graphes, les nœuds peuvent être connectés de toutes les manières possibles et, contrairement aux arbres, les graphes n'ont pas besoin d'être unidirectionnels.

Un arbre est toujours un graphe ou un réseau, mais un graphe ou un réseau ne sera pas toujours un arbre.

Applications de la théorie des graphes

Les systèmes sociaux, physiques, d'information et biologiques, toutes leurs relations et processus intermédiaires peuvent être modélisés à l'aide de graphiques.

Par exemple, la plupart des étudiants en informatique doivent connaître les termes des réseaux et de la mise en réseau. Les réseaux sont également une sorte de graphe avec des attributs (tels que des routeurs, des systèmes informatiques, etc.) associés à des sommets et des arêtes.

Maintenant que vous connaissez les graphes, laissez-nous vous parler de quelques applications qui vous aideront à accroître votre curiosité et à mieux comprendre la théorie des graphes.

1. Informatique

Les graphiques peuvent représenter des réseaux de communication, des dispositifs de calcul, l'organisation des données, le flux de calcul, etc.

Les problèmes de Média social , la biologie, la cartographie des maladies neurodégénératives, les voyages, la conception de puces informatiques et de nombreux autres domaines utilisent le concept d'arêtes et de nœuds des graphes.

Les informaticiens peuvent utiliser des systèmes de transformation de graphes ou de réseaux pour générer des bases de données de graphes qui permettent des transactions sécurisées, l'interrogation de données structurées en réseau et un stockage persistant.

2. Mathématiques

La géométrie, un concept en mathématiques, utilise le plus les graphiques. La théorie des nœuds, qui fait partie de la topologie, utilise également des graphes.

La théorie des graphes algébriques est appliquée à de nombreux domaines, y compris la complexité et les systèmes dynamiques, et a des liens étroits avec la théorie des groupes.

3. Linguistique

En raison d'une meilleure compatibilité entre le langage naturel et les structures discrètes, la linguistique a trouvé diverses utilisations des méthodes de la théorie des graphes.

Par exemple, la syntaxe et la sémantique compositionnelle, qui sont des approches traditionnelles, suivent des modèles de réseaux ou de graphes arborescents ou hiérarchiques.

La grammaire de structure de phrase dirigée par la tête, une approche contemporaine du langage naturel, est modélisée à l'aide de structures de caractéristiques typées ou de graphes acycliques dirigés.

De nombreuses organisations, telles que TextGraphs, WordNet, VerbNet, etc., sont entrées en jeu en raison de nombreuses utilisations des graphes en linguistique.

4. Sciences sociales

La sociologie utilise la théorie des graphes pour analyser les réseaux sociaux afin d'explorer la diffusion de rumeurs ou de mesurer le prestige des acteurs dans ces réseaux.

D'autres graphiques incluent des graphiques de connaissance, des graphiques d'amitié, des graphiques d'influence, des graphiques de collaboration, etc., qui étudient tous le comportement des gens.

5. Physique et Chimie

Vous seriez surpris de le savoir, mais la théorie des graphes a trouvé sa place dans la physique et la chimie en l'utilisant dans l'étude des réseaux moléculaires.

Il est utilisé en physique pour étudier la physique de la matière condensée et les structures et réseaux atomiques tridimensionnels à l'aide de statistiques de théorie des graphes liées à la topologie des atomes.

La théorie quantique des champs en physique peut être résumée à l'aide de graphes de Feynman et de règles de calcul.

La théorie des graphes a également trouvé son utilité dans les neurosciences computationnelles, représentant les connexions fonctionnelles entre les zones cérébrales liées à divers processus cognitifs.

6. Biologie

La théorie des graphes joue un rôle déterminant dans les efforts de conversation de diverses espèces en biologie dans lesquelles les habitats de certaines espèces sont représentés comme des nœuds et leurs voies de migration comme des bords.

Il est également utile pour modéliser et analyser des ensembles de données avec des relations complexes telles que le regroupement de cellules en types de cellules dans l'analyse du transcriptome unicellulaire.

Les graphes sont également utilisés pour modéliser des gènes ou des protéines et étudier leurs relations, telles que les réseaux de régulation des gènes et les voies métaboliques.

Le système nerveux est un réseau ou un graphe avec des neurones comme sommets et les connexions entre eux comme arêtes.

7. Dans l'ensemble

Vous auriez dû observer les itinéraires ou les réseaux de la ville à un moment donné. Les graphiques peuvent facilement les représenter.

Les informations hiérarchiques de votre arbre généalogique peuvent également être représentées par une structure de données arborescente, un type de modèle mathématique particulier.

Parlons des bases

La théorie des graphes est une partie du concept de graphe ou de réseau qui l'informatique a emprunté parce qu'il a des applications de codage.

Avant d'aller de l'avant avec la théorie des graphes, comprenons quelques concepts de base ou fondamentaux.

1. Pointe

Un point, représenté par un point, est une position définie dans un espace à une, deux ou trois dimensions et est désigné par un alphabet.

Par example,

image 617dd19fd4b92

Ici, 'x' est le point.

2. Sommet

C'est un point de rencontre de plusieurs lignes et est également connu sous le nom de nœud. Un alphabet le désigne.

Par example,

image 617dd19fd4b92

Ici, 'x' est le sommet.

3. Ligne

Une connexion entre deux points s'appelle une ligne.

Par example,

image 617dd1a0271dd

Ici, le lien entre les deux points 'x' et 'y' est appelé une ligne.

4. Bord

Une arête est un chemin ou une ligne qui relie deux sommets, à savoir le sommet de départ et le sommet de fin.

De nombreuses arêtes peuvent être formées ; ainsi, au moins un sommet doit former une arête.

Par example,

image 617dd1a0271dd

Ici, le lien entre le sommet 'x' et 'y' est appelé une arête.

5. Bords parallèles

S'il y a plus d'une arête entre deux sommets, les arêtes sont parallèles.

Par example,

image 617dd1a05b1f7

Dans le graphique ci-dessus, entre les deux sommets 'q' et 'w', il y a deux arêtes, et donc ces arêtes sont appelées arêtes parallèles.

6. Graphique

Un graphe 'g' est un réseau ou un modèle mathématique formé à l'aide d'arêtes et de nœuds.

Il est noté 'G', qui est défini comme G = (V, E) où 'V' est l'ensemble des sommets et 'E' est l'ensemble des arêtes.

Par example,

image 617dd1a0963f8

Le réseau ou le graphe ci-dessus peut être défini à l'aide de ses sommets et de ses arêtes, qui sont :

V= {a, b, c, ré}

E = {ab, bc, cd}

7. Multigraphe

Un graphe ou un réseau qui contient des arêtes parallèles est appelé un multigraphe.

Par example,

image 617dd1a0da296

Le réseau ci-dessus est un multigraphe car il y a deux arêtes entre ses sommets 'b' et 'c'.

8. Boucle

La structure que vous obtenez lorsqu'une arête a le même sommet de début et de fin s'appelle une boucle, c'est-à-dire qu'il s'agit d'un graphe avec une arête tirée du sommet vers lui-même.

Par example,

image 617dd1a11da0a

Le graphe ci-dessus peut être défini en utilisant ses sommets et ses arêtes, qui sont :

V= {a, b, c, ré}

E= {aa, ab, bb, bc, cd, da}

Les boucles sont aux sommets a et b.

9. Adjacence

Les normes d'adjacence sont différentes pour les arêtes et les nœuds d'un graphe ou d'un réseau. Ils sont:

(i) Si une arête est présente entre deux sommets, alors ils sont dits adjacents ou en contiguïté l'un avec l'autre, et cette contiguïté est maintenue par cette seule arête reliant les deux sommets.

(ii) Si un sommet typique est présent entre deux arêtes, alors les arêtes sont dites adjacentes ou en contiguïté, et ce seul sommet présent maintient la contiguïté entre les deux arêtes.

Par example,

image 617dd1a15573a

Dans le graphique ci-dessus, la contiguïté des arêtes et des sommets peut être définie comme :

  1. Les sommets a et b sont adjacents car ils sont reliés par une arête commune ab.
  2. Les sommets c et d sont adjacents car ils sont reliés par une arête commune cd.
  3. Les arêtes ab, ac et ad sont adjacentes car elles sont reliées par un sommet commun a.
  4. Les arêtes bc et cd sont adjacentes car elles sont reliées par un sommet commun c.

Qu'est-ce qu'un graphique ?

Les graphes sont des structures de données ou des réseaux qui ont deux composants principaux : un nœud et une arête.

Nœud: Le sommet d'un graphe ou d'un réseau est appelé nœud N ou sommet V.

Bord: La connexion entre deux nœuds, disons u, v, identifiés comme une paire unique (u, v) est appelée une arête E ou une paire ordonnée. Parfois, les arêtes du graphique peuvent être associées à certaines. Noter- Rappelez-vous toujours que (u, v) et (v, u) ne sont pas identiques et sont donc connus comme des paires ordonnées et sont uniques.

Un graphe g peut être compris comme un réseau ou une représentation picturale d'un ensemble de (V, E), où il y a un ensemble de sommets V et un ensemble d'arêtes E.

Par example:

image 617dd1a1a6cef

Dans ce réseau,

V ou N = {a, b, c, ré, e, f}

E = {ab, bc,

Types de graphique

1. Graphes orientés

Graphes ou réseaux dont les arêtes ont des orientations et sont définies comme une paire ordonnée G = (V, E) où 'V' est un ensemble de sommets et 'E' est l'ensemble d'arêtes constitué de paires ordonnées de sommets.

Par example,

image 617dd1a1e6470

Dans le graphe orienté ci-dessus, nous avons une arête (a, b) et des sommets a et b. Ces nœuds sont connus sous le nom de points finaux, le nœud « a » étant la queue et le nœud « b » étant la tête du bord.

2. Graphe non orienté

Un graphe ou un réseau sans arête de direction définie est dit un graphe non orienté.

Le graphe non orienté G est une paire ordonnée G = (V, E), où E est l'ensemble des paires non ordonnées de sommets.

Par example,

image 617dd1a247a53

Dans une arête ( a , b ), la paire de sommets a et b sont appelées extrémités, l'arête joignant les deux sommets incidents sur eux.

3. Graphique des cycles

Si un graphe simple ou un réseau avec 'n' sommets a 'n' arêtes de longueur 'n', alors un tel réseau est appelé graphe cyclique.

Le nombre de sommets doit être supérieur ou égal à 3 et le degré de sommet doit être égal à deux.

Par example,

image 617dd1a297aa8

Le graphe simple ci-dessus est un graphe cyclique car il a supérieur ou égal à 3 arêtes et le degré de sommet = 2.

4. Graphique acyclique

Un graphe dirigé sans cycle est dit un graphe acyclique dirigé ou DAG. Un réseau sera appelé DAG si un sommet 'v' dans DAG n'aura pas de bord dirigé commençant ou se terminant par 'v'.

Noter: Il peut être à la fois dirigé et non dirigé.

Par example,

image 617dd1a2e1859

Dans la figure ci-dessus, il n'y a pas de cycles, donc le graphique est acyclique ou non cyclique.

5. Graphique cyclique

Contrairement au graphe acyclique, un graphe acyclique est un réseau ayant au moins un cycle.

Par example,

image 617dd1a337ed1

Dans les deux graphiques ci-dessus, les arêtes forment un cycle, ce qui signifie que le réseau est cyclique.

6. Graphique connecté

Lorsqu'il existe un chemin défini entre chaque paire de sommets et qu'aucun nœud n'est inaccessible, le graphe ou le réseau est appelé graphe connexe.

Dans les graphes connectés, il doit y avoir au moins une arête entre deux sommets du réseau.

Par example,

image 617dd1a3c44ae

Le réseau ci-dessus est connecté car tous les sommets sont connectés par des arêtes définies.

7. Graphique déconnecté

Contrairement à un graphe connexe, un réseau ou un graphe déconnecté est formé lorsqu'au moins deux sommets ne sont pas connectés.

Par example,

image 617dd1a414937

Le réseau ci-dessus est un graphe déconnecté puisque deux des sommets ne sont pas connectés.

8. Graphique complet

Dans un graphe complet 'g', chaque nœud 'x' est adjacent à chaque nœud 'y' de sorte qu'il y a une arête présente entre chaque paire de sommets.

Le graphe complet aura ‘n’ sommets mutuels et est noté ‘Kn’.

Par example,

image 617dd1a45c877
Sommets à b c
à Pas connectéLiéLiéLié
b LiéPas connectéLiéLié
c LiéLiéPas connectéLié
LiéLiéLiéPas connecté

Le graphe est complet dans la figure ci-dessus car tous ses sommets sont connectés à d'autres sommets.

9. Graphe biconnecté

Un graphe sans point d'articulation ne peut pas être décomposé davantage en morceaux suivants en supprimant des sommets appelés graphe biconnecté.

Ainsi, les graphes biconnectés ne peuvent pas être déconnectés même si l'un des sommets devait être supprimé.

Par example,

img 617dd1a49daad

Dans le graphique G ci-dessus, nous pouvons voir que même si nous supprimons un sommet du graphique ci-dessus, il sera toujours connecté.

10. Graphique nul

Un graphe sans arête est dit nul.

Par example,

image 617dd1a4db140

Dans la figure ci-dessus, il y a quatre sommets mais aucune arête ne les relie. C'est donc un graphe nul.

11. Graphique trivial

Un graphe composé d'un seul sommet et d'aucune arête est appelé graphe trivial. C'est un point sur un plan.

Par example,

image 617dd1a52f339

Dans la figure ci-dessus, le sommet 'q' désigne un graphe trivial.

12. Graphique simple

Si un graphe n'a pas de boucles ni d'arêtes parallèles, alors un tel graphe est appelé graphe simple.

Pour ces graphes, s'il y a 'n' sommets, il peut y avoir un maximum de nC2 arêtes, et 2^(nC2) graphes possibles, où nC2 = n(n-1)/2.

Par example,

image 617dd1a56abc2

Il y a quatre sommets et trois arêtes dans la figure ci-dessus, et pas de boucles ou d'arêtes parallèles.

Ici, si nous voyons,

Ensuite, selon notre formule de nC2 avec n = 4, nous voyons que le nombre maximum d'arêtes possibles est,

nC2 = n(n-1)/2

= 4(4-1)/2 = 6

De plus, le nombre maximum de graphes possibles avec 4 sommets est,

2^(nC2) = 2^4 = 16

Pourquoi n'essayez-vous pas de créer ces 16 graphiques et de voir si la formule est correcte ?

Ça va être amusant.

13. Graphique régulier

Si tous les sommets du graphe ont le même degré, alors un tel graphe est appelé un graphe régulier.

Le degré du graphe définit son nom, c'est-à-dire un graphe à « k » sommets appelé « graphe k-régulier ».

Par example,

image 617dd1a5b678d

Dans le graphe ci-dessus, tous les sommets ont le même degré = 2 et c'est donc un graphe régulier.

14. Graphique de la roue

Lorsqu'un nouveau sommet, appelé hub, est ajouté à un graphe cycle Cn-1, on obtient un graphe roue, noté Wn.

Ce moyeu est relié à tous les sommets de Cn.

Pour calculer le nombre total d'arêtes dans un graphe de roue, nous avons,

Nombre d'arêtes = nombre d'arêtes allant du hub aux autres sommets + plusieurs arêtes allant de tous les autres nœuds dans un cycle sans hub.

=(n-1) + (n-1)

=2(n-1)

Par example,

image 617dd1a606478

Dans le graphe ci-dessus, un sommet central 'e' est connecté à d'autres sommets du graphe cyclique. Il s'agit donc d'un graphe à roue.

15. Graphique bipartite

Si dans un graphe G = (V, E), chaque arête de l'ensemble E joint un sommet de l'ensemble V1 à un autre sommet de l'ensemble V2, alors le graphe est appelé une partition de sommets de graphe bipartite V = (V1, V2).

Ainsi, nous pouvons dire que dans un graphe biparti, chaque arête rejoint deux sommets d'un ensemble de sommets différent.

Par example,

image 617dd1a65c85b

Dans le graphique ci-dessus, l'arête joint les deux sommets de manière croisée.

16. Graphe biparti complet

Contrairement à un graphe biparti simple, chaque sommet des deux sommets V1 et V2 est relié par une arête dans un graphe biparti complet.

Cependant, rappelez-vous qu'un graphe biparti complet n'est pas un graphe complet et doit être confondu.

Un graphe biparti complet est représenté par K (a, b), où a est le nombre de sommets dans V1 et b est le nombre de sommets dans V2.

Ainsi, on peut conclure que le graphe, K (a, b), a un total d'arêtes 'ab' reliant (a + b) sommets, ce qui peut être rendu similaire à un graphe régulier si, a = b.

Par example,

image 617dd1a6a8f0b

Il y a une arête entre chaque sommet reliant les deux ensembles de sommets entre eux.

17. Graphique en étoile

Noté K (1, n-1) Le graphe en étoile est un cas particulier de graphe biparti où il y a un sommet dans V1 et (n-1) sommets dans V2 ou vice versa.

En d'autres termes, un graphe bipartite complet dans lequel tous les sommets d'un ensemble se connectent à un seul sommet est appelé un graphe en étoile.

Par example,

image 617dd1a71e60a

Dans la figure ci-dessus, tous les sommets convergent ou se rencontrent au même sommet. C'est un graphe en étoile dans lequel le sommet V1 = {a} et V2 = {p, q, r, s} .

18. Complément d'un graphique

Nous savons qu'un graphe est constitué d'arêtes et de sommets (V, E).

Un complément d'un graphe 'G-' est un graphe contenant tous les sommets sous forme de graphe, mais les arêtes ne seront que celles absentes du graphe.

Ainsi, si les arêtes présentes dans l'un ne sont pas similaires à l'autre dans deux graphes, c'est-à-dire que les deux ont le même ensemble et le même alignement de sommets, les deux graphes sont appelés complémentaires.

Un graphe complet peut être formé en fusionnant deux graphes adjacents.

Ainsi,

E (G1) + |E (G2) | = | E (G) |,

Où G1 et G1 sont des graphes complémentaires, et G est le graphe complet.

Par example,

image 617dd1a77e856

Dans les graphiques ci-dessus, nous pouvons voir que le graphique 'I' et le graphique 'II' se complètent car ils n'ont pas les mêmes arêtes mais les mêmes sommets. De plus, lors de la fusion, nous obtenons un graphique complet.

Arbres et forêt

Maintenant que nous avons compris les graphes et leurs types, voyons rapidement les arbres et la forêt et comment ils sont un graphe.

Tout d'abord, nous verrons à propos des arbres.

Arbre

Les arbres sont des graphes acycliques et connectés avec des restrictions. La restriction la plus importante est qu'un nœud enfant ne peut avoir qu'un seul nœud parent.

Comme nous l'avons lu précédemment, un arbre est toujours un graphe, mais un graphe peut ne pas être un arbre.

Les arbres sont des réseaux spéciaux ou des graphes représentant des structures hiérarchiques dans un modèle mathématique et sont classés comme le type le plus simple de graphes avec une structure riche.

Qu'il s'agisse de l'arbre généalogique d'un problème informatique, les arbres se sont avérés très utiles.

Il existe quelques définitions liées aux arbres :

1. Nœud racine : Le nœud ou le sommet le plus élevé d'un arbre est appelé nœud racine. Les arbres commencent leur structure hiérarchique à partir de ce nœud.

2. Nœuds feuilles : Les nœuds sans enfant et qui sont les derniers nœuds d'un arbre sont appelés nœuds feuilles.

3. Nœuds enfants : Les nœuds qui ne sont pas des nœuds racines ou des nœuds feuilles sont appelés nœuds enfants. Ce sont les descendants du nœud racine avec plus de nœuds enfants.

4. Succursales : Les bords de l'arbre reliant différents nœuds sont appelés branches.

Mathématiquement, si un arbre a 'n' nœuds, alors il a 'n-1' arêtes.

Si les arêtes deviennent «n», il devra s'apparier avec deux sommets, donnant lieu à un graphe cyclique, et les arbres ne peuvent jamais être cycliques.

Par example,

image 617dd1a7bec2d

Le réseau ci-dessus est une structure hiérarchique avec des bords acycliques. C'est un arbre.

Noeud principal: à

Nœuds enfants : b, c, ré

Nœuds principaux : E f g h

Branches: un b, bc, bd, ce, cf, dg, dh

Arbres couvrants

Si le sous-graphe d'un graphe connexe forme un arbre, on l'appelle un arbre couvrant.

Pour qu'un sous-graphe soit un arbre couvrant, deux conditions doivent être satisfaites :

(i) Ce devrait être un arbre

(ii) Tous les sommets du graphe doivent être présents.

Par example,

image 617dd1a81a07c

Dans les graphes X et Y ci-dessus, X est un graphe connexe et Y est un sous-graphe de X, qui est un arbre car il n'a pas de cycles. Ainsi, Y est un arbre couvrant.

Rang du circuit

Le nombre d'arêtes qui doivent être supprimées d'un graphe connexe pour obtenir un arbre couvrant est appelé rang de circuit du graphe connexe.

Supposons qu'il y ait des sommets 'v' et des arêtes 'e' dans un graphe connexe 'G' à partir duquel un arbre couvrant de (v-1) arêtes est formé.

Puisqu'un arbre couvrant contient des arêtes 'v-1', nous devons donc garder autant d'arêtes hors de 'e' pour former un arbre couvrant sans cycles.

Ainsi, le rang du circuit du graphe connexe = e – (v-1).

Par example,

Dans l'exemple d'arbre couvrant ci-dessus, le graphe connexe X, a

Nombre d'arêtes = 12

Nombre de sommets = 11

Ainsi, rang du circuit = Nombre d'arêtes - (Nombre de sommets - 1)

= 12 – (11 – 1)

= 2

Par conséquent, l'arbre couvrant que nous avons obtenu, c'est-à-dire le graphique Y est correct.

Théorème de Kirchoff

Si vous avez besoin de trouver le nombre d'arbres couvrants qui peuvent être formés à partir d'un graphe connexe, le théorème de Kirchoff peut être utilisé.

Le théorème, qui est une généralisation de la formule de Cayley, stipule que le nombre d'arbres couvrants d'un graphe connexe peut être calculé en temps polynomial à l'aide de la matrice déterminante laplacienne.

La matrice laplacienne d'un graphe est égale à la différence entre la matrice de degré du graphe et sa matrice d'adjacence.

Par example,

image 617dd1a86a14e

Considérez la figure ci-dessus.

Ici, la matrice L peut être remplie à l'aide de 1 et de 0 en désignant respectivement les arêtes présentes ou absentes dans la matrice, c'est-à-dire si une arête est présente, alors 1, et si elle est absente, alors 0.

L =

0àbc
à0un0un
bun0unun
c0un0un
ununun0

En simplifiant on obtient :

0un0un
un0unun
0un0un
ununun0

En utilisant le théorème de Kirchoff, la diagonale principale de la matrice ci-dessus sera remplacée par le degré des sommets, et les termes de repos seront multipliés par -1.

deux-un0-un
-un3-un-un
0-undeux-un
-un-un-un3

En supprimant la ligne 1 et la colonne 1, nous obtenons,

L=

3-un-un
-undeux-un
-un-un3

Le déterminant de la matrice ci-dessus = 8.

Ainsi, il y aura 8 arbres couvrants possibles.

forêt

Si nous suivons la définition du dictionnaire anglais de la forêt, cela peut être appelé une collection d'arbres.

Il en va de même pour la théorie des graphes.

Un graphe acyclique déconnecté, une collection disjointe de divers arbres, est connu sous le nom de forêt.

Par example,

image 617dd1a8ad958

Si nous regardons les deux graphiques ci-dessus, nous pouvons voir qu'il s'agit de graphiques simples déconnectés ou disjoints sans cycles. C'est donc une forêt.

Degré de sommet

Le nombre total de sommets adjacents à un sommet 'X' est appelé le degré d'un sommet et est noté deg(V) défini comme,

Vous (v)<= n-1 where, v belongs to G.

Puisqu'un sommet peut former des arêtes avec tous les autres sommets d'un graphe sauf lui-même, le degré du sommet peut être au maximum du nombre total de sommets de ce graphe - 1.

Selon le degré de sommets, il existe deux types de sommets :

(i) Sommet pendant

Si le degré d'un sommet est 1, alors on l'appelle un sommet pendant. De tels sommets n'ont qu'une arête les reliant à un autre sommet.

Par example,

image 617dd1a90e857

Le sommet est un sommet pendant dans la figure ci-dessus car il n'y a qu'une arête vers lui. C'est donc un sommet pendant.

(ii) Sommet isolé

Si le degré d'un sommet est 0, alors on l'appelle un sommet isolé. De tels sommets n'ont pas d'arêtes les reliant à d'autres sommets.

Par example,

image 617dd1a949093

Dans la figure ci-dessus, le sommet est isolé car aucune arête n'en part. C'est donc un sommet isolé.

Selon les deux graphiques ci-dessous, le degré de sommet diffère :

(i) Graphe orienté

(ii) Graphe non orienté

1. Degré de Vertex – graphe non orienté

Comprenons cela à l'aide d'un exemple :

Considérez le graphique ci-dessous,

image 617dd1a983475

Dans ce graphe, il y a 5 sommets. Maintenant, le degré pour chaque sommet sera :

degré (a) = 2

degré (b) = 3

degré (c) = 3

degré (d) = 2

degré (e) = 3

2. Degré de sommet – graphe orienté

Un graphe ayant des arêtes dirigées est appelé graphe dirigé. Dans ce graphe, chaque sommet a :

(i) Indegree : Ce sont le nombre d'arêtes venant vers le sommet 'A' et sont notées deg-(A).

(ii) Diplôme supérieur : Ce sont le nombre d'arêtes partant du sommet 'A' et sont notés deg+(A).

Par example,

image 617dd1a9d9519

Considérant le graphe orienté ci-dessous, le

Sommets, V = {a, b, c}

Arêtes, E = {ba, da, cb, cd, db}

Calculons le degré entrant et le degré sortant pour chacun de ses sommets :

  1. Indegree

(i) deg- (a) = 2

(ii) deg- (b) = 2

(iii) deg- (c) = 0

(iv) deg- (d) = 1

  1. Degré supérieur

(i) deg+(a) = 0

(ii) deg+(b) = 1

(iii) deg+(c) = 2

(iv) deg+(d) = 2

La suite de degrés d'un graphe

Si la disposition des degrés de tous les sommets d'un graphe est soit ascendante, soit descendante, alors l'ordre ou la séquence obtenue est appelée la séquence de degrés de ce graphe.

Par example,

image 617dd1aa1ae56

Dans la figure ci-dessus, le

Sommets V = {a, b, c, d}

Edges E = {ab, bc, cd, de, ec, eb, ea}

Le degré de chaque sommet est :

degré (a) = 2

degré (b) = 3

degré (c) = 3

degré (d) = 2

degré (e) = 4

Ainsi, la suite de degrés pour les sommets {a, d, b, c, e} dans l'ordre croissant est : {2, 2, 3, 3, 4}

Et la séquence de degrés pour les sommets {e, b, c, a, d} dans l'ordre décroissant est : {4, 3, 3, 2, 2}

Théorème de la somme des degrés des sommets

Pour un graphe non orienté = (V, E) de sommets V = {V1, V2, …., Vn}, la somme des degrés des sommets sera

n Σ je = 1 degré (Vje) = 2 * | E |

Corollaire 1

Dans un graphe non orienté, il y a même plusieurs sommets de degré impair.

Corollaire 2

Pour un graphe non orienté = (V, E) avec des sommets V = {V1, V2, …., Vn}, la somme des degrés des sommets sera

n Σ je = 1 degré + (Vje) = |E| = n Σ je = 1 degré- (Vje).

Corollaire 3

Dans un graphe non orienté, si le degré de chaque sommet, deg(V)<= k then,

K|V|<= 2|E|

Corollaire 4

Dans un graphe non orienté, si le degré de chaque sommet, deg(V) = k alors,

K|V| = 2 | E |

Corollaire 5

Dans un graphe non orienté, si le degré de chaque sommet, deg(V) >= k alors,

K|V| > = 2 |E |

Coloration

À un moment ou à un autre, nous avons tous utilisé des notes autocollantes colorées pour étiqueter nos notes importantes afin de faciliter la référence et la compréhension.

Nous avons tous dû voir des détectives dans des séries télévisées et des films cartographiant des réseaux de différentes couleurs.

Il en va de même pour la coloration des graphes en théorie des graphes.

La coloration dans les graphiques est un moyen réaliste d'étiqueter divers composants graphiques tels que les arêtes, les régions de contraintes et les sommets dans les réseaux graphiques.

Pour colorer un graphique, diverses contraintes telles qu'un ensemble de couleurs de graphique, la méthode d'attribution des couleurs et l'ordre de coloration, etc., doivent être gardées à l'esprit.

Les sommets de même couleur font partie d'ensembles indépendants.

Un graphique coloré avec un numéro chromatique approprié est appelé un graphique correctement coloré.

Numéro chromatique : En règle générale, deux sommets, arêtes ou régions adjacents ne peuvent pas être colorés avec un nombre minimum de couleurs connu sous le nom de nombre chromatique et est noté C(G).

Il peut être défini comme le nombre minimum possible de couleurs nécessaires pour colorer un graphique.

Pour un graphe sans arêtes, la chromatique sera 1, là où pour les autres, elle sera supérieure ou égale à 2.

Par example,

image 617dd1aa57610

Ici, aucun sommet adjacent n'est de la même couleur. De plus, comme il y a 3 nombres de couleurs utilisées dans le graphique, le nombre chromatique sera : 3

1. Coloration des sommets

L'attribution de couleurs aux sommets d'un graphe de sorte qu'aucun sommet adjacent, c'est-à-dire des sommets avec une arête standard, n'ait la même couleur est appelée coloration des sommets.

2. Coloration de la région

L'attribution de différentes couleurs à différentes régions dans un plan de telle sorte que deux régions adjacentes, c'est-à-dire des régions avec le même bord, n'ont pas la même couleur que la coloration de région.

Par example,

img 617dd1aaaf2ec

Dans le graphique ci-dessous, les régions vertes et bleues sont dites adjacentes car elles ont une arête commune ‘ac’ entre elles.

Ainsi, le graphique peut être coloré comme suit :

image 617dd1ab04008

Applications de la coloration graphique

Étant l'une des applications essentielles de la théorie des graphes, de nombreuses applications temps réel l'utilisent.

Il est principalement utilisé en informatique comme suit :

  • Segmentation des images
  • Planification des processus
  • Regroupement
  • Capture d'images
  • Allocation des ressources
  • Exploration de données
  • La mise en réseau

Connectivité

Pour parcourir un graphe d'un sommet à un autre, le graphe doit être connexe.

Pour décider si un graphe est connexe ou déconnecté, nous devons vérifier sa connectivité, qui est différente pour l'arête et le sommet.

D'après la définition des graphes connectés, nous savons que s'il y a une arête entre chaque sommet d'un graphe, on l'appelle un graphe connexe.

Ainsi, s'il existe un chemin ou un lien pour traverser chaque sommet du graphe, cela s'appelle la connectivité d'un graphe.

D'autre part, un graphe déconnecté s'il y a plusieurs arêtes et sommets déconnectés dans le graphe.

Par example,

image 617dd1ab5271a

Dans le graphique ci-dessus, tous les sommets sont connectés les uns aux autres car il y a une arête entre chaque sommet.

Sommet coupé

Dans un graphe connexe 'G', si l'on supprime ou coupe 'G-V', on obtient un graphe déconnecté, alors ce sommet V appartenant à G est appelé un sommet coupé.

Un graphe à ‘n’ sommets peut avoir un maximum de (n-2) sommets coupés.

Par example,

image 617dd1ab9cdd1

Dans ce graphe, les sommets c et e sont des sommets coupés.

Connectivité vertex

La connectivité des sommets est définie comme le nombre minimum de sommets devant être supprimés pour qu'un graphe connexe soit converti en un graphe déconnecté.

Il est noté K(G), et pour tout graphe connexe G,

K (G) ≤ ƛ (G) ≤ δ (G) ………… (i)

Où,

K(G) = Connectivité vertex

ƛ(G) = Connectivité périphérique

δ(G) = nombre minimum de degré de G

Par example,

image 617dd1abd9244

Dans le graphe g ci-dessus, si nous supprimons les sommets d et c, alors un graphe déconnecté sera formé.

Ici,

δ (G) = 2

La suppression des arêtes ‘ce’ et ‘ad’ donne un graphe déconnecté, donc ƛ(G) = 2

En mettant les valeurs de δ(G) et ƛ(G) dans l'équation (i), nous obtenons,

K(G) ≤ 2 ≤ 2

Ainsi, K(G) = 2

Bord coupé (pont)

Comme un sommet coupé, si à partir d'un graphe connexe, une arête est supprimée de sorte qu'il en résulte un graphe déconnecté, alors ces arêtes sont appelées arêtes coupées.

Pour un graphe connexe ‘G’ ayant ‘v’ sommets,

Il y a au moins un sommet coupé pour chaque arête coupée ; cependant, l'inverse n'est pas valide.

Pour chaque sommet coupé, il peut y avoir ou non une arête coupée qui lui est associée.

Une arête ne peut être une arête coupée que si l'arête fait partie d'un cycle.

Il y a un maximum de bords coupés ‘v-1’ possibles.

Par example,

image 617dd1ac32dff

Dans le graphique ci-dessus, l'arête (c,e) est une arête coupée.

Connectivité périphérique

Le nombre minimum d'arêtes coupées ou le plus petit ensemble de coupes d'un graphe requis pour convertir un graphe connexe en un graphe déconnecté est appelé connectivité des arêtes et est noté ƛ (G).

Par example,

image 617dd1ac9b4f2

Ici, nous pouvons voir que le graphe devient déconnecté si nous supprimons les arêtes 'bc' et 'gf' du graphe. Ainsi, la connectivité des bords sera de 2.

Couper l'ensemble d'un graphique

Si la suppression d'un ensemble d'arêtes E' d'un graphe connexe rend le graphe déconnecté et génère un graphe déconnecté, le sous-ensemble E' formé à partir des arêtes de l'ensemble E est appelé l'ensemble de coupe du graphe.

En d'autres termes, l'ensemble des arêtes supprimées qui convertissent un graphe connexe en un graphe déconnecté est appelé l'ensemble coupé du graphe.

Par example,

image 617dd1ac9b4f2

Dans le graphique ci-dessus, si nous supprimons les arêtes 'bc' et 'gf', nous obtenons un graphique déconnecté.

Ainsi, l'ensemble coupé, E' = {bc, gf}

Ensembles indépendants

Pour qu'un ensemble soit un ensemble indépendant,

(i), il ne devrait pas y avoir d'arêtes adjacentes et de sommet commun entre deux arêtes.

(ii) il ne devrait pas y avoir de sommets adjacents et d'arêtes typiques entre deux sommets.

1. Ensemble de sommets indépendant

Un sous-ensemble 'S' de sommets 'V' dans un graphe 'G' = (V, E) est dit être un ensemble de sommets indépendant s'il n'y a pas d'ensembles adjacents de sommets dans 'S'.

Par example,

image 617dd1acea568

Dans le graphique ci-dessus,

Les sous-ensembles possibles sont :

S1 = {b}

S2 = {b, e}

S3 = {c, f}

S4 = {a, e}

Ici, les sous-ensembles S2, S3 et S4 sont un sommet indépendant car ils contiennent au moins deux sommets du graphe et aucun des sommets n'est adjacent. Le sous-ensemble S1 n'est pas un ensemble de sommets indépendant car il ne contient qu'un seul sommet.

L'ensemble de sommets indépendant maximal

Un ensemble de sommets indépendants est l'ensemble de sommets indépendant maximal d'un graphe 'G' si aucun autre sommet n'est ajouté au sous-ensemble.

Par example,

Dans le graphique ci-dessus, S2, S3 et S4 sont des ensembles de sommets indépendants. Puisqu'il n'est pas possible d'ajouter plus de sommets dans aucun de ces sous-ensembles, il s'agit donc d'ensembles de sommets indépendants maximaux.

L'ensemble de sommets indépendants maximum

Un ensemble de sommets indépendant maximal peut être appelé un ensemble de sommets indépendant complet si l'ensemble maximal contient le nombre maximal de sommets.

Par example,

Dans le graphique ci-dessus, S2, S3 et S4 sont des ensembles de sommets indépendants maximaux et le nombre maximal de sommets dans chaque sous-ensemble est de 2. Ainsi, tous ces sous-ensembles sont des ensembles de sommets indépendants maximaux.

2. Ensemble de lignes indépendant

Un sous-ensemble L d'un graphe est un sous-ensemble de lignes indépendant s'il n'y a pas d'arêtes adjacentes présentes dans L.

Par example,

image 617dd1ad44dfa

Dans le graphique ci-dessus,

Les sous-ensembles possibles sont :

L1 = {a, ré} {e, f} {b, c}

L2 = {a, b} {c, e}

L3 = {a,c}

L4 = {e, f} {a, c}

Ici, les sous-ensembles L1, L2 et L4 sont des ensembles de lignes indépendants car il y a au moins deux arêtes du graphique et aucune des arêtes n'est adjacente. Le sous-ensemble L3 n'est pas un ensemble de droites indépendant car il ne contient qu'une seule arête.

Ensemble de lignes indépendantes maximales

Un ensemble de lignes indépendantes est l'ensemble de lignes indépendant maximal d'un graphe 'G' si aucune autre arête ne peut être ajoutée au sous-ensemble.

Par example,

Dans le graphe ci-dessus, il est possible d'ajouter plus de sommets dans le sous-ensemble L2. Ainsi, les sous-ensembles L1 et L4 sont des ensembles de lignes indépendantes maximales.

Ensemble de lignes indépendantes maximales

Un ensemble de lignes indépendant maximal peut être appelé un ensemble de lignes indépendant complet si l'ensemble maximal contient le nombre maximal d'arêtes.

Par example,

Dans le graphique ci-dessus, les sous-ensembles L1 et L4 sont des sous-ensembles de lignes indépendantes maximales avec un nombre maximal d'arêtes dans L1 = 3 et dans L4 = 2. Ainsi, L1 est l'ensemble de lignes indépendantes maximales.

Revêtements

Un sous-graphe couvrant soit tous les sommets, soit toutes les arêtes d'un graphe est appelé graphe de couverture.

Il peut être de deux types :

(i) Couverture de ligne - Un sous-graphe contenant tous les sommets est appelé une couverture de ligne ou un graphe de couverture des arêtes.

(ii) Vertex Covering - Un sous-graphe contenant toutes les arêtes est appelé un graphe de couverture de sommets.

1. Revêtement de ligne

Un sous-graphe, C(E), d'un graphe G = (V, E) est appelé un graphe linéaire couvrant s'il y a au moins une arête C sur laquelle chaque sommet de G est incident, c'est-à-dire que chaque sommet doit être connecté à un autre sommet par une arête.

Ainsi,

Deg(V) >= un où chaque V appartient à G

Noter: Un graphique avec un sommet isolé n'aura pas de couverture de ligne. Le revêtement linéaire d'un graphe avec des sommets 'x' a au moins [1/2] arêtes.

Par example,

image 617dd1ad9b040

Dans ce graphe, les sous-graphes avec recouvrement de ligne sont :

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, ré}, {a, ré}, {b, c}}

C4 = {{a, ré}, {b, c}}

C5 = {{a, c}, {b, ré}}

Couverture de ligne minimale

Une couverture de ligne minimale d'un graphe est celle dans laquelle aucune autre arête ne peut être supprimée de C (E).

Par example,

Dans le graphique ci-dessus, la ligne couvrant les sous-graphiques est :

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, ré}, {a, ré}, {b, c}}

C4 = {{a, ré}, {b, c}}

C5 = {{a, c}, {b, ré}}

Étant donné que l'arête {d, b} peut être supprimée de C1 et l'arête {c, d} peut être supprimée de C3, ces deux sous-graphes ne sont pas des revêtements de ligne minimaux. Ainsi, C2, C4 et C5 sont des revêtements de ligne minimaux.

Couverture de ligne minimale

Le plus petit revêtement de ligne minimal, ou le revêtement de ligne minimal avec le plus petit ou le nombre minimum d'arêtes, est appelé revêtement de ligne minimal.

‘G’ (α1) est appelé le nombre de recouvrement de ligne, qui est le nombre d’arêtes dans le recouvrement de ligne minimum.

Il y a des points spécifiques à retenir pour un recouvrement minimum des suspentes :

  • Chaque revêtement de ligne peut contenir ou non un revêtement de ligne minimum.
  • Si un revêtement de ligne ne contient pas de chemins de longueur égale ou supérieure à 3, alors ce revêtement de ligne est appelé un revêtement de ligne minimal. En effet, tous les composants de couverture de lignes sont des graphiques en étoile dont aucune arête ne peut être supprimée.
  • Chaque revêtement de ligne contient un revêtement de ligne minimal.
  • Un cycle n'est pas possible avec un revêtement de ligne minimal.

Par example,

Dans l'exemple ci-dessus,

Dans le graphique ci-dessus, la ligne couvrant les sous-graphiques est :

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, ré}, {a, ré}, {b, c}}

C4 = {{a, ré}, {b, c}}

C5 = {{a, c}, {b, ré}}

Comme nous l'avons vu précédemment, C2, C4 et C5 sont des revêtements de ligne minimaux. Dans ce cas, C4 et C5 sont des revêtements de ligne minimum car ils ont le nombre minimum d'arêtes.

2. Recouvrement de vertex

Un graphe couvrant les sommets est un sous-graphe 'R' du graphe G = (V, E) dans lequel chaque arête du graphe est incidente sur un sommet de 'R'.

Par example,

image 617dd1ad9b040

A partir du graphe G ci-dessus, les sous-graphes suivants peuvent être formés :

R1 = {a, c}

R2 = {b, ré}

R3 = {a, ré, b}

R4 = {a, b, c}

Parmi ceux-ci, R1, R2, R3 et R4 sont des sommets couvrant des sous-graphes.

Couverture minimale des sommets

Un revêtement minimal de sommets d'un graphe G est celui dans lequel aucun autre sommet ne peut être supprimé de C(E).

Par example,

Dans le graphe ci-dessus, les sommets couvrant les sous-graphes sont :

R1 = {a, c}

R2 = {b, ré}

R3 = {a, ré, b}

R4 = {a, b, c}

En cela, nous pouvons supprimer le sommet 'b' de R4, donc R4 n'est pas une couverture de sommet minimale. R1, R2 et R3 sont des revêtements de sommets minimaux.

Couverture minimale des sommets

La plus petite couverture minimale de sommets, ou la couverture minimale de sommets avec le plus petit ou le nombre minimal de sommets est appelée couverture minimale de sommets.

‘G’ (α2) est appelé le numéro de couverture de ligne, le nombre de sommets dans la couverture de sommet minimale.

Par example,

Dans l'exemple ci-dessus, la ligne couvrant les sous-graphes est :

R1 = {a, c}

R2 = {b, ré}

R3 = {a, ré, b}

R4 = {a, b, c}

Parmi ces quatre, la ligne minimale couvrant les sous-graphes est R1, R2 et R3. Puisque, R1 et R2 ont le nombre minimum de sommets, ce sont donc des couvertures de sommets minimales.

Propriétés de base

Chaque graphe de la théorie des graphes a quelques propriétés définies pour lui en termes spécifiques utilisés pour les caractériser en fonction de leur structure.

Ces termes spécifiques concernent le domaine de la théorie des graphes et sont communs à tous les graphes.

Distance entre deux sommets

Il peut y avoir plusieurs arêtes entre deux sommets, et donc le chemin le plus court ou la distance entre les deux est appelé la distance entre deux sommets notée d (U, V) où U et V sont des sommets entre lesquels la distance doit être trouvée.

Par example,

image 617dd1add963b

Il existe deux chemins pour atteindre le sommet A à partir du sommet D, mais le chemin le plus court entre eux est ae -> ed. Ainsi, ce chemin sera considéré comme la distance entre ces deux sommets.

L'excentricité d'un sommet

L'excentricité d'un sommet, notée e(v), est définie comme le maximum des distances calculées d'un sommet à tous les autres sommets.

Par example,

image 617dd1ae3c9a8

Dans le graphique ci-dessus, la distance entre « b » et tous les autres sommets est :

Distance de 'b' à 'a' : 1

Distance de 'b' à 'c' : 1

Distance de « b » à « e » : 2

Distance de « b » à « d » : 3

Distance de 'b' à 'f' : 3

Ainsi, l'excentricité du sommet 'b', e(b) vaut 3.

De même, les excentricités pour tous les autres sommets sont :

et (a) = 3

et (c) = 2

et (d) = 3

e (e) = 2

e(f) = 3

Le rayon d'un graphe connexe

Le rayon d'un graphe connexe, noté r(G), est le minimum parmi toutes les excentricités, ou le minimum parmi toutes les distances maximales d'un sommet à tous les autres sommets.

Pour plus de simplification, nous pouvons dire que le minimum parmi toutes les excentricités dans un graphe G est le rayon du graphe G.

Par example,

Dans le réseau ou le graphique ci-dessus, les excentricités des sommets sont :

et (a) = 3

e(b) = 2

et (c) = 2

et (d) = 3

e (e) = 2

e(f) = 3

Ainsi, le rayon du graphique, r(G) = 2 car c'est le minimum parmi toutes les excentricités.

Le diamètre d'un graphique

Contrairement au rayon d'un graphe connexe, le diamètre d'un graphe connexe est l'excentricité maximale parmi toutes les autres excentricités.

Ainsi, si le maximum parmi toutes les distances maximales entre un sommet et tous les autres sommets est noté d(G).

Par example,

Sur la base du réseau ou du graphique ci-dessus, les excentricités des sommets sont :

et (a) = 3

e(b) = 2

et (c) = 2

et (d) = 3

e (e) = 2

e(f) = 3

Ainsi, le diamètre du graphique, d(G) = 3 car c'est le maximum parmi toutes les excentricités.

Point central

Le point central du graphe est le sommet dont l'excentricité est égale au rayon du graphe.

Ainsi, si e(V) = r(V),

alors le sommet V est le centre du graphe G.

Par example,

Sur la base du réseau ou du graphique ci-dessus, les excentricités des sommets sont :

et (a) = 3

e(b) = 2

et (c) = 2

et (d) = 3

e (e) = 2

e(f) = 3

L'excentricité des sommets 'b' et 'e' est égale au rayon du graphe, c'est-à-dire que r(G) = e(b) = e(e) = 2. Ainsi, les sommets 'b' et 'e' sont les points centraux du graphique.

Centre

Le centre du graphe est défini comme l'ensemble des points centraux du graphe G.

Par example,

Sur la base du graphique ci-dessus, le centre du graphique est {b, e}.

Circonférence

Le nombre d'arêtes qui font partie du cycle le plus étendu du graphe G est appelé la circonférence.

Par example,

Sur la base du graphique ci-dessus, les cycles les plus longs sont a-b-c-a ou d-e-f-d. Ainsi la circonférence du graphique est 3.

Circonférence

Contrairement à la circonférence d'un graphe, la circonférence est définie comme le nombre d'arêtes du plus petit cycle du graphe G.

Il peut ou non être le même que la circonférence basée sur le graphique.

Par example,

Sur la base du graphique ci-dessus, les plus petits cycles sont a-b-c-a ou d-e-f-d. Ainsi la circonférence du graphique est 3.

Traversability

La traversée d'un graphe se fait en traçant un chemin entre les sommets sans revenir sur le même chemin.

Dans cet article, nous allons comprendre deux concepts principaux de parcours de graphe :

(i) Chemin d'Euler

(ii) Chemin hamiltonien

1. Chemin d'Euler

S'il existe un chemin d'Euler présent dans les graphes connectés ou orientés 'G', alors un tel réseau est traversable.

Il devrait y avoir exactement une arête de 'G' et au moins un sommet de 'G' dans un chemin d'Euler.

Si le sommet de début et de fin d'un chemin d'Euler est le même, alors un tel chemin est appelé circuit d'Euler.

Par example,

image 617dd1ae7cdf9

Dans le graphique ci-dessus, le chemin d'Euler est : d-a-b-d-c-b

Théorème du circuit d'Euler

Selon le théorème du circuit d'Euler, les graphes connectés peuvent être traversables, ssi (si et seulement si) il y a exactement 2 ou 0 sommets avec un degré impair dans G.

Le graphe peut également contenir le chemin d'Euler et non le circuit d'Euler s'il n'a que deux sommets de degré impair.

Ainsi, pour qu'un graphe ait le circuit d'Euler, il ne devrait pas avoir de sommets de degré impair.

Considérant le graphe ou le réseau utilisé dans le cas ci-dessus, le graphe contient un chemin d'Euler d-a-d-b-c-b. Ce chemin n'est pas un circuit d'Euler car il y a deux sommets de degré impair, c'est-à-dire 'b' et 'd'.

2. Chemin hamiltonien

Avant d'en savoir plus sur le chemin hamiltonien, examinons le graphique hamiltonien.

Un graphe hamiltonien est un graphe connexe G dans lequel il existe un cycle contenant tous les sommets du graphe G.

Dans un graphe hamiltonien, chaque sommet de G n'existe qu'une seule fois, et le chemin formé est appelé chemin hamiltonien.

Le cycle hamiltonien est différent du cycle d'Euler car chaque arête du graphe n'existe qu'une seule fois dans le cycle d'Euler. En revanche, dans le cycle hamiltonien, certaines arêtes du graphique peuvent être ignorées.

Par example,

image 617dd1aebf568

Dans le graphique ci-dessus, nous pouvons dire que :

Le chemin d'Euler existe - Vrai

Le circuit d'Euler existe - Faux

Un cycle hamiltonien existe – Vrai

Un chemin hamiltonien existe – Vrai

Correspondances

Un sous-graphe sans contiguïté d'arête ou sans sommet commun entre deux arêtes est appelé un sous-graphe correspondant.

Mathématiquement, un sous-graphe peut être appelé un sous-graphe correspondant M(G) d'un graphe G = (V, E) si chaque sommet de G est incident sur au plus une arête du sous-graphe M.

Ainsi, deg(V) ≤ 1 pour tout V appartenant à G.

Dans un sous-graphe correspondant, il convient de rappeler que deux arêtes ne peuvent pas être adjacentes car dans un tel cas, le degré du sommet avec les arêtes adjacentes aura le degré deux, ce qui est contraire à la règle de correspondance.

Lors de l'appariement des graphiques,

Si deg(V) = 1, alors le sommet est dit concordant.

Si deg(V) = 0, alors le sommet est dit non concordant.

Par example,

image 617dd1af10cd3

Dans ce graphe G, quatre appariements suivants sans contiguïté et couvrant tous les nœuds c, f, e, d peuvent être formés :

image 617dd1af5ae0d

En utilisant les graphiques et les exemples donnés ci-dessus, vous pouvez essayer de former plus de correspondances de réseaux.

Correspondance maximale

Un sous-graphe d'appariement M dans lequel aucune autre arête ne peut être ajoutée à M est appelé un sous-graphe d'appariement maximal.

Par example,

Sur la base du graphique ci-dessus, M1 et M3 sont les sous-graphes de correspondance maximale.

image 617dd1afc4ef6

Correspondance maximale

Le plus grand sous-graphe d'appariement maximal ou le sous-graphe maximal avec le nombre maximal d'arêtes est appelé le sous-graphe d'appariement maximal.

Le nombre correspondant est défini comme le nombre d'arêtes dans le sous-graphe correspondant maximum.

Par example,

Dans le cas ci-dessus, nous avons M1 et M3 comme sous-graphes de correspondance maximale qui sont également les sous-graphes de correspondance maximale car les deux ont le même nombre d'arêtes.

Correspondance parfaite

Si chaque sommet du sous-graphe a un degré un, c'est-à-dire que chaque sommet du graphe G est incident sur une seule arête, alors le sous-graphe est appelé sous-graphe à correspondance parfaite.

Ainsi, vous (V) = 1 pour tout V.

Noter: Puisqu'aucune arête ne peut être ajoutée dans un sous-graphe à correspondance parfaite, il s'agit également d'un sous-graphe à correspondance maximale. Mais l'inverse n'est pas valable.

Chaque sous-graphe correspondant au maximum peut ou non être un sous-graphe correspondant parfaitement selon le nombre de sommets |V(G)|.

Si le nombre de sommets est pair, alors c'est un sous-graphe correspondant parfaitement.

S'il est impair, alors après avoir mis en correspondance chaque sommet, un seul sommet aura le degré zéro, ce qui est contraire au principe des sous-graphes à correspondance parfaite.

Par example,

En utilisant les graphes formés dans le cas ci-dessus, nous pouvons dire que M1 et M3 sont des sous-graphes parfaitement assortis car chaque nœud a le degré 1.

Isomorphisme

Différentes formes du même graphe avec le même nombre d'arêtes, de sommets et de connectivité d'arêtes sont appelées isomorphisme, et ces graphes sont appelés graphes isomorphes.

Graphiques isomorphes

Si deux graphes G1 et G2 ont le même nombre de composantes et la même connectivité d'arêtes, alors de tels graphes sont appelés graphes isomorphes.

Puisque G1 est similaire à G2 donc,

|V(G1) | = |V(G2) |

E (G1) = |E (G2) |

Ainsi, on peut dire que, dans les graphes isomorphes,

Si les sommets d'un graphe forment un cycle, alors les sommets de l'autre formeront également un cycle.

De plus, les séquences de degrés des deux graphiques seront les mêmes.

Exemple:

image 617dd1b021d4c

Dans ce cas, les graphes non orientés donnés ci-dessus sont isométriques car I1 et I2 ont le même nombre de composants (nœud, arête) et la même connectivité d'arête.

Graphiques planaires

Un graphe dans lequel deux arêtes ne se croisent pas à des points autres que des sommets peut être dessiné sur un plan ou une sphère appelés graphes planaires.

Par example,

Graphique 1 :

image 617dd1b06efd5

Graphique 2 :

image 617dd1b0adb2f

Dans les graphiques ci-dessus, le graphique 1 est non plan et le graphique 2 est plan. C'est parce qu'il n'a pas d'arêtes qui ne se croisent pas.

Régions

Les zones connexes formées par un graphe planaire sont appelées régions.

Par example,

La théorie des graphes

Degré de régions

Le degré d'une région bornée ou non bornée est spécifié par le nombre d'arêtes qui entourent la région. Il est donné par,

r = deg(r) = Nombre d'arêtes entourant r.

Par example,

Dans l'exemple ci-dessus, le degré de chaque région est :

deg (Région 1) = 3

deg (Région 2) = 7

deg (région 3) = 3

Somme des degrés des régions

Pour un graphe planaire de 'n' sommets, la somme des degrés de tous les sommets est donnée par,

n Σ je = 1 degré (Vi) = 2 |E |

Le théorème de la somme des degrés de régions stipule qu'un graphe planaire contenant «n» régions aura une somme de degrés de régions comme,

n Σ je = 1 degré (Ri) = 2 |E |

Ainsi, on peut conclure que :

1. Si D est le degré de chaque région, alors la somme des degrés des régions sera :

D|r| = 2|E|

2. Si le degré de chaque région ‘r’ est au moins D, alors la somme des degrés des régions sera :

D|r| ≤ 2|E|

3. Si le degré de chaque région ‘r’ est au plus D, alors la somme des degrés des régions sera :

D|r| ≥ 2|E|

Maintenant, en supposant que toutes les régions ont le même degré et en appliquant les formules d'Euler sur les graphes planaires avec |V| nombre de sommets, |R| nombre de régions, et |E| nombre d'arêtes que nous avons,

(i) |V| + |R| = |E| + 2 si le graphe G est connexe planaire.

(ii) |V| + |R| = |E| + (K+1) s'il s'agit d'un graphe planaire à 'K' composantes.

Homomorphisme

En divisant certaines arêtes de G par un ou plusieurs sommets, si nous pouvons obtenir plus de graphes tels que G1 et G2, ces graphes sont appelés graphes homomorphes.

Homomorphisme et isomorphisme

Si un graphe G1 est isomorphe à un autre graphe G2, alors on peut dire que le graphe G2 est homomorphe au graphe original G. Cependant, on ne peut pas en dire autant de l'inverse.

Graphe polyédrique

Si chaque sommet d'un graphe planaire connexe simple est supérieur ou égal à 3, alors un tel graphe est appelé graphe polyédrique.

Ainsi, deg(V) ≥ 3 pour tout V appartenant à G.

Découvrez notre Guide de l'interface homme-machine ce qui conviendra aux débutants.

Questions fréquemment posées