Théorie des graphes - Types de graphes

Il existe différents types de graphiques en fonction du nombre de sommets, du nombre d'arêtes, de l'interconnectivité et de leur structure globale. Nous ne discuterons que de quelques types de graphiques importants dans ce chapitre.

Graphique nul

A graph having no edges est appelé un graphe nul.

Exemple

Dans le graphique ci-dessus, il y a trois sommets nommés «a», «b» et «c», mais il n'y a pas d'arêtes parmi eux. C'est donc un graphe nul.

Graphique trivial

UNE graph with only one vertex est appelé un graphique trivial.

Exemple

Dans le graphique ci-dessus, il n'y a qu'un seul sommet 'a' sans autres arêtes. C'est donc un graphe trivial.

Graphique non dirigé

Un graphe non dirigé contient des arêtes mais les arêtes ne sont pas dirigées.

Exemple

Dans ce graphe, 'a', 'b', 'c', 'd', 'e', ​​'f', 'g' sont les sommets, et 'ab', 'bc', 'cd', 'da ',' ag ',' gf ',' ef 'sont les arêtes du graphe. Puisqu'il s'agit d'un graphe non dirigé, les arêtes 'ab' et 'ba' sont les mêmes. De même, d'autres arêtes sont également considérées de la même manière.

Graphique dirigé

Dans un graphe orienté, chaque arête a une direction.

Exemple

Dans le graphique ci-dessus, nous avons sept sommets 'a', 'b', 'c', 'd', 'e', ​​'f' et 'g', et huit arêtes 'ab', 'cb', ' dc ',' ad ',' ec ',' fe ',' gf 'et' ga '. Comme il s'agit d'un graphe orienté, chaque arête porte une flèche indiquant sa direction. Notez que dans un graphe orienté, «ab» est différent de «ba».

Graphique simple

Un graphique with no loops et non parallel edges s'appelle un simple graphique.

• Le nombre maximum d'arêtes possibles dans un seul graphe avec 'n' sommets est ⁿ C ₂ où ⁿ C ₂ = n (n - 1) / 2.

• Le nombre de graphes simples possibles avec 'n' sommets = 2 _{ⁿ c 2} = 2 ^{n (n-1) / 2} .

Exemple

Dans le graphique suivant, il y a 3 sommets avec 3 arêtes, ce qui est maximum en excluant les arêtes et boucles parallèles. Cela peut être prouvé en utilisant les formules ci-dessus.

Le nombre maximum d'arêtes avec n = 3 sommets -

ⁿ C ₂ = n (n – 1) / 2

= 3 (3–1) / 2

= 6/2

= 3 arêtes

Le nombre maximum de graphes simples avec n = 3 sommets -

2 _{ⁿ C 2} = 2 ^{n (n-1) / 2}

= 2 ^{3 (3-1) / 2}

= 2 ³

8

Ces 8 graphiques sont comme indiqué ci-dessous -

Graphique connecté

Un graphe G est dit connexe if there exists a path between every pair of vertices. Il doit y avoir au moins une arête pour chaque sommet du graphique. Pour que nous puissions dire qu'il est connecté à un autre sommet de l'autre côté du bord.

Exemple

Dans le graphique suivant, chaque sommet a sa propre arête connectée à une autre arête. C'est donc un graphe connexe.

Graphique déconnecté

Un graphe G est déconnecté s'il ne contient pas au moins deux sommets connectés.

Exemple 1

Le graphe suivant est un exemple de graphe déconnecté, où il y a deux composants, un avec les sommets 'a', 'b', 'c', 'd' et un autre avec 'e', ​​'f', 'g', sommets 'h'.

Les deux composants sont indépendants et non connectés l'un à l'autre. Par conséquent, il est appelé graphe déconnecté.

Exemple 2

Dans cet exemple, il y a deux composants indépendants, abfe et cd, qui ne sont pas connectés l'un à l'autre. Il s'agit donc d'un graphique déconnecté.

Graphique régulier

Un graphe G est dit régulier, if all its vertices have the same degree. Dans un graphe, si le degré de chaque sommet est «k», alors le graphe est appelé «graphe k-régulier».

Exemple

