Théorie des graphes - Propriétés de base
Les graphiques ont diverses propriétés qui sont utilisées pour la caractérisation des graphiques en fonction de leurs structures. Ces propriétés sont définies en termes spécifiques appartenant au domaine de la théorie des graphes. Dans ce chapitre, nous aborderons quelques propriétés de base communes à tous les graphiques.
Distance entre deux sommets
C'est le nombre d'arêtes dans un chemin le plus court entre le sommet U et le sommet V. S'il y a plusieurs chemins reliant deux sommets, alors le chemin le plus court est considéré comme la distance entre les deux sommets.
Notation - d (U, V)
Il peut y avoir n'importe quel nombre de chemins présents d'un sommet à l'autre. Parmi ceux-ci, vous devez choisir uniquement le plus court.
Example
Jetez un œil au graphique suivant -
Ici, la distance entre le sommet «d» et le sommet «e» ou simplement «de» est de 1 car il y a un bord entre eux. Il existe de nombreux chemins du sommet 'd' au sommet 'e' -
- da, ab, être
- df, fg, ge
- de (Il est considéré pour la distance entre les sommets)
- df, fc, ca, ab, être
- da, ac, cf, fg, ge
Excentricité d'un sommet
La distance maximale entre un sommet et tous les autres sommets est considérée comme l'excentricité du sommet.
Notation - e (V)
La distance d'un sommet particulier à tous les autres sommets du graphe est prise et parmi ces distances, l'excentricité est la plus élevée des distances.
Example
Dans le graphique ci-dessus, l'excentricité de 'a' est de 3.
La distance entre 'a' et 'b' est 1 ('ab'),
de 'a' à 'c' vaut 1 ('ac'),
de 'a' à 'd' vaut 1 ('ad'),
de 'a' à 'e' vaut 2 ('ab' - 'be') ou ('ad' - 'de'),
de 'a' à 'f' vaut 2 ('ac' - 'cf') ou ('ad' - 'df'),
de 'a' à 'g' vaut 3 ('ac' - 'cf' - 'fg') ou ('ad' - 'df' - 'fg').
L'excentricité est donc de 3, ce qui est un maximum du sommet 'a' de la distance entre 'ag' qui est maximum.
En d'autres termes,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
e (g) = 3
Rayon d'un graphe connecté
L'excentricité minimale de tous les sommets est considérée comme le rayon du graphique G. Le minimum parmi toutes les distances maximales entre un sommet et tous les autres sommets est considéré comme le rayon du graphique G.
Notation - r (G)
De toutes les excentricités des sommets d'un graphe, le rayon du graphe connecté est le minimum de toutes ces excentricités.
Example
Dans le graphique ci-dessus, r (G) = 2, qui est l'excentricité minimale pour «d».
Diamètre d'un graphique
L'excentricité maximale de tous les sommets est considérée comme le diamètre du graphe G.Le maximum parmi toutes les distances entre un sommet et tous les autres sommets est considéré comme le diamètre du graphe G.
Notation − d(G) - De toutes les excentricités des sommets d'un graphe, le diamètre du graphe connecté est le maximum de toutes ces excentricités.
Example
Dans le graphique ci-dessus, d (G) = 3; qui est l'excentricité maximale.
Point central
Si l'excentricité d'un graphe est égale à son rayon, alors il est connu comme le point central du graphe. Si
e (V) = r (V),
alors «V» est le point central du graphique «G».
Example
Dans l'exemple de graphique, «d» est le point central du graphique.
e (d) = r (d) = 2
Centre
L'ensemble de tous les points centraux de «G» est appelé le centre du graphique.
Example
Dans l'exemple de graphique, {'d'} est le centre du graphique.
Circonférence
le number of edges in the longest cycle of ‘G’ est appelé comme la circonférence de «G».
Example
Dans l'exemple de graphique, la circonférence est de 6, ce que nous avons dérivé du plus long cycle acfgeba ou acfdeba.
Circonférence
Le nombre d'arêtes dans le cycle le plus court de «G» est appelé sa circonférence.
Notation: g (G).
Example - Dans l'exemple de graphe, la circonférence du graphe est 4, que nous avons dérivée du cycle le plus court acfda ou dfged ou abeda.
Théorème de la somme des degrés des sommets
Si G = (V, E) est un graphe non dirigé avec des sommets V = {V 1 , V 2 ,… V n } alors
Corollary 1
Si G = (V, E) est un graphe orienté de sommets V = {V 1 , V 2 ,… V n }, alors
Corollary 2
Dans tout graphe non dirigé, le nombre de sommets avec un degré impair est pair.
Corollary 3
Dans un graphe non dirigé, si le degré de chaque sommet est k, alors
Corollary 4
Dans un graphe non dirigé, si le degré de chaque sommet est au moins k, alors
| Corollary 5
Dans un graphe non dirigé, si le degré de chaque sommet est au plus k, alors