UN Graphiques non orientés : Un graphique dans lequel les arêtes n'ont pas de direction, c'est-à-dire que les arêtes n'ont pas de flèches indiquant la direction du parcours. Exemple : Un graphique de réseau social où les amitiés ne sont pas directionnelles.

Graphiques dirigés : Un graphique dans lequel les arêtes ont une direction, c'est-à-dire que les arêtes ont des flèches indiquant la direction du parcours. Exemple : un graphique de page Web dans lequel les liens entre les pages sont directionnels.

Graphiques pondérés : Graphique dans lequel les arêtes sont associées à des poids ou à des coûts. Exemple : Un graphique de réseau routier où les poids peuvent représenter la distance entre deux villes.

Graphique non pondéré s : un graphique dans lequel les arêtes ne sont associées à aucun poids ni coût. Exemple : Un graphique de réseau social dont les bords représentent des amitiés.

Graphiques complets : Un graphique dans lequel chaque sommet est connecté à tous les autres sommets. Exemple : Un graphique de tournoi où chaque joueur joue contre tous les autres joueurs.

Graphiques bipartis : Un graphe dans lequel les sommets peuvent être divisés en deux ensembles disjoints de telle sorte que chaque arête connecte un sommet d'un ensemble à un sommet de l'autre ensemble. Exemple : un graphique de candidats à un emploi dont les sommets peuvent être divisés en candidats et offres d'emploi.

Des arbres : Un graphique connecté sans cycles. Exemple : Un arbre généalogique où chaque personne est connectée à ses parents.

Cycles : Un graphique avec au moins un cycle. Exemple : Un graphique de partage de vélos où les cycles représentent les itinéraires empruntés par les vélos.

Graphiques clairsemés : Un graphe avec relativement peu d'arêtes par rapport au nombre de sommets. Exemple : Un graphique de réaction chimique où chaque sommet représente un composé chimique et chaque arête représente une réaction entre deux composés.

Graphique dense s : Un graphe avec de nombreuses arêtes par rapport au nombre de sommets. Exemple : Un graphique de réseau social où chaque sommet représente une personne et chaque arête représente une amitié.

Types de graphiques :

1. Graphiques finis

Un graphe est dit fini s’il possède un nombre fini de sommets et un nombre fini d’arêtes. Un graphe fini est un graphe comportant un nombre fini de sommets et d’arêtes. En d’autres termes, le nombre de sommets et le nombre d’arêtes dans un graphe fini sont limités et peuvent être comptés. Les graphes finis sont souvent utilisés pour modéliser des situations du monde réel, dans lesquelles il existe un nombre limité d'objets et de relations entre les objets.

2. Graphique infini :

Un graphe est dit infini s’il possède un nombre infini de sommets ainsi qu’un nombre infini d’arêtes.

3. Graphique trivial :

Un graphe est dit trivial si un graphe fini ne contient qu’un seul sommet et aucune arête. Un graphe trivial est un graphe comportant un seul sommet et aucune arête. Il est également connu sous le nom de graphe singleton ou de graphe à sommet unique. Un graphe trivial est le type de graphe le plus simple et est souvent utilisé comme point de départ pour créer des graphes plus complexes. En théorie des graphes, les graphes triviaux sont considérés comme un cas dégénéré et ne sont généralement pas étudiés en détail.

dessiner un rectangle gimp

4. Graphique simple :

Un graphe simple est un graphe qui ne contient pas plus d’une arête entre la paire de sommets. Une simple voie ferrée reliant différentes villes est un exemple de graphique simple.

5. Multi-graphique :

Tout graphe contenant des arêtes parallèles mais ne contenant aucune auto-boucle est appelé multigraphe. Par exemple une feuille de route.

• Bords parallèles : Si deux sommets sont connectés par plus d’une arête, alors ces arêtes sont appelées arêtes parallèles qui sont plusieurs routes mais une seule destination.
• Boucle: Une arête d’un graphe qui commence à partir d’un sommet et se termine au même sommet est appelée une boucle ou une auto-boucle.

6. Graphique nul :

Un graphe d'ordre n et de taille zéro est un graphe où il n'y a que des sommets isolés sans arêtes reliant une paire de sommets. Un graphe nul est un graphe sans arêtes. En d’autres termes, il s’agit d’un graphe comportant uniquement des sommets et aucune connexion entre eux. Un graphe nul peut également être appelé graphe sans bords, graphe isolé ou graphe discret.

7. Graphique complet :

Un graphe simple avec n sommets est appelé graphe complet si le degré de chaque sommet est n-1, c'est-à-dire qu'un sommet est attaché à n-1 arêtes ou au reste des sommets du graphe. Un graphique complet est également appelé Full Graph.

8. Pseudo-graphique :