Dans les graphiques suivants, tous les sommets ont le même degré. Donc, ces graphiques sont appelés graphiques réguliers.

Dans les deux graphiques, tous les sommets ont le degré 2. Ils sont appelés graphes 2-réguliers.

Graphique complet

Un graphe simple avec 'n' sommets mutuels s'appelle un graphe complet et c'est denoted by ‘K_n’. Dans le graphique,a vertex should have edges with all other vertices, puis il a appelé un graphique complet.

En d'autres termes, si un sommet est connecté à tous les autres sommets d'un graphe, il est appelé graphe complet.

Exemple

Dans les graphiques suivants, chaque sommet du graphe est connecté à tous les sommets restants du graphe, sauf par lui-même.

Dans le graphique I,

	une	b	c
une	Pas connecté	Connecté	Connecté
b	Connecté	Pas connecté	Connecté
c	Connecté	Connecté	Pas connecté

Dans le graphique II,

	p	q	r	s
p	Pas connecté	Connecté	Connecté	Connecté
q	Connecté	Pas connecté	Connecté	Connecté
r	Connecté	Connecté	Pas connecté	Connecté
s	Connecté	Connecté	Connecté	Pas connecté

Graphique de cycle

Un graphe simple avec 'n' sommets (n> = 3) et 'n' arêtes est appelé un graphe cyclique si tous ses arêtes forment un cycle de longueur 'n'.

Si le degré de chaque sommet du graphe est égal à deux, on l'appelle un graphique cyclique.

Notation- C _n

Exemple

Jetez un œil aux graphiques suivants -

• Le graphe I a 3 sommets avec 3 arêtes qui forment un cycle 'ab-bc-ca'.

• Le graphe II a 4 sommets avec 4 arêtes qui forment un cycle 'pq-qs-sr-rp'.

• Le graphe III a 5 sommets avec 5 arêtes qui forment un cycle 'ik-km-ml-lj-ji'.

Par conséquent, tous les graphiques donnés sont des graphiques cycliques.

Graphique de roue

Un graphe de roue est obtenu à partir d'un graphe cyclique C _n-1 en ajoutant un nouveau sommet. Ce nouveau sommet s'appelle unHubqui est connecté à tous les sommets de C _n .

Notation - W _n

Nombre d'arêtes dans W _n = Nombre d'arêtes du moyeu à tous les autres sommets +

Nombre d'arêtes de tous les autres nœuds dans le graphique cyclique sans moyeu.

= (n – 1) + (n – 1)

= 2 (n – 1)

Exemple

Jetez un œil aux graphiques suivants. Ce sont tous des graphiques de roue.

Dans le graphe I, il est obtenu à partir de C ₃ en ajoutant un sommet au milieu nommé «d». Il est noté W ₄ .

Nombre d'arêtes dans W4 = 2 (n-1) = 2 (3) = 6

Dans le graphe II, il est obtenu à partir de C4 en ajoutant un sommet au milieu nommé «t». Il est noté W ₅ .

Nombre d'arêtes dans W5 = 2 (n-1) = 2 (4) = 8

Dans le graphe III, il est obtenu à partir de C ₆ en ajoutant un sommet au milieu nommé «o». Il est noté W ₇ .

Nombre d'arêtes dans W4 = 2 (n-1) = 2 (6) = 12

Graphique cyclique

Un graphique with at least one cycle est appelé un graphe cyclique.

Exemple

Dans l'exemple de graphique ci-dessus, nous avons deux cycles abcda et cfgec. C'est pourquoi on l'appelle un graphe cyclique.

Graphique acyclique

Un graphique with no cycles est appelé un graphe acyclique.

Exemple

Dans l'exemple de graphique ci-dessus, nous n'avons aucun cycle. C'est donc un graphe non cyclique.

Graphique bipartite

Un graphe simple G = (V, E) avec une partition de sommets V = {V ₁ , V ₂ } est appelé un graphe bipartiif every edge of E joins a vertex in V1 to a vertex in V₂.

En général, un graphe Bipertite a deux ensembles de sommets, disons V1 et V2, et si une arête est dessinée, il doit relier n'importe quel sommet de l'ensemble V ₁ à n'importe quel sommet de l'ensemble V ₂ .

