Graphiques et modèles de graphiques

La partie précédente a présenté les différents outils de raisonnement, de vérification et de résolution de problèmes. Dans cette partie, nous étudierons les structures discrètes qui forment la base de la formulation de nombreux problèmes réels.

Les deux structures discrètes que nous allons couvrir sont les graphiques et les arbres. Un graphe est un ensemble de points, appelés nœuds ou sommets, qui sont interconnectés par un ensemble de lignes appelées arêtes. L'étude des graphiques, ougraph theory est une partie importante d'un certain nombre de disciplines dans les domaines des mathématiques, de l'ingénierie et de l'informatique.

Qu'est-ce qu'un graphique?

Definition - Un graphe (noté $ G = (V, E) $) est constitué d'un ensemble non vide de sommets ou nœuds V et d'un ensemble d'arêtes E.

Example - Considérons, un graphe est $ G = (V, E) $ où $ V = \ lbrace a, b, c, d \ rbrace $ et $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $

Degree of a Vertex - Le degré d'un sommet V d'un graphe G (noté deg (V)) est le nombre d'arêtes incidentes avec le sommet V.

Sommet Diplôme Même bizarre
une 2 même
b 2 même
c 3 impair
1 impair

Even and Odd Vertex - Si le degré d'un sommet est pair, le sommet est appelé un sommet pair et si le degré d'un sommet est impair, le sommet est appelé un sommet impair.

Degree of a Graph- Le degré d'un graphe est le plus grand degré de sommet de ce graphe. Pour le graphique ci-dessus, le degré du graphique est de 3.

The Handshaking Lemma - Dans un graphe, la somme de tous les degrés de tous les sommets est égale à deux fois le nombre d'arêtes.

Types de graphiques

Il existe différents types de graphiques, que nous apprendrons dans la section suivante.

Graphique nul

Un graphe nul n'a pas d'arêtes. Le graphe nul des sommets $ n $ est noté $ N_n $

Graphique simple

Un graphe est appelé graphe simple / graphe strict si le graphe n'est pas orienté et ne contient pas de boucles ni d'arêtes multiples.

Multi-graphique

Si dans un graphe plusieurs arêtes entre le même ensemble de sommets sont autorisées, cela s'appelle Multigraph. En d'autres termes, il s'agit d'un graphe comportant au moins une boucle ou plusieurs arêtes.

Graphique dirigé et non dirigé

Un graphe $ G = (V, E) $ est appelé un graphe orienté si l'ensemble d'arêtes est constitué d'une paire de sommets ordonnée et un graphe est dit non orienté si l'ensemble d'arêtes est constitué d'une paire de sommets non ordonnée.

Graphique connecté et déconnecté

Un graphe est connecté si deux sommets du graphe sont reliés par un chemin; tandis qu'un graphe est déconnecté si au moins deux sommets du graphe ne sont pas reliés par un chemin. Si un graphe G est déconnecté, alors chaque sous-graphe connexe maximal de $ G $ est appelé une composante connexe du graphe $ G $.

Graphique régulier

Un graphe est régulier si tous les sommets du graphe ont le même degré. Dans un graphe régulier G de degré $ r $, le degré de chaque sommet de $ G $ est r.

Graphique complet

Un graphe est appelé graphe complet si chaque paire de deux sommets est jointe par exactement une arête. Le graphe complet à n sommets est noté $ K_n $

Graphique de cycle

Si un graphe consiste en un seul cycle, il est appelé graphe cyclique. Le graphe cyclique à n sommets est noté $ C_n $

Graphique bipartite

Si l'ensemble de sommets d'un graphe G peut être divisé en deux ensembles disjoints, $ V_1 $ et $ V_2 $, de telle sorte que chaque arête du graphe joint un sommet dans $ V_1 $ à un sommet dans $ V_2 $, et il n'y a pas d'arêtes dans G qui relient deux sommets dans $ V_1 $ ou deux sommets dans $ V_2 $, alors le graphe $ G $ est appelé un graphe biparti.

Graphique bipartite complet

Un graphe biparti complet est un graphe biparti dans lequel chaque sommet du premier jeu est joint à chaque sommet du deuxième jeu. Le graphe biparti complet est noté $ K_ {x, y} $ où le graphe $ G $ contient $ x $ sommets dans le premier ensemble et $ y $ sommets dans le second ensemble.

Représentation des graphiques

Il existe principalement deux façons de représenter un graphique -

  • Matrice d'adjacence
  • Liste de proximité

Matrice d'adjacence