Un graphe G avec une auto-boucle et quelques arêtes multiples est appelé pseudo-graphe. Un pseudographe est un type de graphe qui permet l'existence d'auto-boucles (arêtes qui relient un sommet à lui-même) et de plusieurs arêtes (plus d'une arête reliant deux sommets). En revanche, un graphique simple est un graphique qui ne permet pas de boucles ou d’arêtes multiples.

9. Graphique régulier :

Un graphe simple est dit régulier si tous les sommets du graphe G sont de même degré. Tous les graphiques complets sont réguliers mais l’inverse n’est pas possible. Un graphe régulier est un type de graphe non orienté dans lequel chaque sommet a le même nombre d’arêtes ou de voisins. En d’autres termes, si un graphe est régulier, alors chaque sommet a le même degré.

10. Graphique biparti :

Un graphe G = (V, E) est dit un graphe biparti si son ensemble de sommets V(G) peut être divisé en deux sous-ensembles disjoints non vides. V1(G) et V2(G) de telle sorte que chaque arête e de E(G) ait une extrémité dans V1(G) et une autre extrémité dans V2(G). La partition V1 U V2 = V est dite Bipartite de G. Ici sur la figure : V1(G)={V5, V4, V3} et V2(G)={V1, V2}

11. Graphique étiqueté :

Si les sommets et les arêtes d’un graphique sont étiquetés avec un nom, une date ou un poids, on parle alors de graphique étiqueté. Il est également appelé graphique pondéré.

12. Graphique digraphique :

Un graphe G = (V, E) avec une application f telle que chaque arête correspond à une paire ordonnée de sommets (Vi, Vj) est appelé un digraphe. On l'appelle aussi Graphique dirigé . Le couple ordonné (Vi, Vj) désigne une arête entre Vi et Vj avec une flèche dirigée de Vi vers Vj. Ici sur la figure : e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Sous-graphique :

Un graphe G1 = (V1, E1) est appelé sous-graphe d'un graphe G(V, E) si V1(G) est un sous-ensemble de V(G) et E1(G) est un sous-ensemble de E(G) tel que chaque arête de G1 a les mêmes sommets d’extrémité que dans G.

14. Graphique connecté ou déconnecté :

Un graphe G est dit connexe si une paire de sommets (Vi, Vj) d’un graphe G est accessible l’un depuis l’autre. Ou bien un graphe est dit connecté s’il existe au moins un chemin entre chaque paire de sommets du graphe G, sinon il est déconnecté. Un graphe nul avec n sommets est un graphe déconnecté composé de n composants. Chaque composant est constitué d'un sommet et d'aucune arête.

comment mettre à jour Java

15. Graphique cyclique :

Un graphe G composé de n sommets et n> = 3 soit V1, V2, V3- – – – Vn et les arêtes (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) sont appelés graphe cyclique.

16. Types de sous-graphiques :

• Sous-graphe disjoint du sommet : Deux graphes G1 = (V1, E1) et G2 = (V2, E2) sont dits sommets disjoints d'un graphe G = (V, E) si V1(G1) intersection V2(G2) = nulle. Sur la figure, il n’y a pas de sommet commun entre G1 et G2.
• Sous-graphe disjoint de bord : Un sous-graphe est dit bord-disjoint si E1(G1) intersection E2(G2) = nulle. Sur la figure, il n’y a pas d’arête commune entre G1 et G2.

Note: Le sous-graphe disjoint d'arêtes peut avoir des sommets en commun, mais un graphe disjoint de sommets ne peut pas avoir d'arête commune, donc le sous-graphe disjoint de sommets sera toujours un sous-graphe disjoint d'arêtes.

17. Sous-graphique couvrant

Considérons le graphique G(V,E) comme indiqué ci-dessous. Un sous-graphe couvrant est un sous-graphe qui contient tous les sommets du graphe d'origine G qui est G'(V',E') s'étendant si V'=V et E' est un sous-ensemble de E.

Ainsi, l'un des sous-graphes couvrant peut être comme indiqué ci-dessous G'(V',E'). Il possède tous les sommets du graphe original G et certaines arêtes de G.

Ce n'est que l'un des nombreux sous-graphes étendus du graphe G. Nous pouvons créer divers autres sous-graphes étendus par différentes combinaisons d'arêtes. Notez que si l'on considère un graphe G'(V',E') où V'=V et E'=E, alors le graphe G' est un sous-graphe étendu du graphe G(V,E).

Avantages des graphiques :

1. Les graphiques peuvent être utilisés pour modéliser et analyser des systèmes et des relations complexes.
2. Ils sont utiles pour visualiser et comprendre les données.
3. Les algorithmes graphiques sont largement utilisés en informatique et dans d’autres domaines, tels que l’analyse des réseaux sociaux, la logistique et les transports.
4. Les graphiques peuvent être utilisés pour représenter un large éventail de types de données, notamment les réseaux sociaux, les réseaux routiers et Internet.

Inconvénients des graphiques :

1. Les grands graphiques peuvent être difficiles à visualiser et à analyser.
2. Les algorithmes graphiques peuvent être coûteux en termes de calcul, en particulier pour les grands graphiques.
3. L'interprétation des résultats graphiques peut être subjective et nécessiter des connaissances spécifiques au domaine.
4. Les graphiques peuvent être sensibles au bruit et aux valeurs aberrantes, ce qui peut avoir un impact sur la précision des résultats d'analyse.

Article associé: Applications, avantages et inconvénients du graphique