Exemple

Dans ce graphique, vous pouvez observer deux ensembles de sommets - V ₁ et V ₂ . Ici, deux arêtes nommées «ae» et «bd» relient les sommets de deux ensembles V ₁ et V ₂ .

Graphique bipartite complet

Un graphe biparti 'G', G = (V, E) avec la partition V = {V ₁ , V ₂ } est dit être un graphe biparti complet si chaque sommet de V ₁ est connecté à chaque sommet de V ₂ .

En général, un graphe biparti complet relie chaque sommet de l'ensemble V ₁ à chaque sommet de l'ensemble V ₂ .

Exemple

Le graphe suivant est un graphe biparti complet car il a des arêtes reliant chaque sommet de l'ensemble V ₁ à chaque sommet de l'ensemble V ₂ .

Si | V ₁ | = m et | V ₂ | = n, alors le graphe biparti complet est noté K _{m, n} .

• K _{m, n} a (m + n) sommets et (mn) arêtes.
• K _{m, n} est un graphe régulier si m = n.

En général, un complete bipartite graph is not a complete graph.

K _{m, n} est un graphe complet si m = n = 1.

Le nombre maximum d'arêtes dans un graphe biparti avec n sommets est -

[n ^deux / 4]

Si n = 10, K5, 5 = [n2 / 4] = [10 ² /4] = 25.

De même, K6, 4 = 24

K7, 3 = 21

K8, 2 = 16

K9, 1 = 9

Si n = 9, k5, 4 = [n2 / 4] = [92/4] = 20

De même, K6, 3 = 18

K7, 2 = 14

K8, 1 = 8

'G' est un graphe biparti si 'G' n'a pas de cycles de longueur impaire. Un cas particulier de graphe biparti est un graphe en étoile.

Graphique en étoile

Un graphe biparti complet de la forme K1, n-1 est un graphe en étoile à n-sommets. Un graphe en étoile est un graphe biparti complet si un seul sommet appartient à un ensemble et tous les sommets restants appartiennent à l'autre ensemble.

Exemple

Dans les graphiques ci-dessus, sur «n» sommets, tous les «n – 1» sommets sont connectés à un seul sommet. Il se présente donc sous la forme de K ¹ , ^n-1 qui sont des graphes en étoile.

Complément d'un graphique

Soit 'G−' un graphe simple avec quelques sommets comme celui de 'G' et une arête {U, V} est présente dans 'G−', si l'arête n'est pas présente dans G. Cela signifie que deux sommets sont adjacents dans 'G−' si les deux sommets ne sont pas adjacents dans G.

Si les arêtes qui existent dans le graphe I sont absentes dans un autre graphe II, et si le graphe I et le graphe II sont combinés ensemble pour former un graphe complet, alors le graphe I et le graphe II sont appelés des compléments l'un de l'autre.

Exemple

Dans l'exemple suivant, graph-I a deux arêtes 'cd' et 'bd'. Son complément graph-II a quatre arêtes.

Notez que les arêtes du graphe-I ne sont pas présentes dans le graphe-II et vice versa. Par conséquent, la combinaison des deux graphiques donne un graphique complet de «n» sommets.

Note - Une combinaison de deux graphiques complémentaires donne un graphique complet.

Si 'G' est un graphe simple, alors

| E (G) | + | E ('G -') | = | E (Kn) |, où n = nombre de sommets dans le graphe.

Exemple

Soit 'G' un graphe simple avec neuf sommets et douze arêtes, trouvez le nombre d'arêtes dans 'G-'.

Vous avez, | E (G) | + | E ('G -') | = | E (Kn) |

12 + | E ('G -') | =

9 (9-1) / 2 = ⁹ C ₂

12 + | E ('G -') | = 36

| E ('G -') | = 24

'G' est un graphe simple avec 40 arêtes et son complément 'G−' a 38 arêtes. Trouvez le nombre de sommets dans le graphe G ou 'G−'.

Soit «n» le nombre de sommets du graphe.

Nous avons, | E (G) | + | E ('G -') | = | E (Kn) |

40 + 38 = n (n-1) / 2

156 = n (n-1)

13 (12) = n (n-1)

n = 13