Les graphes nexialistes représentent les connexités existant entre plusieurs éléments.

Ces graphes sont généralement produits par apprentissage. Dans ce cas l’algorithme d’apprentissage doit également respecter les règles de construction des graphes ce qui rajoute à la complexité naturelle d’un algorithme d’apprentissage.

Les graphes sont connexes s’il existe un chemin entre toute paire de nœuds du graphe. Ils sont k-connexes s’il existe k chemins disjoints entre toute paire de nœuds du graphe. (Lacomme Philippe, 2007).

A l’inverse un graphe non connexe peut être constitué de composantes connexes. Il s’agit de sous-graphes maximaux connexes, on parle alors du nombre de connexité du graphe.

Les graphes nexialistes se présentent souvent sous forme de forêts de graphes car les connexités sont généralement typées et multiples. Le graphe connexe dispose parfois de points d’articulation, ce sont des nœuds qui lorsqu’ils sont supprimés augmentent le nombre de connexité du graphe. Il peut également disposer d’isthmes, ce sont des arcs qui lorsqu’ils sont supprimés augmentent aussi le nombre de connexité du graphe. Le nombre de points d’articulation et d’isthmes représente le niveau de vulnérabilité du graphe.

Lacomme Philippe, Prins Christian, Sevaux Marc. 2007. Algorithmes de graphes. s.l. : Eyrolles, 2007.