Types de graphes

Sous graphes

Graphe simple : ce sont des graphes qui n’ont pas ni nœuds, ni arêtes parallèles. Donc chaque pareil de sommets est uni seulement par une arête. Il n’a pas de boucles non plus. Ce type de graphe est défini comme un pareil G= (V, E), qu’il a un ensemble de sommets V et un ensemble E de connexions entre les sommets. Dans ce cas : V= [A,B,C,D] et E= [AB,AC,AD,BD,DC]

Graphe no simple ou multi graphe : ce sont des graphes avec des nœuds et arêtes parallèles. Presque toujours les pareils de sommets ont plus d’une arête qui les connecte, alors deux arêtes peuvent connecter les mêmes deux sommets. Dans ce cas: V= [A,B,C,D,E] et E= [AA,AC,AC,AE,CB,CE,BD,BD,BE,DE]. Comme on peut apprécier dans le groupe d'arêtes, il y en a quelques qui se repentent.

Graphe acyclique : ce sont des graphes qui n’ont pas de cycles. Un cycle est un graphe avec le même nombre d’arêtes que de sommets, donc deux sommets sont adjacents seulement s’ils sont consécutifs dans le graphe. Comme on peut le voir, ce graphe n'a aucun cycle bien que le sommet D n’est pas connecté ni avec le sommet C ni le B, et non plus les sommets C et B entre eux. En plus le nombre d'arêtes c’est #E=3 et le nombre de sommets est #V=4, donc ils sont différents et alors le graphe n’a pas un cycle.

Graphe cyclique : ce sont des graphes avec des cycles. Cela veut dire que le graphe a un cycle avec qui passe pour toutes les arêtes une seule fois et dans lequel coïncident le sommet initial et le final. Dans ce graphe on trouve un cycle lequel est composé par V= (B,A,C,D,B) et E=(BA,AC,CD,DB).

Graphe dirigé : ce sont des graphes auxquels les arêtes ont une direction concrète. Elles sortent d’un sommet pour y aller dans un autre avec un ordre qui est toujours le même. Les arêtes sont des flèches. On appelle origine au premier sommet d’une arête et fin au deuxième. Un même graphe peut alors avoir des arêtes différentes si on change les directives.

Dans le cas du graphe A l’ensemble d'arêtes c’est→ E=[AC,AB,BC]. En revanche, dans le cas B, E=[AC,CB,BA].

Graphe non dirigé : ce sont des graphes auxquels les côtés ne sont pas orientés, alors les arêtes n’ont pas une direction et ne sont pas des flèches, sinon des segments qui unissent deux points. Si on reprend le graphe antérieur et on le transforme dans un graphe non dirigé on peut considérer les arêtes de différentes façons bien que l'arête qui connecte A et B peut être AB ou BA indifféremment. Donc, E=[AC,CB,BA] et aussi E=[AB,BC,CA].

Graphe connexe : ce sont des graphes auxquels on peut suivre un chemin des n’importe quel sommet pour y arriver à un autre. C’est-à-dire, chaque pareil de sommets A, B a un chemin qui passe par un nombre sans importance de sommets pour arriver à l’autre extrême. Le graphe à côté a tous ses sommets connectés entre eux, donc on a des chemins qui unissent tous ses sommets. Alors comme il est connexe on peut tracer un chemin de n’importe quel sommet pour arriver à un autre.

Graphe dense : ce sont des graphes auxquels le numéro d’arêtes est proche au numéro maximal d’arêtes qu’il peut avoir. On peut savoir si un graphe est dense avec une formule pour calculer la densité.

Où E=numéro d’arêtes et V= numéro de sommets. Si D est proche à 1, on dira que le graphe est dense. Si, au contraire, D est plus proche à 0, le graphe sera dispersé.

Graphe dense D=2·5/4 (4-1)=0,8333

Graphe complet: il a au moins une arête qui unisse chaque pareil de sommets, donc tous les pareils de sommets sont adjacents.

On désigne ces graphes comme Kn où #V=n.

-Alors un graphe complet accomplit la formule suivante, ou le résultat c’est le nombre d'arêtes.

-On désigne les graphes avec n sommets comme (n-1)-régulier.

-Tout graphes complète c’est régulier mais pas tous les graphes réguliers sont complets

On prend ce graphe comme exemple. Il est donc un graphe complet K5

Alors le nombre d'arêtes il faut qu’il soit strictement 10.

On peut voir que cela c’est vrai bien que les arêtes qui forment ce graphe sont :

AB,AC,AD,AE,BC,BD,BE,CD,CE,DE→ #E=10.

Une chose à tenir en compte c’est que les représentations avec matrices d'adjacence de ce type de graphes sont toujours semblables bien qu' elles soient composées par 1 et la diagonale centrale par 0. Voici la matrice d'adjacence de ce graphe K5:

On peut voir comme tous les vertices sont connectés, la matrice est formée par 1,sauf la diagonale qui montre que les sommets n’ont pas des arêtes cycliques.

Graphe incomplet : il n’a pas d’union entre tous les sommets, donc ils ne sont pas tous adjacents.

Dans ce cas tous les sommets sont adjacents sauf le sommet E lequel est seulement uni au sommet A. Alors si on applique la formule des graphes complets on verra qu’il ne s'accomplit pas.

K5=5(5-1)2=10 On voit que l’ensemble d'arêtes dans ce cas c’est: AB,AC,AD,AE,BC,BD,CD, et alors #E= 7 qui est différent à 10.

Graphe vide : il n'a aucune union. Tous ces sommets on degré 0, bien qu’ils n’ont aucune arête qui les connecte avec un autre sommet.

Dans ce cas→ grA=gr B=grC= 0

Graphe biparti : les sommets se divisent en deux groupes, par exemple X et Y. Chaque sommet du groupe X peut être seulement connecté aux sommets du groupe Y.

On divise les sommets en X→EX =[A,B,C,D] et Y→ EX=[E,F,G]

Et on peut voir que les sommets X entre eux ne sont pas connectés, de la même façon que les sommets Y ne sont plus connectés entre eux.

Graphe régulier : c’est un graphe auquel le nombre d’arêtes qui sortent de chaque sommet est le même. Donc tous les sommets de ce type de graphe ont le même degré. Comme on a déjà commenté, dans ce groupe de graphes ont trouvé tous les graphes complets, mais il faut faire attention car ne pas tous les graphes réguliers sont complets.