Une matrice d'adjacence $ A [V] [V] $ est un tableau 2D de taille $ V \ fois V $ où $ V $ est le nombre de sommets dans un graphe non orienté. S'il y a une arête entre $ V_x $ et $ V_y $ alors la valeur de $ A [V_x] [V_y] = 1 $ et $ A [V_y] [V_x] = 1 $, sinon la valeur sera zéro. Et pour un graphe orienté, s'il y a une arête entre $ V_x $ et $ V_y $, alors la valeur de $ A [V_x] [V_y] = 1 $, sinon la valeur sera zéro.

Adjacency Matrix of an Undirected Graph

Considérons le graphe non orienté suivant et construisons la matrice de contiguïté -

La matrice d'adjacence du graphe non orienté ci-dessus sera -

a

b

c

d

a

0

1

1

0

b

1

0

1

0

c

1

1

0

1

d

0

0

1

0

Adjacency Matrix of a Directed Graph

Considérons le graphe orienté suivant et construisons sa matrice de contiguïté -

La matrice d'adjacence du graphe dirigé ci-dessus sera -

a

b

c

d

a

0

1

1

0

b

0

0

1

0

c

0

0

0

1

d

0

0

0

0

Liste de proximité

Dans la liste de contiguïté, un tableau $ (A [V]) $ de listes chaînées est utilisé pour représenter le graphe G avec $ V $ nombre de sommets. Une entrée $ A [V_x] $ représente la liste chaînée de sommets adjacents au $ Vx-ième $ sommet. La liste de contiguïté du graphe non orienté est illustrée dans la figure ci-dessous -

Graphique planaire ou non planaire

Planar graph- Un graphe $ G $ est appelé graphe plan s'il peut être dessiné dans un plan sans arêtes croisées. Si nous dessinons un graphe dans le plan sans croisement d'arête, cela s'appelle l'incorporation du graphe dans le plan.

Non-planar graph - Un graphe n'est pas plan s'il ne peut pas être dessiné dans un plan sans que les arêtes du graphe ne se croisent.

Isomorphisme

Si deux graphes G et H contiennent le même nombre de sommets connectés de la même manière, ils sont appelés graphes isomorphes (notés $ G \ cong H $).

Il est plus facile de vérifier le non-isomorphisme que l'isomorphisme. Si l'une de ces conditions suivantes se produit, alors deux graphiques sont non isomorphes -

  • Le nombre de composants connectés est différent
  • Les cardinalités des ensembles de sommets sont différentes
  • Les cardinalités définies sur les bords sont différentes
  • Les séquences de degrés sont différentes

Exemple

Les graphiques suivants sont isomorphes -

Homomorphisme

Un homomorphisme d'un graphe $ G $ à un graphe $ H $ est un mapping (peut ne pas être un mapping bijectif) $ h: G \ rightarrow H $ tel que - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ dans E (H) $. Il mappe les sommets adjacents du graphe $ G $ aux sommets adjacents du graphe $ H $.

Propriétés des homomorphismes

  • Un homomorphisme est un isomorphisme s'il s'agit d'une cartographie bijective.

  • L'homomorphisme préserve toujours les arêtes et la connectivité d'un graphe.

  • Les compositions des homomorphismes sont également des homomorphismes.

  • Découvrir s'il existe un graphe homomorphe d'un autre graphe est un problème NPcomplete.

Graphiques d'Euler

Un graphe connexe $ G $ est appelé graphe d'Euler, s'il existe une trace fermée qui inclut chaque arête du graphe $ G $. Un chemin Euler est un chemin qui utilise chaque arête d'un graphe exactement une fois. Un chemin Euler commence et se termine à différents sommets.

Un circuit d'Euler est un circuit qui utilise chaque arête d'un graphe exactement une fois. Un circuit d'Euler commence et se termine toujours au même sommet. Un graphe connexe $ G $ est un graphe d'Euler si et seulement si tous les sommets de $ G $ sont de degré pair, et un graphe connexe $ G $ est eulérien si et seulement si son ensemble d'arêtes peut être décomposé en cycles.

Le graphique ci-dessus est un graphique d'Euler sous la forme $ “a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ couvre toutes les arêtes du graphe.

Graphiques hamiltoniens

Un graphe connexe $ G $ est appelé graphe hamiltonien s'il existe un cycle qui inclut tous les sommets de $ G $ et que le cycle est appelé cycle hamiltonien. La marche hamiltonienne dans le graphe $ G $ est une marche qui passe par chaque sommet exactement une fois.

Si $ G $ est un graphe simple à n sommets, où $ n \ geq 3 $ Si $ deg (v) \ geq \ frac {n} {2} $ pour chaque sommet $ v $, alors le graphe $ G $ est Graphique hamiltonien. C'est appeléDirac's Theorem.

Si $ G $ est un graphe simple avec $ n $ sommets, où $ n \ geq 2 $ si $ deg (x) + deg (y) \ geq n $ pour chaque paire de sommets non adjacents x et y, alors le graph $ G $ est un graphe hamiltonien. C'est appeléOre's theorem.