Bien qu'il existe de nombreux types de graphiques différents en fonction du nombre de sommets, du nombre d'arêtes, de l'interconnectivité et de leur structure globale, certains de ces types de graphiques courants sont les suivants :
1. Graphique nul
UN graphique nul est un graphe dans lequel il n’y a aucune arête entre ses sommets. Un graphe nul est également appelé graphe vide.
Exemple
Un graphe nul à n sommets est noté Nn.
2. Graphique trivial
UN graphique trivial est le graphe qui n'a qu'un seul sommet.
Exemple
Dans le graphique ci-dessus, il n’y a qu’un seul sommet « v » sans aucune arête. Il s’agit donc d’un graphe trivial.
3. Graphique simple
UN graphique simple est le graphe non orienté avec pas de bords parallèles et pas de boucles .
Un graphe simple qui a n sommets, le degré de chaque sommet est au plus n -1.Exemple
Dans l'exemple ci-dessus, le premier graphe n'est pas un graphe simple car il a deux arêtes entre les sommets A et B et il a également une boucle.
Le deuxième graphique est un graphique simple car il ne contient aucune boucle ni arête parallèle.
4. Graphique non orienté
Un graphe non orienté est un graphe dont les arêtes sont pas dirigé .
Exemple
Dans le graphique ci-dessus, puisqu'il n'y a pas d'arêtes orientées, il s'agit donc d'un graphique non orienté.
5. Graphique dirigé
UN Graphique dirigé est un graphique dans lequel le les bords sont dirigés par des flèches.
Le graphe orienté est également connu sous le nom de digraphes .
Exemple
Dans le graphique ci-dessus, chaque arête est dirigée par la flèche. Un bord dirigé a une flèche de A à B, ce qui signifie que A est lié à B, mais B n'est pas lié à A.
6. Graphique complet
Un graphe dans lequel chaque paire de sommets est joint par exactement une arête est appelé graphique complet . Il contient toutes les arêtes possibles.
Un graphe complet à n sommets contient exactement nC2 arêtes et est représenté par Kn.
Exemple
Dans l'exemple ci-dessus, puisque chaque sommet du graphique est connecté à tous les sommets restants par exactement une arête, les deux graphiques sont donc un graphique complet.
7. Graphique connecté
UN graphique connecté est un graphe dans lequel nous pouvons visiter n'importe quel sommet à n'importe quel autre sommet. Dans un graphe connecté, au moins une arête ou un chemin existe entre chaque paire de sommets.
Exemple
Dans l’exemple ci-dessus, nous pouvons passer de n’importe quel sommet à n’importe quel autre sommet. Cela signifie qu'il existe au moins un chemin entre chaque paire de sommets, c'est donc un graphe connecté.
8. Graphique déconnecté
UN graphique déconnecté est un graphe dans lequel aucun chemin n’existe entre chaque paire de sommets.
Exemple
Le graphique ci-dessus se compose de deux composants indépendants qui sont déconnectés. Puisqu’il n’est pas possible de visiter les sommets d’un composant aux sommets d’autres composants, il s’agit donc d’un graphe déconnecté.
9. Graphique régulier
UN Graphique régulier est un graphe dans lequel le degré de tous les sommets est le même.
Si le degré de tous les sommets est k, alors on parle de graphe k-régulier.
Exemple
Dans l’exemple ci-dessus, tous les sommets sont de degré 2. Ils sont donc appelés 2- Graphique régulier .
10. Graphique cyclique
Un graphe avec 'n' sommets (où n>=3) et 'n' arêtes formant un cycle de 'n' avec toutes ses arêtes est appelé graphique de cycle .
Un graphique contenant au moins un cycle est appelé un graphique cyclique .
Dans le graphique cyclique, le degré de chaque sommet est 2.
Le graphe cyclique qui a n sommets est noté Cn.
comment appeler une méthode en java
Exemple 1
Dans l’exemple ci-dessus, tous les sommets ont le degré 2. Ce sont donc tous des graphes cycliques.
Exemple 2
Puisque le graphique ci-dessus contient deux cycles, il s’agit donc d’un graphique cyclique.
11. Graphique acyclique
Un graphique qui ne contient aucun cycle est appelé un graphique acyclique .
Exemple
Puisque le graphique ci-dessus ne contient aucun cycle, il s’agit donc d’un graphique acyclique.
12. Graphique biparti
UN graphe biparti est un graphique dans lequel l'ensemble de sommets peut être divisé en deux ensembles de telle sorte que les arêtes ne passent qu'entre les ensembles, pas à l'intérieur d'eux.
Un graphe G (V, E) est appelé graphe biparti si son ensemble de sommets V(G) peut être décomposé en deux sous-ensembles disjoints non vides V1(G) et V2(G) de telle sorte que chaque arête e ∈ E (G) a sa dernière articulation en V1(G) et son autre dernier point en V2(G).
La partition V = V1 ∪ V2 est appelée bipartition de G.
Exemple 1
Exemple 2
13. Graphique bipartite complet
UN graphe biparti complet est un graphe biparti dans lequel chaque sommet du premier ensemble est joint à chaque sommet du deuxième ensemble par exactement une arête.
Un graphe biparti complet est un graphe biparti complet.
Complete Bipartite graph = Bipartite graph + Complete graph
Exemple
Le graphique ci-dessus est connu sous le nom de K4,3.
14. Graphique en étoile
Un graphe en étoile est un graphe biparti complet dans lequel n-1 sommets ont le degré 1 et un seul sommet a le degré (n -1). Cela ressemble exactement à une étoile dont (n - 1) sommets sont connectés à un seul sommet central.
Un graphe en étoile avec n sommets est noté Sn.
Exemple
Dans l'exemple ci-dessus, sur n sommets, tous les (n-1) sommets sont connectés à un seul sommet. Il s’agit donc d’un graphique en étoile.
15 Graphique pondéré
Un graphique pondéré est un graphique dont les bords ont été étiquetés avec des poids ou des nombres.
La longueur d'un chemin dans un graphe pondéré est la somme des poids de toutes les arêtes du chemin.
Exemple
Dans le graphique ci-dessus, si le chemin est a -> b -> c -> d -> e -> g alors la longueur du chemin est 5 + 4 + 5 + 6 + 5 = 25.
16. Multi-graphique
Un graphe dans lequel il y a plusieurs arêtes entre n'importe quelle paire de sommets ou il y a des arêtes d'un sommet à lui-même (boucle) est appelé un multi-graphique .
Exemple
Dans le graphique ci-dessus, les ensembles de sommets B et C sont connectés par deux arêtes. De même, les ensembles de sommets E et F sont connectés par 3 arêtes. Il s’agit donc d’un multigraphe.
17. Graphique planaire
UN graphe planaire est un graphe que nous pouvons tracer dans un plan de telle sorte que deux de ses arêtes ne se croisent qu'à un sommet auquel elles sont incidentes.
Exemple
Le graphique ci-dessus peut ne pas sembler planaire car ses arêtes se croisent. Mais on peut redessiner le graphique ci-dessus.
Les trois dessins plans du graphique ci-dessus sont :
Les trois graphiques ci-dessus ne sont pas constitués de deux arêtes qui se croisent et, par conséquent, tous les graphiques ci-dessus sont plans.
18. Graphique non planaire
Un graphe qui n’est pas un graphe planaire est appelé un graphe non planaire. En d’autres termes, un graphe qui ne peut être dessiné sans au moins une paire de ses arêtes croisées est appelé graphe non planaire.
Exemple
Le graphique ci-dessus est un graphique non planaire.